<<软件技术基础>> 排序

排序

教学目标 了解有关排序的 基本概念 排序的典型算法

教学要求 通过本单元的学习，了解、掌握有关排序的： 基本概念 排序、排序分类、算法稳定性 典型的排序算法 插入排序、选择排序、交换排序 快速排序、归并排序

一、基本概念 排序 排序分类 算法稳定性

排序(Sorting) 就是将记录按关键字递增(递减)的次序排列起来,形成新的有序序列,称为排序。 设n个记录的序列为{R1,R2,…,Rn},其相应关键字序列为{K1,K2,…,Kn},需确定一种排序P1,P2,…,Pn,使其相应的关键字满足递增(升序),或递减(降序)的关系: Kp1  Kp2 ... Kpn 或 Kp1  Kp2 ….  Kpn

排序分类 根据排序元素所在位置的不同,排序分: 内排序和外排序。 内排序 在排序过程中，所有元素调到内存中进行的排序，称为内排序。内排序是排序的基础。内排序效率用比较次数来衡量。 外排序 在数据量大的情况下，只能分块排序，但块与块间不能保证有序。外排序用读/写外存的次数来衡量其效率。

内排序方法分类 内排序方法有许多种： 按排序过程中依据的不同原则分类： 插入、交换、选择、归并和基数排序等； 按排序过程中所需工作量来区分： 简单排序（O（n2 ）） 快速排序（O（nlogn）） 基数排序（O（d*n）） 排序过程中所需进行的操作： 比较两个关键字的大小 移动记录的位置 2

排序算法的稳定性 若待排序的序列中，存在多个具有相同关键字的记录，经过排序，这些记录的相对次序保持不变，则称该算法是稳定的； 若经排序后，记录的相对次序发生了改变，则称该算法是不稳定的。

排序算法的数据结构 顺序存储结构（C语言描述）： #define N n struct record { int key ； /* 关键字项 */ int otherterm； /* 其它项 */ } ； typedef struct record RECORD； RECORD file[N+1]；

二、典型排序算法 插入排序 选择排序 交换排序 快速排序 归并排序

⑴插入排序（算法3-5） 基本思想： 将n个元素的数列分为已有序和无序两个部分。 {{a1}，{a2，a3，a4，…,an}} …... {{a1(n-1)，a2(n-1) ，…}, {an(n-1)}} 每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较,找出插入位置,将该元素插入到有序数列的合适位置中。 有序 无序

插入排序算法步骤 Step1 从有序数列{a1}和无序数列{a2,a3,…,an}开始进行排序; Step2 处理第i个元素时(i=2,3,…,n),数列 {a1,a2,…,ai-1}是已有序的,而数列{ai,ai+1,…,an}是无序的。用ai与ai-1、a i-2,…,a1进行比较,找出合适的位置将ai插入。 Step3 重复Step2，共进行n-1的插入处理，数列全部有序。

插入排序举例 设有数列{ 18，12，10，12，30，16 } 初始状态：{18}，{12，10，12，30，16} 比较次数 初始状态：{18}，{12，10，12，30，16} 比较次数 i=1 {18}，{12，10，12，30，16} 1 i=2 {12，18}，{10，12，30，16} 2 i=3 {10，12，18}，{12，30，16} 2 i=4 {10，12，12，18}，{30，16} 1 i=5 {10，12，12，18，30}，{16} 3 {10，12，12，16，18，30 } 总计： 9 次

插入排序算法 insert_sort(item , n ) int *item ,n ; { int i，j，t ; for（i=1；i<n;i++ )/* n-1次循环 */ { t=item[i]; /* 要插入的元素 */ j = i - 1; /* 有序部分起始位置 */ while(j>=0 && t < item[j])/* 寻找插入位置*/ { item[j+1]=item[j]; /* 当前元素后移 */ j- - ; } item[j+1]=t; /* 插入该元素 */

插入排序算法主程序 #include “stdio.h” main( ) { int i,a[ ]={18,12,10,12,30,16}; printf(“Before sorting\n”); for(i=0;i<6;i++) printf(“%3d”,a[i]); printf(“\n”); insert_sort(a,6); /* 调用插入排序函数 */ printf(“After sorting\n”); printf(“%3d”,a[i]); printf(“\n”); } 示例

算法讨论 插入算法比较次数和交换次数约为 n2/2，因此，其时间复杂度为O（ n2 ）。 该算法是稳定的。

⑵选择排序（算法3-6） 基本思想：每次从待排序的记录中选出关键字最小（或最大）的记录，顺序放在已有序的记录序列的最后（或最前）面，直到全部数列有序。 {{a1}，{a2，a3，a4，…,an}} {{a1(1)，a2(1)}，{a3(1)，a4(1)…,an(1)}} …... {{a1(n-1)，a2(n-1) ，…}, {an(n-1)}} 有序 无序

选择排序算法步骤 Step1 从原始数列{a1 , a2,a3,…,an}开始进行排序，比较n-1次，从中选出最小关键字，放在有序数列中，形成{a1}、 {a2,a3,…,an}有序数列和无序数列两部分，完成第1趟排序。 Step2 处理第i趟排序时(i=2,3,…,n),从剩下的n-i+1个元素中找出最小关键字，放在有序数列的后面。 Step3 重复Step2，共进行n-1趟的选择处理，数列全部有序。

选择排序举例 设有数列{ 18，12，10，12，30，16 } 初始状态：{}，{18，12，10，12，30，16} 比较次数 初始状态：{}，{18，12，10，12，30，16} 比较次数 i=1 {10}，{18，12，12，30，16} 5 i=2 {10，12}，{12，18，30，16} 4 i=3 {10，12，12}，{18，30，16} 3 i=4 {10，12，12，16}，{18，30} 2 i=5 {10，12，12，16，18}，{30} 1 总计： 15 次

选择排序算法 select_sort(int *item,int count) { int i,j,k，t; for(i=0;i<count-1;++i)/* n-1次循环 */ { k=i; /* 无序部分第1个元素 */ t=item[i]; /* 及位置 */ for(j=i+1;j<count;++j)/* 寻找最小值循环 */ { if(item[j]<t) { k=j; t=item[j]; }/* 记录最小值及位置 */ } item[k]=item[i]; /* 交换最小值与无序 */ item[i]=t; /* 部分最后1个元素位置*/

选择排序算法主程序 #include "stdio.h" #define N 6 static int n=0; main() { int a[100],i; printf("Enter a[i]\n"); for(i=0;i<N;i++) scanf("%d",&a[i]); select_sort(a,N);/* 调用选择排序函数 */ printf(" %d ",a[i]); printf("\nn=%d\n",n); } 示例

算法讨论 每次选出当前最小关键字，但没有为以后的选择留下任何信息，比较次数仍为O（ n2 ）。 选择排序算法是不稳定的。

3、交换排序（冒泡排序） 指导思想： 两两比较待排序记录的关键字，并交换不满足顺序要求的那些偶对元素，直到全部数列满足有序为止。 冒泡排序（Bubble sort）是基于交换排序的一种算法。它是依次两两比较待排序元素；若为逆序（递增或递减）则进行交换，将待排序元素从左至右比较一遍称为一趟“冒泡”。每趟冒泡都将待排序列中的最大关键字交换到最后（或最前）位置。直到全部元素有序为止。    …  a1 a2 a3 … an-1 an 最大值

冒泡排序（算法3-7） step1 从待排序队列的前端开始(a1)两两比较记录的关键字值,若ai>ai+1(i=1,2,…,n-1),则交换ai和ai+1的位置,直到队列尾部。一趟冒泡处理，将序列中的最大值交换到an的位置。 step2 如法炮制，第k趟冒泡，从待排序队列的前端开始(a1)两两比较ai和ai+1（i=1，2，…n-k)，并进行交换处理,选出序列中第k大的关键字值,放在有序队列的最前端。 Step3 最多执行n-1趟的冒泡处理,序列变为有序。

冒泡排序算法举例 设有数列{ 65,97,76,13,27,49,58 } 比较次数 第1趟 {65，76，13，27，49，58}，{97} 6 第2趟 {65，13，27，49，58}，{76，97} 5 第3趟 {13，27，49，58}，{65，76，97} 4 第4趟 {13，27，49}，{58，65，76，97} 3 第5趟 {13，27}，{49，58，65，76，97} 2 第6趟 {13}，{27，49，58，65，76，97} 1 总计： 21 次

冒泡排序算法3-7 bubble(int *item,int count) { int a,b，t; for(a=1;a<count;++a) /* n-1 趟冒泡处理 */ for(b=1;b<=count-a;b++)/* 每趟n-i次的比较 */ if(item[b-1]>item[b])/* 若逆序，则交换 */ { t=item[b-1]; /* 它们的位置 */ item[b-1]=item[b]; item[b]=t; }

冒泡排序算法3-7主程序 #define N 7 #include "stdio.h" main() { int s[]={65,97,76,13,27,49,58},i; bubble(s,N); /* 调用选择排序函数 */ printf("The sorted string is:\n"); for(i=0;i<N;i++) printf(" %d",s[i]); } 示例

改进的冒泡排序算法3-8 从上述举例中可以看出，从第4趟冒泡起，序列已有序，结果是空跑了3趟。若两次冒泡处理过程中，没有进行交换，说明序列已有序，则停止交换。这就是改进的冒泡算法的处理思想。 用改进的冒泡算法进行处理，比较次数有所减少。 对于数列{ 65,97,76,13,27,49,58 } 比较次数 第1趟 {65，76，13，27，49，58}，{97} 6 第2趟 {65，13，27，49，58}，{76，97} 5 第3趟 {13，27，49，58}，{65，76，97} 4 第4趟 {13，27，49}，{58，65，76，97} 3 总计： 18 次

改进的冒泡排序算法3-8 bubble_a(int *item,int count) { int a,b,t,c; for(a=1;a<count;++a) /* n-1趟的循环 */ { c=1; /* 设置交换标志 */ for(b=1;b<=count-a;b++)/* n-1趟处理 */ { if(item[b-1]>item[b])/* 若逆序，则 */ { t=item[b-1]; /* 交换位置 */ item[b-1]=item[b]; item[b]=t; c=0; } /* 若有交换，则 */ } /* 改变交换标志 */ if(c) break; /* 若没有交换，则 */ } /* 退出处理 */ } 示例

算法讨论 若待排序列有序(递增或递减),则只需进行一趟冒泡处理即可;若反序，则需进行n-1趟的冒泡处理。在最坏的情况下,冒泡算法的时间复杂度是O( n2 )。 当待排序列基本有序时，采用冒泡排序法效果较好。 冒泡排序算法是稳定的。

4、快速排序 快速排序法是一位计算机科学家C.A.R.Hoare推出并命名的。曾被认为是最好的一种排序方法。快速排序法是对冒泡排序法的一种改进，也是基于交换排序的一种算法。因此，被称为“分区交换排序”。

快速排序基本思想 在待排序序列中按某种方法选取一个元素K，以它为分界点，用交换的方法将序列分为两个部分：比该值小的放在左边，否则在右边。形成 再分别对左、右两部分实施上述分解过程，直到各子序列长度为1，即有序为止。 分界点元素值K的选取方法不同，将构成不同的排序法，也将影响排序的效率： 取左边第1个元素为分界点； 取中点A[（left+right）/2]为分界点； 选取最大和最小值的平均值为分界点等。 设有序列{a1，a2，…,An},选取中点元素K为分界点,分别从序列两头分别与K进行比较,小于K的元素交换到左边,否则交换到右边;一趟处理后,左边子序列的元素均小于分界点值K,右边子序列元素均大于等于K值。

快速排序（算法3-9） Step1 分别从两端开始，指针i指向第一个元素A[left]，指针j指向最后一个元素A[right]，分界点取K ； Step2 循环（ij） 从右边开始进行比较： 若K  A[j]，则将A[j]交换到左边； 若K 〈 A[j] ，则 j=j-1，再进行比较； 从左边开始进行比较： 若K 〉 A[i]，则 i=i+1，再进行比较； 若K  A[i]，则将A[i]交换到右边。 当i=j时，一次分解操作完成。 Step3 在对分解出的左、右两个子序列按上述步骤继续进行分解，直到子序列长度为1（不可再分）为止，也即序列全部有序。

快速排序算法举例 对于数列{49，38，60，90，70，15，30，49}， 采用中点分界法： 初始状态: 49 38 60 90 70 15 30 49 比较次数 第1趟 49 38 60 90 70 15 30 49 49 38 60 90 70 15 30 49 5（i4、j1） 49 38 30 49 70 15 60 90 5（i4、j1） { 49 38 30 49 70 15 60 } 90 小计：10 k = 90 j i i j i j

快速排序算法举例（续一） 初始状态: 49 38 60 49 70 15 30 比较次数 第2趟 49 38 60 49 70 15 30 2（i1、j1） 30 38 60 49 70 15 49 30 38 15 49 70 60 49 { 30 38 15}49{ 70 60 49 } 小计：8 k = 49 i j i j 3（i2、j1） j i 3（i1、j2） i j

快速排序算法举例（续二） k = 38 初始状态: 30 38 15 比较次数 第3趟 30 38 15 3（i2、j1） 初始状态: 30 38 15 比较次数 第3趟 30 38 15 3（i2、j1） { 30， 15 } 38 小计：3 第4趟 70 60 49 2（i1、j1） 49 60 70 2（i1、j1） 小计：4 i j i j k = 60 i j i j

快速排序算法举例（续三） 第5趟 30 15 2（i1、j1） 15 30 小计：2 最后状态： k = 30 初始状态: 30 15 比较次数 第5趟 30 15 2（i1、j1） 15 30 小计：2 最后状态： { 15 30 38 49 49 60 70 90 } 总计： 27 i j

快速排序算法3-9 quick_sort(item,count) int *item,count; { qs(item,0,count-1); }

qs（）子函数 qs(int *item,int left,int right) { int i,j,x,y,k; i=left; j=right; x=item[(left+right)/2]; /* 计算中点位置 */ do{ /* i≤j 的循环处理 */ while(item[i]<x && i<right ) i++ ； /* 确定i点交换位置 */ while(x<item[j] && j>left) j--; /* 确定j点交换位置 */ if(i<=j) /* 如果i、j位置合法，则交换 */ { y=item[i]; /* A[i]和A[j]的位置 */ item[i]=item[j]; item[j]=y; i++; j--; } } while(i<=j); if(left<j) qs(item,left,j); /* 对分割出的左部再处理*/ if(i<right) qs(item,i,right); /* 对分割出的右部再处理*/

快速排序算法3-9主程序 #include "stdio.h" main( ) { int s[]={49,38,60,90,70,15,30,49}，n,i; quick_sort(s,8); /* 调用快速排序函数 */ printf("The sorted string is :\n"); for( n=0; n < 8; n++ ) printf(" %d",s[n]); printf(“\n”); } 示例

算法讨论 分界点选取方法不同，排序效果差异很大； 比较次数为nlogn，即为：O（nlogn），交换次数为n/6*logn。 快速排序算法是不稳定的。

5、归并排序 归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表；即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

归并排序（算法3-12） Step1 把待排序的n个记录看作是长度为1的有序序列。将相邻子序列两两归并为长度为2的有序序列； Step3 按Step2的方式，重复对相邻有序子序列进行归并操作，直到成为一个有序序列为止。

归并排序算法简述 设有待排序数列 {49，38，65，97，76，12，27}， 第一趟处理，先将每个元素看成是有序的子序列，即 [49] [38] [65] [97] [76] [12] [27] 第二趟处理，将长度为1的子序列合并为长度为2的子序列，即 [38 ，49] [65，97] [12 ，76] [ 27 ] 第三趟处理，将长度为2的子序列合并为长度为4的子序列，即 [38 ，49 ，65，97] [12 ，27，76 ] 第四趟处理，将长度为4的子序列合并为长度为8的序列，即 [12，27，38 ，49 ，65，76，97] 提示：将归并过程中贡献出的元素，送进工作单元（SWAP[m]）中。

归并排序算法3-12说明 设有两个有序序列L1和L2，它们顺序存放在数组X[l1]，X[l1+1]，…,X[u1]和X[l2],X[l2+1],…,X[u2]中,其中: l2=u1+1; 设置三个变量 i、j、m，其中i、j分别表示序列L1和L2中当前要比较的记录的位置；初值 i=l1， j=l2。m表示Swap数组中当前位置，初值m=l1。 归并时，反复比较X[i]和X[j]： 若X[i]X[j] 则X[i]送Swap[m]，i++；m++； 若X[i]>X[j] 则X[j]送Swap[m]，j++；m++； 当序列L1或L2的全部记录已归并到数组X中,即i=u1+1,或j=u2+1时, 比较结束,然后将另一个序列中剩余的所有记录依此放回到数组Swap中,完成L1和L2的合并。

归并排序算法举例 设有数列{6，202，100，301，38，8，1}， 初始状态： [6] [202] [100] [301] [38] [8] [1] 比较次数 i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ] 3 i=2 [ 6 100 202 301 ] [ 1 8 38 ] 4 i=3 [ 1 6 8 38 100 202 301 ] 4 总计： 11 SWAP数组： 6 100 202 301 1 8 8 38 SWAP数组： 1 6 8 38 100 202 301

归并排序算法3-12 merge_sort(int *x,int n) { int i,k,l; int swap[N]; k=1; while(k<n) /* 步长从1到2*m的循环 */ merge(x,swap,k,n); for(i=0;i<n;i++) /* 将数列从SWAP放回X中 */ x[i]=swap[i]; k=2*k; /* 序列长度加倍 */ }

归并排序算法3-12(续一） merge(int *x,int *swap,int k,int n) { int i, j, l1, l2, u1, u2, m; l1=0; m=0; while(l1+k<n) { l2=l1+k; u1=l2-1; u2=(l2+k-1<n)?l2+k-1:n-1; for(i=l1,j=l2;i<=u1&&j<=u2;m++) { if(x[i]<=x[j]) { swap[m]=x[i]; i++; }/* x[i]贡献出 */ else { swap[m]=x[j]; j++; }/* x[j]贡献出 */ } while(i<=u1) /* 将序列1中剩余元素顺序放回SWAP中 */ { swap[m]=x[i]; m++; i++; } while(j<=u2)/* 将序列1中剩余元素顺序放回SWAP中 */ { swap[m]=x[j]; m++; j++; } l1=u2+1; /* 改变子序列 */ }/*将原始序列中剩余的、不足一组的记录顺序放到SWAP中 */ for(i=l1;i<n;i++,m++) swap[m]=x[i];

归并排序算法3-12主程序 #define N 7 main( ) { int s[N]，n,i; printf("Enter a[i]\n"); for(i=0;i<N;i++) scanf("%d",&a[i]); merge_sort(a,N); /* 调用归并排序函数 */ printf("The sorted string is :\n"); for( n=0; n < N; n++ ) printf(" %d",s[n]); printf(“\n”); } 示例

算法讨论 空间复杂度为O（ n ）， 用辅助空间L1、L2、（Swap） 时间复杂度为O（nlogn） 2-路归并排序算法是稳定的。

希尔（Shell）排序 希尔排序是一种快速排序法，出自D.L.Shell, 指导思想： 仍采用插入法，排序过程通过调换并移动数据项来实现。每次比较指定间距的两个数据项，若左边的值小于右边的值，则交换它们的位置。间距d按给定公式减少： di+1 =（di +1）/2 ，直到d等于1为止。d取{9，5，3，2，1}。

算法步骤 Step1 将n个元素个数列分为n个部分，元素比较间距为d。 step2 在第i步，两元素比较的间距取 di+1 =（di +1）/2 {9，5，3，2，1} 若ai+1 > ai ,则交换它们的位置。 Step3 重复上述步骤，直到dK = 1。

希尔排序举例 设有数列“f d a c b e”, 第1趟 d=5 f d a c b e 得到 e d a c b f 第2趟 d=3 e d a c b f 得到　 c b a e d f 第3趟 d=2 c b a e d f 得到　 a b c e d f 第4趟 d=1 a b c e d f 得到　 a d c d e f

SHELL排序子函数 shell(char *item,int count) { int i,j,k,s,w; char x; int a[]={9,5,3,2,1}; for(w=0;w<5;w++)/* 不同步长的5次循环 */ { k=a[w];s=-k; for(i=k;i<count;i++) { x=item[i]; j=i-k; 　　　 if(s==0) 　　 { s++; item[s]=x; } 　　 while(x<item[j]&&j>=0&&j<=count) 　 { item[j+k]=item[j]; j=j-k; } item[j+k]=x; }

SHELL排序主函数 main() { char s[80];int l; printf("Enter a string:"); #include "stdio.h" main() { char s[80];int l; printf("Enter a string:"); gets(s); l=strlen(s); shell(s,l); /* 调用shell函数 */ printf("The sorted string is: %s\n",s); } 示例