常用排序算法总结——数据结构

第9章 排序

排序{ R1 , R2 , R3 , . . . , Rn } { K 1 , K2 , K 3 , . . . , Kn }

设 n 个记录的序列为 其相应的关键字序列为

若规定 1 , 2 , 3 , . . . , n 的一个排列 p1 , p2 , p3 , . . . , pn , 使得相应的关键字满足如下非递减关系: Kp ≤ K p ≤ K p ≤ . . . ≤ Kp1 2 3 n

则原序列变为一个按关键字有序的序列: { Rp , Rp , Rp , . . . , Rp }1 2 3n

此操作过程称为排序。

第9章 排序

稳定排序与不稳定排序

假设 Ki = Kj ,且排序前序列中 Ri 领先于 Rj ; 若在排序后的序列中 Ri 仍领先于 Rj ,则称排序方法是 稳定的。 若在排序后的序列中 Rj 仍领先于 Ri ,则称排序方法是 不稳定的。 例，序列 3 15 8 8 6 9

若排序后得 3若排序后得 3

66

88

88

99

1515

稳定的不稳定的

第9章 排序

内部排序与外部排序

内部排序: 指的是待排序记录存放在计算机随机存储 器中进行的排序过程。 外部排序: 指的是待排序记录的数量很大，以致内存 一次不能容纳全部记录，在排序过程中尚需对外存进 行访问的排序过程。

第9章 排序

排序的时间复杂性

排序过程主要是对记录的排序码进行比较和记录的移动过 程。因此排序的时间复杂性可以算法执行中的数据比较次 数及数据移动次数来衡量。当一种排序方法使排序过程在 最坏或平均情况下所进行的比较和移动次数越少，则认为 该方法的时间复杂性就越好，分析一种排序方法，不仅要 分析它的时间复杂性，而且要分析它的空间复杂性、稳定 性和简单性等。

第9章 排序

内部排序 插入排序 交换排序(快速排序) 选择排序 归并排序 基数排序 二叉排序树排序

按照排序过程中所依据的原则的不同可以分类为:

第9章 排序

插入排序——直接插入排序

思想: 利用有序表的插入操作进行排序 有序表的插入: 将一个记录插入到已排好序的有序表中， 从而得到一个新的有序表。 例，序列 13 27 插入 13 27 38 49 38 49 65 76 97 65 76 97

第9章 排序

直接插入排序算法描述初始，令第 1 个元素作为初始有序表；

依次插入第 2 , 3 , …, k 个元素构造新的有序表；直至最后一个元素； 例，序列 49 38 65 97 76 13 27

初始，S = { 49 } ;

{{13 49 } 65 } 49 } 65 } 76 } 97 } { 38 27 38 65 76 97 38 49 49 76 97 13 38 65 97直接插入排序算法主要应用比较和移动两种操作。

第9章 排序

void insertsort(ElemType R[],int n)//待排序元素用一个数组R表示，数组有n个元素 { for ( int i=1; i<n; i++) //i表示插入次数，共进行n-1次 插入 { ElemType temp=R[i]; //把待排序元素赋给temp int j=i-1; while ((j>=0)&& (temp<R[j])) { R[j+1]=R[j]; j--; } // 顺序比较和移动

R[j+1]=temp;}}

直接插入排序的效率分析 第9章 排序 从空间来看

,它只需要一个元素的辅助空间，用于元素 的位置交换。 从时间分析，首先外层循环要进行n-1次插入，每次插入 最少比较一次(正序),移动两次；最多比较i次，移动 i+2次(逆序)(i=1,2,…,n-1)。 Cmin=n-1 M min=2(n-1)

Cmax=1+2+…+n-1=(n2-n)/2M max=3+4+…+n+1=(n2+3n-4)/2 Cave=(n2+n-2)/4 M max=(n2+7n-8)/4 因此，直接插入排序的时间复杂度为O(n2)。 直接插入算法的元素移动是顺序的，该方法是稳定的。

第9章 排序

折半插入排序由于直接插入排序算法利用了有序表的插入操作， 故顺序查找操作可以替换为折半查找操作。 例，序列 49 38 65 97 76 13 27

设已形成有序表 { 38 49 65 97 76 } 插入元素 13

第9章 排序 算法: void BinaryInsertSort(ElemType R[],int n) { for(int i=1; i<n; i++) //共进行n-1次插入

{{

int left=0,right=i-1;ElemType temp=R[i];while(left<=right) int middle=(left+right)/2; //取左区间 else left=middle+1; } //取右区间 for(int j=i-1;j>=left;j--) R[j+1]=R[j]; //元素后移空出插入位 R[left]=temp; } //取中点

if(temp<R[middle]) right=middle-1;

}

第9章 排序

折半插入效率分析

二分插入算法与直接插入算法相比， 需要辅助空间与直接插入排序基本一致； 时间上，前者的比较次数比直接插入查找的最坏情况 好，最好的情况坏， 两种方法的元素的移动次数相同， 因此二分插入排序的时间复杂度仍为O(n2)。 二分插入算法与直接插入算法的元素移动一样是顺序 的，因此该方法也是稳定的。

第9章 排序

希尔(shell)排序

分析直接插入排序

1. 若待排序记录序列按关键字基本有序，则排序效率可大大提高； 2. 待排序记录总数越少，排序效率越高；

第9章思想: 排序先将待排序记录序列分割成为若干子序列分别进行直接插入排序； 待整个序列中的记录基本有序后，再全体进行一次直接插入排序。

例，序列 49 38 65 97 76 13 27 48 55 4 19第一趟排序 49 38 65 97 76 13 27 48 55 4 19

13 27 48 55 4 19 38 65 97 76 49

第9章 排序第二趟排序

13 27 48 55 4 19 38 65 97 76 49 13 27 48 55 4 19 38 65 97 76 49

13 4 19 38 27 48 55 49 97 76 65 第三趟排序 4 13 19 27 38 48 49 55 65 76 97

第9章 排序 希尔排序的算法

template <class T > void ShellSort (T Vector[], int arrSize ) { T temp; int gap = arrSize / 2; //gap是子序列间隔 while ( gap != 0 ) { //循环,直到gap为零 for ( int i = gap; i < arrSize; i++) { temp = Vector[i]; //直接插入排序 for ( int j = i; j >= gap; j -= gap ) if ( temp < Vector[j-gap] ) Vector[j] = Vector[j-gap]; else break; Vector[j] = temp; } gap = ( int ) ( gap / 2 ); } }

第9章 排序

希尔排序效率分析

希尔排序的时间复杂性在O(nlog2n)和O(n2 )之间， 大致为O(n1.3)。

第9章 排序

交换排序——冒泡排序

思想:

通过不断比较相邻元素大小，进行交换来实现排序。

第一趟排序:首先将第一个元素与第二个元素比较大小，若为逆序，则交换； 然后比较第二个元素与第三个元素的大小，若为逆序，则交换；

直至比较第 n-1 个元素与第 n 个元素的大小，若为逆序，则交换；

...

结果:关键字最大的记录被交换至最后一个元素位置上。

第9章 排序

例，序列 49 38 76 13 27

38 49 初 始

38 13 49 13 27 49 49 27

13 38 38 13 27 27 38 次大值 第 三 趟 排 序 后

13

49 3876 13 13 76 27 27 76

27第 四 趟 排 序 后

最大值 第 二 趟 第 排 一 序 趟 后 排 序 后

冒泡排序的算法实现。 第9章 排序 void Bubblesort(ElemType R[],int n) { int flag=1; //当flag为0则停止排序 for (int i=1; i<n; i++)

{ //i表示趟数，最多n-1趟flag=0;//开始时元素未交换 for (int j=n-1; j>=i; j--)

if (R[j]<R[j-1])R[j]=R[j-1];

{ //发生逆序 ElemType t=R[j];

R[j-1]=t;flag=1; } //交换，并标记发生了交换 if(flag==0)return; } }

第9章 排序

冒泡排序的效率分析

从冒泡排序的算法可以看出，若待排序的元素为正序， 则只需进行一趟排序，比较次数为(n-1)次，移动元 素次数为0;若待排序的元素为逆序，则需进行n-1趟 排序，比较次数为(n2-n)/2,移动次数为3(n2-n )/2,因 此冒泡排序算法的时间复杂度为O(n2)。由于其中的 元素移动较多，所以属于内排序中速度较慢的一种。 因为冒泡排序算法只进行元素间的顺序移动，所以是 一个稳定的算法。

本文来源：https://www.bwwdw.com/article/hu64.html