第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 intKeyType,typedefstructkey,KeyTypeInfoTypeotherinfo,}RcdType;例：Typedef struct {char name[10];char sex[2];char birthday[8];char department[4];InfoTypeT2ypb@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个记录(r1,r...n），相应关键字(k,k2..k)求一种排列p1,P2...Pn，使得kp1≤kp2≤...≤kpn即(rp1,p2pn)是按关键字有序序列稳定与不稳定排序若k=k,并且在待排序列中r领先于r：（即i<i),若排序后的序列中r仍然领先Ii，则称该排序方法稳定。内部排序与外部排序内部排序：仅在内部存储器中完成的排序外部排序：在排序中需要访问外部存储器的排序本章排序操作对象：Typedef structRcdType r[MAXSIZE+1];Intlen;}SqTable;3中国科学技术大学ypb@ustc.edu.cn
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简单排序方法（复杂度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[i]有序序列R[1..i-1]无序序列R[i.n]有序序列R[1..i]无序序列R[i+1..n]4中国科学技术大学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;/i为最小值位置j=i;for (k=i+1; k<=L.len; k++ )if( L.r[k].key < L.r[i].key ) j = k ;if(i!=j)( W-L.r[il; L.rlil =-L.r[il; L.r[i] = W; ?1 // SelectPass5中国科学技术大学ypb@ustc.edu.cn
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
选择排序void SelectSort (SqTable &L) RcdType W ;for (i=l; i<L.len; ++i) {j=i;for (k=i+1; k<=L.len; k++ )if(L.r[k].key < L.r[i].key) j =k ;SelectPassif (i!=i ) W-L.r[il;L.r[i] =L.r[i];L.r[i] = W;) // SelectSort6中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 6 中国科学技术大学 选择排序 void SelectSort (SqTable &L) { 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
起泡排序voidBubbleSort（SqTable&L）复杂度O(n2)-有序序列的比较次数是n-1次-逆序序列的比较次数是n(n-1)/2；移动次数3n(n-1)/2一是稳定排序R[i]无序序列R[1]有序序列R[i+1..n]无序序列R[1..i-1]有序序列R[i..n]MUSwPuit灯片放中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 7 中国科学技术大学 void BubbleSort（SqTable &L）复杂度 O(n2 ) –有序序列的比较次数是n-1次 – 逆序序列的比较次数是 n(n-1)/2；移动次数3n(n-1)/2 – 是稳定排序 R[i] 无序序列R[1.i] 有序序列R[i+1.n] 无序序列R[1.i-1] 有序序列R[i.n] 起泡排序
void BubbleSort(SqTable &L )i = L.len,while (i>1) (lastExchangeIndex = 1;for (j = l; j<i; j++)(if (L.r[j+1].key <L.r[j].key) (W-L.rli]; L.r[i] =L.r[j+1]; L.r[i+1] = W;lastExchangeIndex = j; //if} //fori= lastExchangeIndex:} // while // BubbleSort8中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 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
对比void bubble sort(int all, int n):for (i-n-1, change=TRUE; i>0 && change; --i) change =FALSE;for (j=O; j<i; ++i)if (a[i] ≥ a[j+1])( w = a[i]; a[i]= a[j+1]; a[j+1]= W, change = TRUE人9中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 9 中国科学技术大学 对比 void bubble_sort(int a[], int n){ for (i=n-1, change=TRUE; i>0 && change; -i) { change = FALSE; for (j=0; j a[j+1]) { w = a[j]; a[j]= a[j+1]; a[j+1]= w; change = TRUE } } }
插入排序&L,int i)复杂度 O(n)void InsertPass(SqTable&L）复杂度0(n2)void InsertSort(SqTable数据的有序性影响算法最差比较移动（n+4）（n-1）/2一是稳定排序R[i]有序序列R[1..i-1]无序序列R[i..n]有序序列R[1..i]无序序列R[i+1.n]10中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 10 中国科学技术大学 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] 插入排序