《常用排序算法总结——数据结构》由会员分享，可在线阅读，更多相关《常用排序算法总结——数据结构（70页珍藏版）》请在金锄头文库上搜索。
1、设 n 个记录的序列为 R1 , R2 , R3 , . . . , Rn ,其相应的关键字序列为 K1 , K2 , K3 , . . . , Kn ,此操作过程称为排序。,排序,假设 Ki = Kj ，且排序前序列中 Ri 领先于 Rj ；,若在排序后的序列中 Ri 仍领先于 Rj ，则称排序方法是稳定的。,若在排序后的序列中 Rj 仍领先于 Ri ，则称排序方法是不稳定的。,例，序列 3 15 8 8 6 9,若排序后得 3 6 8 8 9 15,稳定的,若排序后得 3 6 8 8 9 15,不稳定的,稳定排序与不稳定排序,内部排序: 指的是待排序记录存放在计算机随机存储器中进行的排序过
2、程。,外部排序: 指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。,内部排序与外部排序,排序的时间复杂性,排序过程主要是对记录的排序码进行比较和记录的移动过程。因此排序的时间复杂性可以算法执行中的数据比较次数及数据移动次数来衡量。当一种排序方法使排序过程在最坏或平均情况下所进行的比较和移动次数越少，则认为该方法的时间复杂性就越好，分析一种排序方法，不仅要分析它的时间复杂性，而且要分析它的空间复杂性、稳定性和简单性等。,按照排序过程中所依据的原则的不同可以分类为:,插入排序,交换排序(快速排序),选择排序,归并排序,基数排序,二叉排序树排序,内
3、部排序,思想: 利用有序表的插入操作进行排序,有序表的插入: 将一个记录插入到已排好序的有序表中，从而得到一个新的有序表。,例，序列 13 27 38 65 76 97,插入 49,13 27 38 49 65 76 97,插入排序直接插入排序,例，序列 49 38 65 97 76 13 27,初始，S = 49 ；, 38 49 ,初始，令第 1 个元素作为初始有序表；,依次插入第 2 , 3 , , k 个元素构造新的有序表；,直至最后一个元素；,直接插入排序算法主要应用比较和移动两种操作。,直接插入排序算法描述,void insertsort(ElemType R,int n) /待排
4、序元素用一个数组R表示，数组有n个元素 for ( int i=1; i=0) ,直接插入排序的效率分析,从空间来看，它只需要一个元素的辅助空间，用于元素的位置交换。 从时间分析，首先外层循环要进行n-1次插入，每次插入最少比较一次（正序），移动两次；最多比较i次，移动i2次（逆序）（i=1，2，n-1）。 Cmin=n-1 M min=2（n-1） Cmax=1+2+n-1=（n2-n）/2 M max=3+4+n+1=（n2+3n-4）/2 Cave=（n2+n-2）/4 M max=（n2+7n-8）/4 因此，直接插入排序的时间复杂度为O（n2）。 直接插入算法的元素移动是顺序的，该方
5、法是稳定的。,由于直接插入排序算法利用了有序表的插入操作，故顺序查找操作可以替换为折半查找操作。,例，序列 49 38 65 97 76 13 27,设已形成有序表 38 49 65 97 76 ,插入元素 13,折半插入排序,算法: void BinaryInsertSort(ElemType R,int n) for(int i=1; i=left;j-)Rj+1=Rj; /元素后移空出插入位Rleft=temp; ,折半插入效率分析,二分插入算法与直接插入算法相比， 需要辅助空间与直接插入排序基本一致； 时间上，前者的比较次数比直接插入查找的最坏情况好，最好的情况坏， 两种方法的元素的移
6、动次数相同， 因此二分插入排序的时间复杂度仍为O(n2)。 二分插入算法与直接插入算法的元素移动一样是顺序的，因此该方法也是稳定的。,分析直接插入排序,1. 若待排序记录序列按关键字基本有序，则排序效率可大大提高；,2. 待排序记录总数越少，排序效率越高；,希尔(shell)排序,思想:,先将待排序记录序列分割成为若干子序列分别进行直接插入排序；,待整个序列中的记录基本有序后，再全体进行一次直接插入排序。,例，序列 49 38 65 97 76 13 27 48 55 4 19,第一趟排序,13 19 49,27 38,48 65,55 97,4 76,第二趟排序,13 38 55 76,4
7、27 49 65,19 48 97,第三趟排序,4 13 19 27 38 48 49 55 65 76 97,希尔排序的算法template void ShellSort (T Vector, int arrSize ) T temp;int gap = arrSize / 2; /gap是子序列间隔 while ( gap != 0 ) /循环,直到gap为零for ( int i = gap; i = gap; j -= gap )if ( temp Vectorj-gap )Vectorj = Vectorj-gap;else break; Vectorj = temp; gap =
8、( int ) ( gap / 2 ); ,希尔排序效率分析,希尔排序的时间复杂性在O（nlog2n）和O（n2 ）之间，大致为O（n1.3）。,思想: 通过不断比较相邻元素大小，进行交换来实现排序。,首先将第一个元素与第二个元素比较大小，若为逆序，则交换；,然后比较第二个元素与第三个元素的大小，若为逆序，则交换；,. . .,直至比较第 n-1 个元素与第 n 个元素的大小，若为逆序，则交换；,第一趟排序:,结果:,关键字最大的记录被交换至最后一个元素位置上。,交换排序冒泡排序,例，序列 49 38 76 13 27,38 49 13 27,初始,第一趟排序后,最大值,次大值,第二趟排序后,
9、38 13 27,13 27,第三趟排序后,第四趟排序后,冒泡排序的算法实现。 void Bubblesort(ElemType R,int n) int flag=1; /当flag为0则停止排序for (int i=1; i=i; j-) if (RjRj-1) /发生逆序 ElemType t=Rj;Rj=Rj-1;Rj-1=t;flag=1; /交换，并标记发生了交换if(flag=0)return; ,冒泡排序的效率分析从冒泡排序的算法可以看出，若待排序的元素为正序，则只需进行一趟排序，比较次数为（n-1）次，移动元素次数为0；若待排序的元素为逆序，则需进行n-1趟排序，比较次数为(
10、n2-n)/2，移动次数为3(n2-n )/2，因此冒泡排序算法的时间复杂度为O（n2）。由于其中的元素移动较多，所以属于内排序中速度较慢的一种。 因为冒泡排序算法只进行元素间的顺序移动，所以是一个稳定的算法。,冒泡排序的一种改进算法。,思想:,以首记录作为轴记录，从前、后双向扫描序列，通过交换，实现大值记录后移，小值记录前移，最终将轴记录安置在一个适当的位置。(小值记录在前、大值记录在后),轴记录将原序列分割成两部分，依次对前后两部分重新设定轴记录，继而分别再进行快速排序。,直至整个序列有序。,交换排序快速排序,快排序（Quick Sort),快速排序实例,快排序算法思想,快排序（Quick
11、 Sort),快排序-分割过程 快排序是一个分治算法（也是第一个） 快排序的关键过程是每次递归的分割过程 分割问题描述：对一个序列，取它的一个元素作为轴，把所有小于轴的元素放在它的左边，大于它的元素放在它的右边 分割算法： 用临时变量对轴备份 取两个指针low和high，它们的初始值就是序列的两端下标，在整个过程中保证low不大于high 移动两个指针 首先从high所指的位置向左搜索，找到第一个小于轴的元素, 把这个元素放在low的位置 再从low开始向右，找到第一个大于轴的元素，把它放在high的位置,快排序（Quick Sort),快排序-分割过程 分割算法： 重复上述过程，直到low=
12、high， 把轴放在low所指的位置 这样所有大于轴的元素被放在右边，所有小于轴的元素被放在左边,快排序（Quick Sort),快排序-分割过程,38 65 97 76 13 27 49,49,low,high,pivot = 49,0 1 2 3 4 5 6 7,high,38 65 97 76 13 49,27,low,27 38 97 76 13 49,65,high,27 38 97 76 65 49,13,low,27 38 13 76 65 49,97,high,49,快排序（Quick Sort),快排序-分割过程 int Partition(T Array, int low,
13、 int high)T pivot = Arraylow;/ while(low = pivot)high -;Arraylow = Arrayhigh;while(low high ,快排序（Quick Sort),快排序-算法快排序算法是个递归地对序列进行分割的过程，递归终止的条件是最终序列长度为1,0 1 2 3 4 5 6 7,49 38 65 97 76 13 27 49,76 97 65 49,27 38 13,49,49,13,38,27,49 65,97,76,13 17 38 49 76 97,49 65,快排序（Quick Sort),快排序-算法 void QuickSort(T Array, int low, int high)int PivotLocation;if(low high)PivotLocation = Partition(Array, low, high);QuickSort(Array, low, PivotLocation-1);QuickSort(Array, PivotLocation+1, high); ,
