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

第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 …… 此处隐藏：1954字，全部文档内容请下载后查看。喜欢就下载吧 ……