第8章排序 8.1排序的基本概念 8.2简单排序 8.3希尔排序 8.4快速排序 8.5堆排序 8.6归并排序 8.7基数排序 ypb@ustc.edu.cn 中国科学技术大学
ypb@ustc.edu.cn 1 中国科学技术大学 第8章 排序 8.1排序的基本概念 8.2简单排序 8.3希尔排序 8.4快速排序 8.5堆排序 8.6归并排序 8.7基数排序
8.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 中国科学技术大学
ypb@ustc.edu.cn 2 中国科学技术大学 8.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
排序 设N个记录{红1,2…In},相应关键字{k1,k2…kn} 求一种排列p1,P2…pn,使得kpp2≤≤km 即{红p1,p2…pm}是按关键字有序序列 o i 稳定与不稳定排序 若k=k,并且在待排序列中r领先于r(即s),若排序后的序列中r仍 然领先[，则称该排序方法稳定 ©内部排序与外部排序 内部排序：仅在内部存储器中完成的排序 外部排序：在排序中需要访问外部存储器的排序 g本章排序操作对象：Typedef struct{ RcdType r[MAXSIZE+1]; Int len; }SqTable; 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 len; }SqTable;
8.2简单排序方法（复杂度0n2) >选择排序 void SelectPass(SqTable&L,inti)复杂度On) void SelectSort(SqTable&L)复杂度O(n2) -nn+1)/2次比较和3（n-1)次交换。 本身是稳定算法，本例由交换引起不稳定，可采 - 用移动策略获稳定算法 [i] R[j] 有序序列R[1.i-1] 无序序列R[i.n 有序序列R[1.i门 无序序列R+1.n ypb@ustc.edu.cn 中国科学技术大学
ypb@ustc.edu.cn 4 中国科学技术大学 8.2简单排序方法（复杂度 O(n2 )） ➢ 选择排序 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]
选择排序（一趟） void SelectPass(SqTable &L,int i RcdType W; 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[il;L.r[il=L.r[il;L.r[il=W; }l∥SelectPass ypb@ustc.edu.cn 5 中国科学技术大学
ypb@ustc.edu.cn 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