第九章 排序 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 len; }SqTable; 排序 稳定与不稳定排序
设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 len; }SqTable;

4 9.2简单排序方法（复杂度 O(n2)） 9.2.1选择排序 void SelectPass（SqTable &L,int i）复杂度 O(n) void SelectSort（SqTable &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(SqTable &L, int i ) { RcdType W；
j = i； //j为最小值位置 for ( k=i+1; k<=L.len; 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 (SqTable &L) { for (i=1; i<L.len; ++i) {
RcdType W； for (i=1; i<L.len; ++i) { j = i； for ( k=i+1; k<=L.len; 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 SelectPass

7 9.2.2起泡排序 有序序列的比较次数是n-1次 逆序序列的比较次数是 n(n-1)/2；移动次数3n(n-1)/2 是稳定排序 R[i]
void BubbleSort（SqTable &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]

8 起泡排序 void BubbleSort(SqTable &L ){ i = L.len; 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

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

10 插入排序(一趟) void InsertPass(SqTable &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

11 插入排序 void InsertSort (SqTable &L) { // 对顺序表L作插入排序
for ( i=2; i<=L.len; ++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 InsertPass

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

13 希尔排序(1) 若元素数为n=2k, 增量(子表数量)为2k-1, 2k-2, …,2,1
void ShlSort(SqTable &L) // 对顺序表进行Shell排序 { n=L.Len; for (i = n/2；i > 2；i /= 2) // 增量n/2、n/4、… for (j = 1；j <= i；j++) // 对i个子表排序 InsSort2(&L.r[j]，n+1-j，i)； InsSort2(&L.r[1]，n，1)； } void InsSort2(RcdType A[], int n，int incr) for(i = incr；i <= n；i += incr) for(j = i；(j > =incr) && (A[j].key < A[j-incr].key)；j -= incr) swap(A[j]，A[j-incr])； 若元素数为n=2k, 增量(子表数量)为2k-1, 2k-2, …,2,1 第二个元素

14 希尔排序(2) ak+1=3ak+1 void ShellSort(SqTable &L, int dlta[], int t) {
for (int k=0; k<t; ++k) //dlta[]={121,40,13,4,1}等 ShellInsert(L, dlta[k]); // 一趟增量为dlta[k]的插入排序 } // ShellSort void ShellInsert(SqTable &L, int dk) { for (i=dk+1; i<=L.len; i++) if (L.r[i].key < L.r[i-dk].key) { L.r[0] = L.r[i]; // 暂存在L.r[0] for (j=i-dk; j>0 && L.r[0].key < L.r[j].key; j-=dk) L.r[j+dk] = L.r[j]; // 交换位置 L.r[j+dk] = L.r[0]; // 插入 } } // ShellInsert

15 void ShellSort(SqTable &L, int dlta[], int t) {
for (int k=0; k<t; ++k) //dlta[]={121,40,13,4,1}等 ShellInsert(L, dlta[k]); // 一趟增量为dlta[k]的插入排序 } // ShellSort void ShellInsert(SqTable &L, int dk) { for (i=dk+1; i<=L.len; i++) //逐个间隔插入，不分子集 if (L.r[i].key < L.r[i-dk].key) { L.r[0] = L.r[i]; // 暂存在L.r[0] for (j=i-dk; j>0 && 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

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

17 快速排序(分割1) 为什么是l？ 还可以怎么做？ 例待排序列：72 6 57 88 60 42 83 73 48 85
int partition(SqTable &L，int i，int r，KeyType pivot) { l=i-1; do { while (L.r[++l].key < pivot)； // 从左移到右 while (r>i && L.r[--r].key > pivot)); // 从右移到左 删= swap（L.r[l]，L.r[r])； } while (l < r )； //由于循环中当l=r+1时才会停止且发生了多余交换 //故应该换回来 swap(L.r[l]，L.r[r])； return l； } 为什么是l？ 还可以怎么做？ 例待排序列：

18 初始状态 l r 移动指针 l r 第一次交换 移动指针 l r 第二次交换 移动指针 r l 第三次交换 翻转交换 | 快速排序的分割步骤

19 快速排序1 void QuiSort(SqTable &L，int i，int j) {// 对顺序表进行快速排序
pivotIndex = FindPivot(L，i，j) // i、j为子序列左右两端的下标 swap(L.r[pivotIndex]，L.r[j])； // 置轴点到末端 k = partition(L，i，j，L.r[j].key)； swap(L.r[k]，L.r[j])； // 置轴点位置 if ((k - i) > 1) QuiSort(L，i，k-1)； // 左分区排序 if ((j - k) > 1) QuiSort(L，k+1，j)； // 右分区排序 }

20 72

21 快速排序(分割2) int Partition2 ( 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; if(low<high)R[low++] = R[high]; // 将比枢轴小的记录移到低端 while (low<high && R[low].key<=pivotkey) ++low; if(low<high)R[high--] = R[low]; // 将比枢轴大的记录移到高端 } //while R[low] = R[0]; // 枢轴记录移到正确位置 return low; // 返回枢轴位置 } // Partition2

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

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

24 void HeapAdjust(HeapType &H, int s, int m)
{// 已知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.len/2; i>0; --i) HeapAdjust ( H, i, H.len ); for (i=H.len; i>1; --i) {H.r[i] ↔ H.r[1] HeapAdjust(H, 1, i-1); } } // HeapSort

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

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

27 归并排序（递归） void Msort ( RcdType Rs[], RcdType Rt[], int s, int t ) {
// 对Rs[s..t]进行归并排序，排序后的记录存入Rt[s..t]。 RcdType Rtmp[t-s+1]; if (s==t) {Rt[s] = Rs[s];return;} m = (s+t)/2; Msort (Rs, Rtmp, s, m); Msort (Rs, Rtmp, m+1, t); Merge (Rtmp, Rt, s, m, t); } // MSort void MergeSort (SqTable &L) { MSort(L.r, L.r, 1, L.len); } // MergeSort

28 2路归并

29 2路归并排序程序 一趟排序 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++};

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

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

32

33 typedef struct{ KeyType keys[D]; //keys[0..D-1],0位最高 InfoType otherinfo; }RcdType; //重新定义RcdType void RadPass(RcdType R[],RcdType T[],int n,int k) {//对R[]的元素按关键字的第k项做一趟的分配和收集,k取0..D-1 //结果放置在T[]中 for(j=0;j<R;j++)count[j]=0; //初始化统计数组 for(j=1;j<=n;j++)count[R[j].keys[k]]++;//统计数组 for(j=1;j<R;j++)count[j]=count[j-1]+count[j]; for(j=n;j>=1;j--){ p=R[j].keys[k]; //当前元素k项关键字内容 T[count[p]]=R[j]; //放置R[j]到T[p] count[p]--; } }//void RadPass

34 void RadSort(SqTable &L)
{//对序列L.r[1..Len]进行基数排序 RcdType T[L.Len+1]; //辅助数组 k=D-1; //k取最低位项关键字 while(k>=0){ RadPass(L.r,T,L.Len,k); k--; if(k>=0){ RadPass(T,L.r,L.Len,k); k--; }else //D为奇数时，需要把数据复制为L。 for(j=1;j<=L.Len;j++)L.r[j]=T[j]; }//while }//RadSort

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

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

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