各种经典排序算法

排序本节基本内容与要求基本内容顺序查找、二分查找、二叉树查找以及散列表上查找及算法思想排序的基本概念以及选择、插入、交换和归并四类排序的基本思想和算法要求掌握线性表、树和散列表(或称哈希表)的查找方法及算法实现以及各种查找方法的应用熟练掌握选择、插入、交换和归并四类排序的基本思想和算法排序1.4内部排序一、基本概念二、插入排序三、交换排序四、选择排序五、归并排序排序一、基本概念1.排序的功能：将一个数据元素（或记录）的任意序列，重新排成一个按关键字有序的序列。例如：下列是一组记录对应的关键字序列(52,49,80,36,14,58,61,23,97,75)调整为(14,23,36,49,52,58,61,75,80,97)排序2.排序的定义假设含n个记录的序列为{R1,R2,…，Rn}其相应的关键字序列为{K1,K2,…，Kn}这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系：Kp1≤Kp2≤…≤Kpn按此固有关系将上式记录序列重新排列为{Rp1,Rp2,…，Rpn}的操作称作排序。排序3、排序的基本操作排序的概念：就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。排序过程的组成步骤：首先比较两个关键字的大小；然后将记录从一个位置移动到另一个位置。对记录的关键字大小进行比较将记录从一个位置移动到另一个位置当待排序记录的关键字均不相同时，则排序结果是唯一的，否则排序的结果不一定唯一。排序4、排序的稳定性若有：{R1,...,Ri,...,Rj,.....}且关键字：Ki=Kjij排序后：{Ri,Rj,.....}则称该排序结果具有稳定性。在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。排序内部排序：是指在排序的整个过程中，数据全部存放在计算机的内存储器里，并且在内存储器里调整数据的位置；当文件很大以致内存不足以存放全部数据时，在排序过程中需要对外存进行存取访问，称这种借助于外存储器进行排序的方法为外部排序。注意：①内排序适用于记录个数不很多的小文件②外排序则适用于记录个数太多，不能一次将其全部记录放入内存的大文件。5、排序的分类排序每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。把新元素（未排序的元素的关键字）逐个插入正在增长的顺序表中。寻找插入位置的方法：线性插入排序对半插入排序希尔排序二、插入排序排序有序序列L.r[1..i-1]L.r[i]无序序列L.r[i..n]有序序列L.r[1..i]无序序列L.r[i+1..n]1、线性插入排序基本思想：每步将一个待排序的元素按其大小插入到前面已排序的数据中的适当位置。重复该工作，直至有序区包含所有元素。排序方法：具体方法：先将第一个数据看成是一个有序的子序列，然后从第2个数据起逐个插入到这个有序的子序列中去，相应的元素要移动。3．将L.r[i]插入到L.r[j+1]的位置上。2．将L.r[j+1..i-1]中的所有记录均后移一个位置；1．在L.r[1..i-1]中查找L.r[i]的插入位置，L.r[1..j]L.r[i]L.r[j+1..i-1]；排序该算法适合于n较小的情况，时间复杂度为O(n2).待排元素序列：[53]2736156942第一次排序：[2753]36156942第二次排序：[273653]156942第三次排序：[15273653]6942第四次排序：[1527365369]42第五次排序：[152736425369]线性插入排序示例对于有n个数据元素的待排序列，插入操作要进行n-1次例：排序voidinsertSort(RedTypeL[],intn){inti,j;for(i=2;i=n;i++){L[0]=L[i];//作为监视哨for(j=i-1;L[0].keyL[j].key;j)L[j+1]=L[j];//记录后移L[j+1]=L[0];//插入}}插入算法方法:Ki与Ki-1,Ki-2,…K1依次比较,直到找到应插入的位置。排序哨兵(监视哨)哨兵(监视哨)有两个作用作为临时变量存放R[i](当前要进行比较的关键字)的副本；在查找循环中用来监视下标变量j是否越界。R[0]R[1]R[2]R[3]R[4]R[5]6206157315620157376152073367152033671520直接插入排序的程序：#includestdio.h#definen5intar[n];intc,t;voidd_insort(a)inta[n];{inti,j;for(i=2;i=n;i++){t=a[i];j=i-1;while((j0)&&(ta[j])){a[j+1]=a[j];j=j-1;}a[j+1]=t;}}main(){inti;printf(请输入数据:);for(i=1;i=n;i++)scanf(%d,&ar[i]);d_insort(ar);printf(排序后的序列:);for(i=1;i=n;i++){printf(%d|,ar[i]);}printf(\n);}运行结果：请输入数据:5060204080排序后的序列:20|40|50|60|80|排序性能分析最好情况（原始记录按关键字有序排列）：O（n）“比较”的次数：最坏情况（原始记录按关键字逆序排列）：O（n2）“比较”的次数：112nni02)1)(4()1(2nnini“移动”的次数：“移动”的次数：2)1n)(4n()1i(n2i结论：适用原始数据基本有序或数据量不大的情况。排序希尔排序（Shell’smethod）又称为“缩小增量排序”，本质上讲是插入排序，它是对线性插入排序的改进。其基本思想是：先取一个小于n的整数d1并作为第一个增量，将文件的全部记录分成d1个组，所有距离为d1倍数的记录放在同一个组中，在各组内进行直接插入排序；然后取第二个增量d2d1，重复上述的分组和排序，直至所取的增量dt=1(dtdt1…d2d1)为止，此时，所有的记录放在同一组中进行直接插入排序。2希尔插入排序——算法思想排序如何选择增量序列才能产生最好的排序效果，这个问题至今没有得到解决。希尔本人最初提出取d1=n/2，di+1=di/2，dt=1，t=log2n。排序希尔插入排序——步骤（1）首先选取一个整数d1n（n为待排序数据的个数），作为两个数据之间的距离，这样把全部数据分成d1个组，凡是距离为d1的数据放在一个组里，在各组内进行内部排序，直到各组排好序为止。（2）从上述的结果序列出发，再选择d2d1，重复上面的分组与排序工作。（3）依次取di+1di，直到dm=1（设一共需要m次分组），即所有数据放在一组中排序为止。此时，全部数据便按次序排好了。设待排序共有10个记录，其关键字分别为47,33,61,82,71,11,25,47,57,02，增量序列取值依次为5,3,1。希尔插入排序——过程排序希尔排序实质上还是一种插入排序，其主要特点是：每一趟以不同的增量进行排序。在每趟的插入排序中，记录的关键字是和同一组中的前一个关键字进行比较，所以关键字较小的记录在排序过程中是作跳跃式的移动。另外，由于开始时增量的取值较大，每组中记录较少，故排序比较快，随着增量值的逐步变小，每组中的记录逐渐变多，但由于此时记录已基本有序了，因次在进行最后一趟增量为1的插入排序时，只需作少量的比较和移动便可完成排序，从而提高了排序速度。希尔插入排序——特点排序希尔排序比直接插入排序的平均性能要好：在最好情况（原始记录按关键字有序排列）下，移动次数为0，比较次数界于n～n2之间。在最坏情况（原始记录按关键字逆序排列）下，移动次数和比较次数接近n2。在平均情况下，移动次数和比较次数在O（n1.3）左右，好于直接插入排序。希尔插入排序——性能效率排序例1.19希尔排序的程序#includestdio.h#definemax10intdata[max+1];intindex[max+1];inti;排序voidshell_sort(a)inta[max+1];{inti,j,n,m,skip;intalldone;for(i=1;i=max;i++)index[i]=i;skip=max;while(skip1){skip=skip/2;do{alldone=1;for(j=1;j=max-skip;j++){i=j+skip;n=index[i];m=index[j];if(a[n]a[m]){index[i]=m;index[j]=n;alldone=0;}}}while(alldone==0);}}排序main(){printf(请输入数据:);for(i=1;i=max;i++)scanf(%d,&data[i]);printf(\n);for(i=1;i=max;i++)printf(%d,data[i]);printf(\n);shell_sort(data);for(i=1;i=max;i++)printf(%d,data[index[i]]);printf(\n);}排序运行结果：请输入数据:194111174743133731231941111747431337312311131719233137414347希尔排序的分析较为复杂，因为它的时间是所取“增量”序列的函数，这涉及到一些数学上尚未解决的难题。增量序列可以有各种取法，但需注意：应使增量序列中的值没有除1以外的公因子，并且最后一个增量值必须等于1。2.希尔排序排序三、交换排序两两比较待排序记录的关键字，发现两个记录次序相反时即进行交换，直到没有反序的记录为止。冒泡排序快速排序排序假设在排序过程中，记录序列L.r[1..n]的状态为：第i趟冒泡排序无序序列L.r[1..n-i+1]有序序列L.r[n-i+2..n]n-i+1无序序列L.r[1..n-i]有序序列L.r[n-i+1..n]比较相邻记录，将关键字最大的记录交换到n-i+1的位置上7.3.1冒泡排序——基本思想和过程排序voidBubbleSort(SqList*L){for(i=L-length;i1;--i){for(j=1;ji;++j)if(L-r[j+1]L-r[j]){Swap(L-r[j],L-r[j+1]);}}}时间性能分析：比较次数:最坏(n-1)+(n-2)+...+1;最好：n-1移动次数:最坏：3((n-1)+(n-2)+...+1)；最好：07.3.1冒泡排序——算法和性能分析排序52319782553157989i=7i=6for(j=1;ji;j++)if(L-r[j+1]L-r[j])…13i=27.3.1冒泡排序——改进排序voidBubbleSort(SqList*L){i=L-length;while(i1){//定位第i个位置的记录lastExchangeIndex=1;for(j=1;ji;++j)if(L-r[j+1]L-r[j]){Swap(L-r[j],L-r[j+1]);lastExchangeIndex=j;}i=lastExchangeIndex;}}7.3.1冒泡排序——改进算法排序最好情况（记录按关键字有序排列）：只需进行一趟冒泡“比较”的次数：最坏情况（记录按关键字逆序排列）：需进行n-1趟冒泡“比较”的次数：0“移动”的次数：“移动”的次数：n-12)1()1(2nnini2)1(3)1(32nnini7.3.1冒泡排序——性能分析排序首先对无序的记录序列进行“一次划分”，通过一趟排序将待排序列分成两部分，使其中一部分记录的关键字均比另