第九章 排序 9.1排序的基本概念 9.2简单排序方法（复杂度 O(n2)） 9.3先进排序方法（复杂度 O(nLogn)）

Presentation on theme: "第九章 排序 9.1排序的基本概念 9.2简单排序方法（复杂度 O(n2)） 9.3先进排序方法（复杂度 O(nLogn)）"— Presentation transcript:

1 第九章 排序 9.1排序的基本概念 9.2简单排序方法（复杂度 O(n2)） 9.3先进排序方法（复杂度 O(nLogn)）
9.4基数排序（复杂度 O(d×n)） 9.5各种排序的综合比较

2 9.1排序的基本概念 排序单元结构定义 例： Typedef struct { char name[10]; char sex[2];
typedef int KeyType; //简单起见，只要可比就可以 typedef struct{ KeyType key; InfoType otherinfo; }RcdType; 例： Typedef struct { char name[10]; char sex[2]; char birthday[8]; char department[4]; }InfoType

3 Typedef struct{ RcdType r[MAXSIZE+1]; Int length; }Sqlist; 排序 稳定与不稳定排序
设N个记录 {r1,r2…rn}， 相应关键字{k1,k2…kn} 求一种排列p1,p2…pn，使得kp1≤kp2≤…≤kpn 即{rp1,rp2…rpn}是按关键字有序序列 稳定与不稳定排序 若ki=kj,并且在待排序列中ri领先于rj (即i<j),若排序后的序列中ri仍然领先 rj，则称该排序方法稳定。 内部排序与外部排序 内部排序：仅在内部存储器中完成的排序 外部排序：在排序中需要访问外部存储器的排序 本章排序操作对象： Typedef struct{ RcdType r[MAXSIZE+1]; Int length; }Sqlist;

4 9.2简单排序方法（复杂度 O(n2)） 9.2.1选择排序 void SelectPass（Sqlist &L,int i）复杂度 O(n) void SelectSort（Sqlist &L）复杂度 O(n2) n(n＋1)/2次比较和3（n-1）次交换。 本身是稳定算法，本例由交换引起不稳定，可采用移动策略获稳定算法 R[i] R[j] 有序序列R[1..i-1] 无序序列R[i..n] 有序序列R[1..i] 无序序列R[i+1..n]

5 选择排序(一趟) void SelectPass( SqList &L, int i ) { RcdType W； j = i；
for ( k=i+1; k<=L.length; k++ ) if ( L.r[k].key < L.r[j].key ) j = k ； if ( i != j ) { W=L.r[j]；L.r[j] =L.r[i]；L.r[i] = W；} } // SelectPass

6 选择排序 void SelectSort (SqList &L) { for (i=1; i<L.length; ++i) {
RcdType W； for (i=1; i<L.length; ++i) { j = i； for ( k=i+1; k<=L.length; k++ ) if ( L.r[k].key < L.r[j].key ) j =k ； if ( i!=j ) { W=L.r[j];L.r[j] =L.r[i];L.r[i] = W;} } } // SelectSort

7 9.2.2插入排序 数据的有序性影响算法 最差比较移动 (n+4)(n-1)/2 是稳定排序 R[i]
void InsertPass(Sqlist &L,int i)复杂度 O(n) void InsertSort(Sqlist &L) 复杂度 O(n2) 数据的有序性影响算法 最差比较移动 (n+4)(n-1)/2 是稳定排序 R[i] 有序序列R[1..i-1] 无序序列R[i..n] 有序序列R[1..i] 无序序列R[i+1..n]

8 插入排序(一趟) void InsertPass( SqList &L, int i ) {
L.r[0] = L.r[i]; // 复制为哨兵 for ( j=i-1; L.r[0].key < L.r[j].key; --j ) L.r[j+1] = L.r[j]; // 记录后移 L.r[j+1] = L.r[0]; // 插入到正确位置 } // InsertPass

9 插入排序 void InsertSort ( SqList &L) { // 对顺序表L作插入排序
for ( i=2; i<=L.length; ++i ) if ( L.r[i].key < L.r[i-1].key ) L.r[0] = L.r[i]; // 复制为哨兵 for ( j=i-1; L.r[0].key < L.r[j].key; --j ) L.r[j+1] = L.r[j]; // 记录后移 L.r[j+1] = L.r[0]; // 插入到正确位置 } // if } // InsertSort

10 9.2.3起泡排序 有序序列的比较次数是n-1次 逆序序列的比较次数是 n(n-1)/2；移动次数3n(n-1)/2 是稳定排序 R[i]
void BubbleSort（Sqlist &L）复杂度 O(n2) 有序序列的比较次数是n-1次 逆序序列的比较次数是 n(n-1)/2；移动次数3n(n-1)/2 是稳定排序 R[i] 有序序列R[i+1..n] 无序序列R[1..i] 有序序列R[i..n] 无序序列R[1..i-1]

11 起泡排序 void BubbleSort( SqList &L ){ i = L.length; while (i >1) {
lastExchangeIndex = 1; for (j = 1; j < i; j++){ if (L.r[j+1].key < L.r[j].key) { W=L.r[j]；L.r[j] =L.r[j+1]；L.r[j+1] = W； lastExchangeIndex = j; } //if } //for i = lastExchangeIndex; } // while } // BubbleSort

12 9.3先进排序方法（复杂度 O(nLogn)） 9.3.1快速排序 void Partition 一趟快速排序（分割）
void Qsort（RcdType R[],int s,int t）递归函数 void QuickSort（SqList &L）快速排序 时间复杂度 O(nLogn) 最坏情况有序O(n2) 空间复杂度 O(n) 改进：取中原则：R[s],R[t],R[(s+t)/2]

13 快速排序(分割) int Partition ( RcdType R[], int low, int high) {
R[0] = R[low]; // 将枢轴记录移至数组的闲置分量 pivotkey = R[low].key; // 枢轴记录关键字 while (low<high) { // 从表的两端交替地向中间扫描 while(low<high&& R[high].key>=pivotkey) --high; R[low++] = R[high]; // 将比枢轴记录小的记录移到低端 while (low<high && R[low].key<=pivotkey) ++low; R[high--] = R[low]; // 将比枢轴记录大的记录移到高端 } //while R[low] = R[0]; // 枢轴记录移到正确位置 return low; // 返回枢轴位置 } // Partition

14 快速排序 void QSort (RedType R[], int s, int t ) { // 对记录序列R[s..t]进行快速排序
if (s < t-1) { // 长度大于1 pivotloc = Partition(R, s, t);// 对 R[s..t] QSort(R, s, pivotloc-1); // 对低子序列递归排序 QSort(R, pivotloc+1, t); // 对高子序列递归排序 } // if } // Qsort void QuickSort( SqList & L) { QSort(L.r, 1, L.length); } // QuickSort

15 9.3.2归并排序 void Merge (RcdType SR[], RcdType TR[], int i, int m, int n)
void Msort ( RcdType SR[], RcdType TR1[], int s, int t ) 递归函数 void MergeSort（SqList &L）快速排序 时间复杂度 O(nLogn) 空间复杂度 O(n)

16 归并排序(一趟) void Merge (RcdType SR[], RcdType TR[], int i, int m, int n) { // 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] for (j=m+1, k=i; i<=m && j<=n; ++k) { if (SR[i].key<=SR[j].key) TR[k] = SR[i++]; else TR[k] = SR[j++]; } while (i<=m) TR[k++] = SR[i++]; while (j<=n) TR[k++] = SR[j++]; } // Merge

17 归并排序 void Msort ( RcdType SR[], RcdType TR1[], int s, int t ) {
// 对SR[s..t]进行归并排序，排序后的记录存入TR1[s..t]。 RcdType TR2[t-s+1]; if (s==t) TR1[s] = SR[s]; else { m = (s+t)/2; Msort (SR, TR2, s, m); Msort (SR, TR2, m+1, t); Merge (TR2, TR1, s, m, t); } // else } // MSort void MergeSort (SqList &L) { MSort(L.r, L.r, 1, L.length); } // MergeSort

18 2路归并排序程序 1）一趟排序 void mergepass(RcdType SR[],RcdType TR[],int s,int n){
while(i+2s-1<=n) { merge(SR,TR,i,i+s-1,i+2*s-1); i +=2*s; } if(i+s-1<n) //最后还有两个集合，但不等长 merge(SR,TR,i,i+s-1,n); else //最后还有一个集合 while(i<＝n){TR[i]=SR[i];i++};

19 2路归并排序程序（2） 2） 2路归并 void mergesort((Sqlist &L){
RcdType TR[L.length+1]; s=1; while（s<n）{ mergepass(L.r,TR,s,n); s*=2; mergepass(TR,L.r,s,n); s*=2; }

20 9.3.3堆排序 小顶堆: ri<r2i; ri<r2i+1 大顶堆 :ri>r2i, ri>r2i+1
时间复杂度 O(nLogn)  空间复杂度 O(1)

21 9.4基数排序（复杂度 O(d×n)） 逻辑关键字、关键字，关键字分级 对于有d个关键字的记录排序，要进行d趟分配和收集
时间复杂度 O(n×d); 空间复杂度 O(n)

22 9.5各种排序的综合比较 选择排序方法考虑因素 待排序记录数n 记录本身其他信息量大小 关键字分布情况 稳定性要求 时间性能
按时间性能分三类 :简单、先进、基数 有序性对算法的影响 插入和起泡有好的影响O（n） 快速有坏的影响O(n2) 选择、归并、堆、基数没有影响 记录其他信息复杂度对算法的影响 起泡、快速、堆等移动较多的算法影响较大

23 空间性能 稳定性 例：（4，3，4，2）进行快速排序不稳定 所有简单排序、堆是O（1） 快速是O（Logn） 归并、基数O(n)
快速和堆大范围交换的算法不稳定 其他算法均稳定。 例：（4，3，4，2）进行快速排序不稳定

24 各种排序的综合比较表 选择 O(n2) O(1) Y 无 插入 O(n) 好 起泡 快速 O(nLogn) O(Logn) N 坏 归并 堆
算法 平均时间 最坏情况 最好情况 辅助空间 稳定性 有序性影响 选择 O(n2) O(1) Y 无 插入 O(n) 好 起泡 快速 O(nLogn) O(Logn) N 坏 归并 堆 基数 O(n*d)