排序算法

Reference

中山大学, 王若梅老师”数据结构与算法”课件

Intro

Sorting 排序:将一组杂乱无章的数据排列成一个按关键字有序的序列。

数据表(datalist): 它是待排序数据对象的有限集合。

关键字(key): 通常数据对象有多个属性域,即多个数据成员组成,其中有一个属性域可用来区分对象,作为排序依据。该域即为关键字。每个数据表用哪个属性域作为关键字,要视具体的应用需要而定。即使是同一个表,在解决不同问题的场合也可能取不同的域做关键字。

Stability 排序算法的稳定性: 如果在对象序列中有两个对象r[i]和r[j],它们的关键字 k[i] == k[j],且在排序之前,对象r[i]排在r[j]前面。如果在排序之后,对象r[i]仍在对象r[j]的前面,则称这个排序方法是稳定的,否则称这个排序方法是不稳定的。

内排序与外排序: 内排序是指在排序期间数据对象全部存放在内存的排序;外排序是指在排序期间全部对象个数太多, 不能同时存放在内存,必须根据排序过程的要求,不断在内、 外存之间移动的排序。

排序的时间开销: 排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。各节给出算法运行时间代价的大略估算一般都按平均情况进行估算。对于那些受对象关键字序列初始排列及对象个数影响较大的,需要按最好情况和最坏情况进行估算。

衡量排序方法的标准

  • 排序时所需要的平均比较次数
  • 排序时所需要的平均移动
  • 排序时所需要的平均辅助存储空间
  • 排序的稳定性

Summary

1557848373380

插入排序(Insert Sort)

插入排序的基本方法是:每步将一个待排序的对象,按其关键字大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。

直接插入排序(Straight Insertion Sort)

将一个记录插入到已排序好的有序表中,从而得到一个新,记录数增1的有序表。即:先将序列的第1个记录看成是一个有序的子序列,然后从第2个记录逐个进行插入,直至整个序列有序为止。

要点:设立哨兵,作为临时存储和判断数组边界之用。

直接插入排序示例:

1342520948_8667

如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。

算法分析

  • 当待排序的关键字序列已经基本有序时, 用直接插入排序最快
  • 若设待排序的对象个数为L.length= n,则该算法的主程序执行n-1趟
  • 关键字比较次数和对象移动次数与对象关键字的初始排列有关。
  • 最好情况下,排序前对象已经按关键字大小从小到大有序,每趟只需与前面的有序对象序列的最后一个对象的关键字比较 1 次,移动 2 次对象,总的关键字比较次数为 n-1,对象移动次数为2(n-1)。
  • 若待排序对象序列中出现各种可能排列的概率相同,则可取上述最好情况和最坏情况的平均情况。在平均情况下的关键字比较次数和对象移动次数约为$n^2/4$。因此,直接插入排序的时间复杂度为$o(n^2)$。
  • 直接插入排序是一种稳定的排序方法。

二分插入排序

在查找插入位置时使用二分搜索, 选取插入

希尔排序(Shell Sort)

思想:分治策略

希尔排序是一种分组直接插入排序方法,其原理是:先将整个序列分割成若干小的子序列,再分别对子序列进行直接插入排序,使得原来序列成为基本有序。这样通过对较小的序列进行插入排序,然后对基本有序的数列进行插入排序,能够提高插入排序算法的效率

具体如下(实现为升序):

  1. 先取一个小于n的整数d1作为第一个增量,将所有距离为d1的倍数的记录放在同一个组中,把无序数组分割为若干个子序列。

  2. 在各子序列内进行直接插入排序。

  3. 然后取第二个增量d2<d1,重复步骤1~2,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。

算法分析

希尔排序的时间复杂度与步长序列$\{d_n\}$有关

gap的取法有多种。最初 shell 提出取 gap = [n/2],gap = [gap/2],直到gap = 1。后来Knuth 提出取gap = [gap/3] +1。还有人提出都取奇数为好,也有人提出各gap互质为 好。

wiki上有详细的对比, 我选取其中表现较好, 实现简单的两种介绍

  • 形式为$2^p3^q$的光滑数, 1, 2, 3, 4, 6, 8, 9, 12..., 时间复杂度为$\Theta(nlog^2n)$

  • 时间复杂度为$O(n^{4/3})$

交换排序(Exchange Sort)

交换排序的基本思想是两两比较待排序对象的关键字,如果发生逆序(即排列顺序与排序后的次序正好相反),则交换之, 直到所有对象都排好序为止。

冒泡排序(Bubble Sort)

冒泡排序是第一个接触也最容易理解的排序算法,因为就像泡泡一样,最轻的率先“冒”出来占据第一的位置,随后是剩下的最轻的再冒出来,占据第二的位置,就这样一步步冒出来,也就完成了排序。

1
2
3
4
5
6
7
8
9
10
    void bubbleSort(int a[], int n){  
        for(int i =0 ; i< n-1; ++i) {  
            for(int j = 0; j < n-i-1; ++j) {  
                if(a[j] > a[j+1])  
                {  
                    int tmp = a[j] ; a[j] = a[j+1] ;  a[j+1] = tmp;  
                }  
            }  
        }  
    }

算法步骤

  1. 对象个数n。最多作最多作n-1趟, i= 0, 2, …, n-1 。
  2. 第i趟中从后向前j= n-1, n-2, ……, i,顺次两两比较
  3. 比较如果发生逆序,则交换V[j-1] 和V[j]。

总之就是每一趟都是将剩余中最大或最小的数据项排在前面已经“冒”出来的数据表后面,遍历完毕也就实现了排序。

算法分析

最好情况:正序排列,比较次数(KCN):n−1 ; 移动次数(RMN):为0。则对应的时间复杂度为O(n)。

完全正序排列的话,只需一趟就能判定是否有序,如果遍历j之后发现没有发生逆序就说明已经有序,所以,共比较了n−1次,移动0次。

最坏情况:逆序排序,比较次数(KCN):∑n−1i=1(n−i)=n(n−1)2;移动次数(RMN):3∑n−1i=1(n−i)=3n(n−1)2。

完全逆序排序的话,第i都要比较n−i次,而每次比较都要移动3次数据项来交换记录位置。因此总的时间复杂度为O(n2)。

它需要一个附加空间,是一个稳定的排序算法。

算法优化

对冒泡排序常见的改进方法是加入一标志性变量exchange,用于标志某一趟排序过程中是否有数据交换,如果进行某一趟排序时并没有进行数据交换,则说明数据已经按要求排列好,可立即结束排序,避免不必要的比较过程。

1
2
3
4
5
6
7
8
9
10
11
12
    void Bubble_1 ( int r[], int n) {  
        int i= n -1;  //初始时,最后位置保持不变  
        while ( i> 0) {  
            int pos= 0; //每趟开始时,无记录交换  
            for (int j= 0; j< i; j++)  
                if (r[j]> r[j+1]) {  
                    pos= j; //记录交换的位置  
                    int tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;  
                }  
            i= pos; //为下一趟排序作准备  
         }  
    }

快速排序(Quick Sort)

算法思想

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。

步骤

  • 分解
  • 求解
  • 组合

算法步骤

  • 快速排序方法的基本思想是任取待排序对象序列中的某个对象 (例如取第一个对象) 作为枢轴(pivot),按照该对象的关键字大小,将整个对象序列划分为左右两个子序列:
    • 左侧子序列中所有对象的关键字都小于或等于枢轴对象的关键字
    • 右侧子序列中所有对象的关键字都大于枢轴对象的关键字
  • 枢轴对象则排在这两个子序列中间(这也是该对象最终应安放的位置)。
  • 然后分别对这两个子序列重复施行上述方法,直到所有的对象都排在相应位置上为止。

如何划分

2011111422474014

  1. 首先我们从数组的left位置取出该数(20)作为基准(base)参照物。
  2. 从数组的right位置向前找,一直找到比(base)小的数,如果找到,将此数赋给left位置(也就是将10赋给20)
    此时数组为:10,40,50,10,60,
    left和right指针分别为前后的10。
  3. 从数组的left位置向后找,一直找到比(base)大的数
    如果找到,将此数赋给right的位置(也就是40赋给10)
    left和right指针分别为前后的40。
  4. 重复“第二,第三“步骤,直到left和right指针重合
    最后将(base)插入到40的位置,
    此时数组值为: 10,20,50,40,60,至此完成一次排序。

算法分析

  • 当待排序关键字序列已经基本有序时,快速排序显著变慢。
  • 从快速排序算法的递归树可知,快速排序的趟数取决于递归树的深度。
  • 平均情况
    • 可以证明,函数quicksort的平均计算时间也是 O(nlog2n)。实验结果表明:就平均计算时间而言, 快速排序是我们所讨论的所有内排序方法中最好的 一个。
  • 理想情况
    • 如果每次划分对一个对象定位后,该对象的左侧子序列与右侧子序列的长度相同,则下一步将是对两个长度减半的子序列进行排序,这是最理想的情况。
    • 在n个元素的序列中,对一个对象定位所需时间为O(n)。若设 t(n) 是对n 个元素的序列进行排序所需的时间,而且每次对一 个对象正确定位后,正好把序列划分为长度相等的两个子序列,此时,总的计算时间为:O(nlogn)
  • 快速排序是递归的,需要有一个栈存放每层递归调用时的指针和参数。
  • 最大递归调用层次数与递归树的深度一致, 理想情况为 log2(n+1)。因此,要求存储开销为 o(log2n)。
  • 最坏情况
    • 在最坏的情况,即待排序对象序列已经按其关键字从小到大 排好序的情况下,其递归树成为单支树,每次划分只得到一 个比上一次少一个对象的子序列。这样,必须经过 n-1 趟才 能把所有对象定位,而且第 i 趟需要经过 n-i 次关键字比较 才能找到第 i 个对象的安放位置,总的关键字比较次数将达到$\sum\limits_{i=1}^{n-1}(n-i)$
    • 其排序速度退化到简单排序的水平,比直接插入排序还慢。占用附加存储(即栈)将达到o(n)。
    • 若能更合理地选择基准对象,使得每次划分所得的两个子序列中的对象个数尽可能地接近,可以加速排序速度,但是由于对 象的初始排列次序是随机的,这个要求很难办到。
    • 有一种改进办法:取每个待排序对象序列的第一个对象、最后一个对象和位置接近正中的3个对象,取其关键字居中者作为基准对象。

改进

  • key的选取
  • 内观排序

改版

  • 快速选择(BFPRT)

选择排序(Selection Sort)

选择排序的基本思想是:每一趟(例如第 i 趟,i = 1, …, n-1) 在后面的n-i+1个待排序对象中选出关键字最小的对象, 作为有序对象序列的第 i 个对象。待到第n-1 趟 作完,待排序对象只剩下1个,就不用再选了。

简单选择排序(Simple Selection Sort)

基本步骤为:i从1开始,直到n-1,进行n-1趟排序,第i趟的 排序过程为:在一组对象r[i]~r[n] (i=1,2,…,n-1)中选择具有 最小关键字的对象;并和第i 个对象进行交换;

算法分析

  • 不稳定, 因为交换有跳跃性
  • 直接选择排序的关键字比较次数KCN与对象的初始 排列无关。第 i 趟选择具有最小关键字对象所需的 比较次数总是 n-i-1 次,此处假定整个待排序对象序 列有 n 个对象。因此,总的关键字比较次数为$\frac{n(n-1)}{2}$
  • 对象的移动次数与对象序列的初始排列有关。当这组对象的初始状态是按其关键字从小到大有序的时 候,对象的移动次数RMN = 0,达到最少。
  • 最坏情况是每一趟都要进行交换,总的对象移动次 数为RMN= 3(n-1)。

树形选择排序

堆排序

利用堆的概念,可以很容易地实现选择排序 的思路。堆排序分为两个步骤:第一步,根 据初始输入数据,利用堆的调整算法 形成初 始堆,输出堆顶元素。第二步,重新调整剩 余元素使之成为堆。重复以上操作

步骤

  • 最大堆的第一个对象r[1]具有最大的关键字,将r[1]与r[n]对调, 把具有最大关键字的对象交换到最后,再对前面的n-1个对象, 使用堆的调整算法HeapAdjust(1, n-1),重新建立最大堆。结 果具有次最大关键字的对象又上浮到堆顶,即r[1]位置。
  • 再对调r[1]和r[n-1],调用HeapAdjust (1, n-2),对前n-2个对 象重新调整,…。
  • 如此反复执行,最后得到全部排序好的对象序列。这个算法 即堆排序算法。

1545784906161

1545784916137

1545784957329

1545784971481

1545784997647

1545785008459

1545785021364

1545785029817

1545785042366

1545785051266

算法分析

  • 建堆时间复杂度为$O(nlogn)$
  • 单次调整时间复杂度为$O(logn)$
  • 该算法的附加存储主要是在第二个for循环中用来执行 对象交换时所用的一个临时对象。因此,该算法的空间复杂性为O(1)
  • 堆排序是一个不稳定的排序方法

归并排序(Merge Sort)

归并排序的提出是为了解决外部排序问题.

归并,是将两个或两个以上的有序表合并成一个新的有序表。

对象序列 initList中有两个有序表V[l] …V[m]和V[m+1] …V[n]。 它们可归并成一个有序表,存于另一对象序列mergedList的 V[l] …V[n]中。

这种归并方法称为2-路归并(2-way merging)。

基本思想是:设两个有序表A和B的对象个数(表长)分别为 al和 bl,变量i 和 j 分别是表A和表B的当前检测指针。设表C 是归并后的新有序表,变量k是它的当前存放指针。

算法步骤

假设初始对象序列有n 个对象,首先把它看成是 n 个长度为 1 的有序子序列 (归并项),先做两两归并, 得到 n / 2个长度为 2 的归并项 (如果 n 为奇数,则 最后一个有序子序列的长度为1);再做两两归并,…, 如此重复,最后得到一个长度为n 的有序序列。

算法分析

  • 在归并排序算法中,递归深度为O(log2n),对象 关键字的比较次数为O(nlog2n)。算法总的时间 复杂度为O(nlog2n)。
  • 归并排序占用附加存储较多,需要另外一个与 原待排序对象数组同样大小的辅助数组。这是 这个算法的缺点。
  • 归并排序是一个稳定的排序方法。

基数排序(Radix Sort)

基数排序是采用“分配”与“收集”的办法, 用对多关键字进行排序的思想实现对单关键字进行排序的方法。

多关键字排序

  • 最高位优先MSD (Most Significant Digit first)
  • 最低位优先LSD (Least Significant Digit first)

混合排序

内观排序/内省排序(Intro Sort)

https://zh.wikipedia.org/wiki/%E5%86%85%E7%9C%81%E6%8E%92%E5%BA%8F

  • 从快速排序开始, 在三个基准中选择基准点, 以防止退化.
  • 当递归深度超过一定深度(深度为排序元素数量的对数值)后转为堆排序。采用这个方法,内省排序既能在常规数据集上实现快速排序的高性能,又能在最坏情况下仍保持$O(nlogn)$的时间复杂度.
  • 当数据量较小时, 会切换到插入排序.
文章目录
  1. 1. Reference
  2. 2. Intro
  3. 3. Summary
  4. 4. 插入排序(Insert Sort)
    1. 4.1. 直接插入排序(Straight Insertion Sort)
    2. 4.2. 二分插入排序
    3. 4.3. 希尔排序(Shell Sort)
  5. 5. 交换排序(Exchange Sort)
    1. 5.1. 冒泡排序(Bubble Sort)
    2. 5.2. 快速排序(Quick Sort)
  6. 6. 选择排序(Selection Sort)
    1. 6.1. 简单选择排序(Simple Selection Sort)
    2. 6.2. 树形选择排序
    3. 6.3. 堆排序
  7. 7. 归并排序(Merge Sort)
  8. 8. 基数排序(Radix Sort)
  9. 9. 混合排序
    1. 9.1. 内观排序/内省排序(Intro Sort)
|