第十章排序 10.1排序的基本概念 10.2简单排序方法（复杂度0(n2) 10.3先进排序方法（复杂度O(nLogn)/O(n32) 10.4基数排序（复杂度O(d×n)) 10.5各种排序的综合比较 ypb@ustc.edu.cn 中国科学技术大学
ypb@ustc.edu.cn 1 中国科学技术大学 第十章 排序 10.1排序的基本概念 10.2简单排序方法（复杂度O(n2)） 10.3先进排序方法（复杂度 O(nLogn) /O(n3/2 )） 10.4基数排序（复杂度 O(d×n)） 10.5各种排序的综合比较
10.1排序的基本概念 ©排序单元结构定义 typedef int KeyType; /简单起见，只要可比就可以 typedef struct{ KeyType key, InfoType otherinfo: }RcdType; g例： Typedef struct{ char name[10]; char sex[2]; char birthday[8]; char department[4]; InfoType ypb@ustc.edu.cn 2 中国科学技术大学
ypb@ustc.edu.cn 2 中国科学技术大学 10.1排序的基本概念 排序单元结构定义 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
S 排序 设N个记录{红1,2…rn},相应关键字{k1,k2k} 求一种排列p1,P2…Pn,使得kp1kp2≤km 即{红p1,rp2…pm}是按关键字有序序列 。稳定与不稳定排序 若k=k,并且在待排序列中r领先于r(即is),若排序后的序列中r仍 然领先，则称该排序方法稳定。 ©内部排序与外部排序 内部排序：仅在内部存储器中完成的排序 外部排序：在排序中需要访问外部存储器的排序 g本章排序操作对象：Typedef struct{ RcdType r[MAXSIZE+1]; Int length; }Sqlist; ypb@ustc.edu.cn 3 中国科学技术大学
ypb@ustc.edu.cn 3 中国科学技术大学 排序 设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;
10.2简单排序方法（复杂度0n2) 10.2.1选择排序 void SelectPass(Sqlist&L,inti)复杂度On) void SelectSort(Sqlist&L)复杂度O(n) -n(n+1)/2次比较和3（n-1)次交换。 -本身是稳定算法，本例由交换引起不稳定，可采 用移动策略获稳定算法 R[i] R[j] 有序序列R[1i-1] 无序序列R[n 有序序列R[1.i门 无序序列R[+l.n ypb@ustc.edu.cn 4 中国科学技术大学
ypb@ustc.edu.cn 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]
选择排序（一趟） 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 (il=j) W=L.r[il;L.r[il=L.r[il;L.r[il=W; }I∥SelectPass ypb@ustc.edu.cn 5 中国科学技术大学
ypb@ustc.edu.cn 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
选择排序 void SelectSort (SqList &L) 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 (il=j){W=L.r[j];L.r[j]=L.r[i];L.r[i]=W;) } },∥SelectSort ypb@ustc.edu.cn 6 中国科学技术大学
ypb@ustc.edu.cn 6 中国科学技术大学 选择排序 void SelectSort (SqList &L) { 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
10.2.2插入排序 void InsertPass(Sqlist&L,inti)复杂度0(n) void InsertSort(Sqlist&L)复杂度0(n2) 数据的有序性影响算法最差比较移动(n+4)(n-1)/2 -是稳定排序 R[的 有序序列R[1.i-1 无序序列Ri.n 有序序列R[1.i 无序序列R[+1.n] ypb@ustc.edu.cn 中国科学技术大学
ypb@ustc.edu.cn 7 中国科学技术大学 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] 10.2.2插入排序
插入排序（一趟） void InsertPass(SqList &L,int i ) L.r[0]=L.r[, 川复制为哨兵 for (j=i-1;L.r[0].key L.r[j].key;--j) L.r[j+1]=L.r[jl; ∥记录后移 L.rj+1]=L.[0] ∥插入到正确位置 }/∥InsertPass ypb@ustc.edu.cn 8 中国科学技术大学
ypb@ustc.edu.cn 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
插入排序 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[; ∥复制为哨兵 for (j=i-1;L.r[0].key L.r[j].key;-j) L.r[j+1]=L.r[i]; ∥记录后移 L.r[j+1]=L.r[0]; ∥插入到正确位置 }∥if }/∥InsertSort ypb@ustc.edu.cn 9 中国科学技术大学
ypb@ustc.edu.cn 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
其他插入排序 折半插入： 插入时因为有序区可以使用折半查找，从而提 高插入速度 2路插入： 一为了减少移动，分两个半区插入，可以和折半一起 使用 表插入： 一通过静态链表形式存储数据元素，通过修改指针 的方式避免元素的移动，不可以使用折半插入。 ypb@ustc.edu.cn 10 中国科学技术大学
ypb@ustc.edu.cn 10 中国科学技术大学 其他插入排序 折半插入： – 插入时因为有序区可以使用折半查找，从而提 高插入速度 2路插入： – 为了减少移动，分两个半区插入,可以和折半一起 使用 表插入： – 通过静态链表形式存储数据元素，通过修改指针 的方式避免元素的移动，不可以使用折半插入