搜索
第9章内部排序-.275.-第9章内部排序本章学习要点◆熟悉并掌握本章中各种内部排序方法的基本思想及其实现过程◆掌握各种内部排序算法的时间复杂度和空间复杂度的计算和分析方法◆了解各种内部排序方法的优缺点以及其不同的应用场合◆要求能够针对实际问题的特点选择合理的排序算法并通过编程实现排序（Sorting）是计算机程序设计中的一种重要运算，它的功能是将一组数据元素按照其关键字的某种规定顺序（递增或递减）进行排列。对数据元素进行排序的目的是为了便于查找，在关键字有序的一组数据中的查找要比无序时更容易，速度也更快。本章主要介绍几种常用的内部排序方法，主要有：插入排序、交换排序、选择排序、归并排序和基数排序。最后对各种排序算法的时间复杂度和空间复杂度进行了分析和比较，并且讨论了如何针对实际问题合理选择排序算法等内容。9.1排序的有关概念和数组的输入与输出9.1.1排序的概念1．排序将一个数据元素的任意序列，重新排列成一个按关键字有序（递增有序或递减有序）的序列的过程叫排序。2．排序方法的稳定性若在排序过程中，序列的两个关键字值相同的记录的相对位置不发生改变，则称所用的排序方法为稳定的；反之，若在某个序列的排序过程中关键字值相同的记录的相对位置发生了改变，则称所用的排序方法是不稳定的。3．内部排序和外部排序在排序过程中，如果待排序列全部读入计算机存储器中，则称此为内部排序；反之，若待排序列仅有部分记录在内存中，在排序过程中还要对外存中的纪录进行访问，这样的排序过程叫外部排序。4．排序方法的性能分析对于所选用的排序方法的好坏主要是基于其算法的时间复杂度和空间复杂度两方面进行分析。5．数据元素类型说明数据元素可以是任意一个结构类型，排序过程是按元素中的某个关键字（数据项）进行第9章内部排序-.276.-排序。不失一般性，我们在本章的所有例题中总是假定待排序列中的数据元素中只含有关键字项，且其数据类型为整型。9.1.2一维数组的输入与输出1．数组输入操作函数voidInput(int*A,intn)的功能是，从键盘输入n个整数到数组A[]中。#includeiostream.hvoidInput(int*A,intn){inti;cout请输入n个整数:\n;for(i=0;in;i++)cinA[i];}2．数组输出操作函数voidOutput(intA[],intn)的功能是，依次显示输出数组A[]中的n个整数。voidOutput(intA[],intn){inti;cout结果为:\n;for(i=0;in;i++)coutA[i];coutendl;}3．数组排序操作函数voidMainSort(void(*sort)(int*,int))的功能是，首先通过函数调用Input(A,n)输入n个整数到数组A[]中，再通过函数调用sort(A,n)对A[]中的n个整数排序，最后通过函数调用Out(A,n)显示输出数组A[]中的n个整数。voidMainSort(void(*sort)(int*,int)){int*A,n;cout请输入整数的个数:\n;cinn;A=newint[n];Input(A,n);cout原顺序;Output(A,n);sort(A,n);//调用sort对数组A进行处理cout排序后的顺序;Out(A,n);delete[]A;}9.2插入排序法第9章内部排序-.277.-9.2.1直接插入排序(StraightInsertionSort)1．算法思想对于任意排列的序列(a0,a1,a2,…,an-1)，先将第一个记录看成是一个有序序列L1=(a0)，再将第2个记录插入到L1中得到有序序列L2=(a0,a1),,一般的，将第k+1个记录插入到有序序列Lk中得到有序序列Lk+1，如此重复插入n-1次即可得到有序序列Ln=(a0,a1,a2,…,an-1)。2．举例说明设原始序列为：8、3、5、2、9、7、*5、4第1轮：(8)3,5,2,9,7,*5,4第2轮：(3,8)5,2,9,7,*5,4第3轮：(3,5,8)2,9,7,*5,4第4轮：(2,3,5,8)9,7,*5,4第5轮：(2,3,5,8,9)7,*5,4第6轮：(2,3,5,7,8,9)*5,4第7轮：(2,3,5,*5,7,8,9)4第8轮：(2,3,4,5,*5,7,8,9)3．算法实现voidInsertSort(intA[],intn){inttemp,i,j;for(i=0;in-1;i++){for(temp=A[i+1],j=i+1;j0;j--){if(temp=A[j-1])break;A[j]=A[j-1];}A[j]=temp;//将temp插入到相应的位置}}4．算法分析从排序过程可知该算法是稳定的；算法的比较次数为f(n)=1+2+3+…+n-1，所以该算法的时间复杂度为T(n)=O(n2)；由于在排序过程中仅有一个辅助变量（temp），所以该算法的空间复杂度为S(n)=O(1)。说明：（1）从算法的基本操作部分可以看出，当待排序数组A[n]基本有序时可以大大减少其比较的执行次数，所以该算法适用于序列为基本有序的场合。（2）使用直接插入排序算法排序时可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。比如，初始序列的最后一个元素为最小元素时就会出现以上情况。*9.2.2折半插入排序折半插入排序是直接插入排序的一个改进算法，该算法在排序过程中，通过折半查找法来实现寻找插入位置的操作，从而减少了数据元素中关键字的比较次数。第9章内部排序-.278.-1．折半插入排序函数voidInertSort1(inta[],intn){inti,j,k,t,l,h;for(i=1;in;i++)if(a[i]a[i-1]){l=0;h=i-1;while(l=h)//用二分法查找插入位置{t=(l+h)/2;if(a[t]==a[i])break;elseif(a[t]a[i])l=t+1;elseh=t-1;}if(hl)t=l;//查找失败for(k=a[i],j=i;jt;j--)a[j]=a[j-1];a[j]=k;}}2．分步实现折半查找插入排序(1)函数intFound(intA[],intn,intx)通过折半查找法求元素x在数组A[n]中的插入下标。intFound(intA[],intn,intx){intt,l,h;l=0;h=n-1;if(x=A[h])t=n;elseif(x=A[0])t=0;else{while(l=h){t=(l+h)/2;if(A[t]==x)break;elseif(A[t]x)l=t+1;elseh=t-1;}if(hl)t=l;}returnt;}(2)调用函数Found()实现插入排序。voidInertSort2(inta[],intn){inti,j,x,t;for(i=1;in;i++)第9章内部排序-.279.-{x=a[i];t=Found(a,i,x);for(j=i;jt;j--)a[j]=a[j-1];a[t]=x;}}9.2.3希尔排序法(ShellSort)1．算法思想先将整个待排的n个记录序列按照某个间隔值d1（通常取n/2）分割成为若干个子序列，再对其分别进行直接插入排序，下一步取间隔值d2d1（通常取di+1=di/2）重复前面的过程,,直到间隔值为1时对整体序列进行最后一次直接插入排序。2．举例说明设原始序列为：7、5、9、13、10、2、3、*5、8、1，其长度为n=10。第1轮：取间隔值d=10/2=5，先将序列看成如图9.1(a)所示的5个子序列：(7,2)(5,3)(9,*5)(13,8)(10,1)。再分别对每个子序列进行插入排序，其结果为如图9.1(b)所示的子序列：(2,7)(3,5)(*5,9)(8,13)(1,10)。第1轮排序结果为：2,3,*5,8,1,7,5,9,13,10（注意：在对各子序列排序时，子序列在主序列中的相对位置不变）。第2轮：取间隔值d=5/2=2，先将序列分成如图9.2(a)所示的2个子序列：(2,*5,1,5,13)(3,8,7,9,10)。再分别进行插入排序，其结果为如图9.2(b)所示的子序列：(1,2,*5,5,13)(3,7,8,9,10)。第2轮排序结果为：1,3,2,7,*5,8,5,9,13,10。第3轮：取d=2/2=1，此时将整体序列进行一次直接插入排序。第3轮排序结果为：1，2，3，*5，5，7，8，9，10，13。第9章内部排序-.280.-3．算法实现(1)算法Insert(A,k,n)的功能是，对数组A[n]按间隔k进行分组插入排序voidInsert(intA[],intk,intn){inti,j,temp;for(i=k-1;in-1;i++){//A[i+1]为要插入的元素for(temp=A[i+1],j=i+1;j-k=0;j-=k){//在相应的子序列中寻找插入位置。if(temp=A[j-k])break;A[j]=A[j-k];}A[j]=temp;//将temp插入到相应的位置}}(2)希尔排序函数voidShellSort(intA[],intn){intk=n;while(k=k/2){Insert(A,k,n);}}4．算法分析该算法是不稳定的；希尔排序算法的时间复杂度与间隔值d的取法有关，当取d1=n，di+1=di/2(i=1,2,3,…)时，该算法的时间复杂度为T(n)=O(nlog2n)，空间复杂度为S(n)=O(1)。9.3交换排序法交换排序是借助于交换操作来完成的排序方法。它的基本思想是：在待排序的序列中，找到不满足序性的两个关键字，交换相应元素的相对位置，以满足序性；重复该过程，直到序列中所有元素的关键字都有序为止。本节主要介绍最为常见的两个交换排序算法：起泡排序法和快速排序法。9.3.1起泡排序法(BubbleSort)1．算法思想(大数沉底法)起泡排序算法的基本思想是：先将第1个与第2个记录的关键字比较，如果关键字逆序，则交换这两个记录，否则不交换；再将第2个与第3个记录的关键字比较，如果关键字逆序，则交换第2个与第3个记录，否则不交换，…，以此类推，最后将第n-1个与第n个记录的关键字比较，如果关键字逆序，则交换，否则不交换。上述过程称为一趟起泡排序，其结果是使关键字值最大的记录移到第n个记录的位置。然后对前n-1个记录进行同样的操作，第第9章内部排序-.281.-2趟起泡排序的结果是使关键字值次大的记录移到第n-1个记录的位置。一般地，第i趟起泡排序的结果是从前n-i个记录中将关键字最大的记录移到第n-i+1个记录的位置上。如果在某一趟排序中没有发生交换操作，则整个排序提前结束，否则最后排到仅剩一个记录为止。2．举例说明设原始记录序列为：8、3、5、2、9、7、*5、4第1趟排序结果：3,5,2,8,7,*5,4,(9)第2趟排序结果：3,2,5,7,*5,4,(8,9)第3趟排序结果：2,3,5,*5,4,(7,8,9)第4趟排序结果：2,3,5,4,(*5,7,8,9)第5趟排序结果：2,3,4,(5,*5,7,8,9)第6趟排序结果：2,3,(4,5,*5,7,8,9)由于没有发生交换操作，排序提前结束。3．算法实现voidBubbleSort(intA[],intn){inti,j,t,f;//f=1时表示发生了交换操作for(f=1,i=n-1;i0&&f;i--){for(f=0,j=0;ji;j++)if(A[j]A[j+1])//如果产生逆序{f=1;t=A[j];A[j]=A[j+1];A[j+1]=t;//交换A[j]与A[j+1]的值}}}4．算法分析起泡排序算法是稳定的。容易算出，该算法的时间复杂度为T(n)=O(n2)，空间复杂度为S(n)=O(1)。算法的基本操作是交换操作，