第十章 排序 10.1排序的基本概念 10.2简单排序方法（复杂度 O(n2)）

Presentation on theme: "第十章 排序 10.1排序的基本概念 10.2简单排序方法（复杂度 O(n2)）"— Presentation transcript:

1 第十章 排序 10.1排序的基本概念 10.2简单排序方法（复杂度 O(n2)）
10.3先进排序方法（复杂度 O(nLogn) /O(n3/2)） 10.4基数排序（复杂度 O(d×n)） 10.5各种排序的综合比较

2 10.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 10.2简单排序方法（复杂度 O(n2)） 10.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； //j为最小值位置 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 10.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 其他插入排序 折半插入： 2路插入： 表插入： 插入时因为有序区可以使用折半查找，从而提 高插入速度
为了减少移动，分两个半区插入,可以和折半一起使用 表插入： 通过静态链表形式存储数据元素，通过修改指针的方式避免元素的移动，不可以使用折半插入。

11 10.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]

12 起泡排序 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

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

14 快速排序(分割) 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

15 快速排序 void QSort (RedType R[], int s, int t ) { // 对记录序列R[s..t]进行快速排序
if (s < t) { // 长度大于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

16 10.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)

17 归并排序(一趟) void Merge (RcdType SR[], RcdType TR[], int l, int m, int n) { // 将有序的SR[l..m]和SR[m+1..n]归并为有序的TR[l..n] for (i=l,j=m+1, k=l; 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

18 归并排序 void Msort ( RcdType SR[], RcdType TR1[], int s, int t ) {
// 对SR[s..t]进行归并排序，排序后的记录存入TR1[s..t]。 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

19 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++};

20 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; }

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

22 void HeapAdjust(HeapType &H, int s, int m) { // 算法10.10
// 已知H.r[s..m]中记录的关键字除H.r[s] 之外均满足堆的定义， rc = H.r[s]; for (j=2*s; j<=m; j*=2) { // 沿key较大的孩子结点向下筛选 if (j<m && H.r[j].key<H.r[j+1].key) ++j; // j为key较大的记录的下标 if (rc.key >= H.r[j].key) break; // rc应插入在位置s上 H.r[s] = H.r[j]; s = j; }//for H.r[s] = rc; // 插入 } // HeapAdjust void HeapSort(HeapType &H) { for (i=H.length/2; i>0; --i) HeapAdjust ( H, i, H.length ); for (i=H.length; i>1; --i) {H.r[i] ↔ H.r[1] HeapAdjust(H, 1, i-1); } } // HeapSort

23 10.3.4希尔排序 又称“缩小增量排序” 初始： └───────────┘ └──────────┘ 一趟排序: └──────┴──────┴──────┘ └──────┴──────┘ 二趟排序： 三趟排序：

24 希尔排序 能用哨卡吗？ void ShellInsert(SqList &L, int dk) {
for (i=dk+1; i<=L.length; i++) //逐个间隔插入，不分子集 if (LT(L.r[i].key, L.r[i-dk].key)) { for (j=i-dk; j>0 && LT(L.r[j+dk].key, L.r[j].key); j-=dk) L.r[j+dk] = L.r[j]; // 记录后移，查找插入位置 L.r[j+dk] = L.r[0]; // 插入 } } // ShellInsert void ShellSort(SqList &L, int dlta[], int t) { for (int k=0; k<t; ++k) ShellInsert(L, dlta[k]); // 一趟增量为dlta[k]的插入排序 } // ShellSort 能用哨卡吗？

25 10.3.5树形选择排序 13 38 65 27 49 97 76 27 38 65 76 49 97 ∞ 38 49 65 76 97 ∞ 49 65 76 ∞ 97

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

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

28 空间性能 稳定性 例：（4，3，4，2）进行快速排序不稳定 经过一趟排序能将一个数据放在最终位置 所有简单排序、堆是O（1）
快速是O（Logn） 归并、基数O(n) 稳定性 快速和堆大范围交换的算法不稳定 其他算法均稳定。 例：（4，3，4，2）进行快速排序不稳定 经过一趟排序能将一个数据放在最终位置 选择、起泡、堆

29 排序的另一种分类 选择排序： 交换排序： 插入排序： 归并排序 基数排序 简单选择、树形选择、堆排序 起泡排序、快速排序
简单插入、折半插入、表插入、希尔排序 归并排序 基数排序

30 各种排序的综合比较表 选择 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)