各种基本排序算法思路介绍.doc

各种基本排序算法思路介绍1.冒泡排序：冒泡排序的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复以上过程，仍从第一对数开始比较(因为可能由于第2个数和第3个数的交换，使得第1个数不再大于第2个数)，将小数放前，大数放后，一直比较到最小数前的一对相邻数，将小数放前，大数放后，第二趟结束，在倒数第二个数中得到一个新的最小数。如此下去，直至最终完成排序。由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。冒泡排序法的改进比如用冒泡排序将4、5、7、1、2、3这6个数排序。在该列中，第二趟排序结束后，数组已排好序，但计算机此时并不知道已经反排好序，计算机还需要进行一趟比较，如果这一趟比较，未发生任何数据交换，则知道已排序好，可以不再进行比较了。因而第三趟比较还需要进行，但第四、五趟比较则是不必要的。为此，我们可以考虑程序的优化。为了标志在比较中是否进行了，设一个布尔量flag。在进行每趟比较前将flag置成true。如果在比较中发生了数据交换，则将flag置为false，在一趟比较结束后，再判断flag，如果它仍为true(表明在该趟比较中未发生一次数据交换)则结束排序，否则进行下一趟比较。性能分析若记录序列的初始状态为正序，则冒泡排序过程只需进行一趟排序，在排序过程中只需进行n-1次比较，且不移动记录；反之，若记录序列的初始状态为逆序，则需进行n(n-1)/2次比较和记录移动。因此冒泡排序总的时间复杂度为O(n*n)。2.简单选择：每一趟从待排序的数据元素中选出最小(或最大)的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法。n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：初始状态：无序区为R1.n，有序区为空。第1趟排序在无序区R1.n中选出关键字最小的记录Rk，将它与无序区的第1个记录R1交换，使R1.1和R2.n分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。第i趟排序第i趟排序开始时，当前有序区和无序区分别为R1.i-1和R(1in-1)。该趟排序从当前无序区中选出关键字最小的记录Rk，将它与无序区的第1个记录R交换，使R1.i和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。3.插入排序：有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法-插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为()。是稳定的排序方法。插入算法(insertion sort)把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外，而第二部分就只包含这一个元素。在第一部分排序后，再把这个最后元素插入到此刻已是有序的第一部分里的正确位置中。插入排序由于是像已经排好序的队列中插入，所以有好几种方式，包括：直接插入排序，折半插入排序，链表插入排序，Shell排序。4.希尔排序：希尔排序(Shell Sort)是插入排序的一种。因D.L.Shell于1959年提出而得名。基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2 d1重复上述的分组和排序，直至所取的增量dt=1(dt dt-ld2 d1)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上为分组的直接插入排序方法。算法分析1.增量序列的选择Shell排序的执行时间依赖于增量序列。好的增量序列的共同特征：最后一个增量必须为1；应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。有人通过大量的实验，给出了目前较好的结果：当n较大时，比较和移动的次数约在nl.25到1.6n1.25之间。2.Shell排序的时间性能优于直接插入排序希尔排序的时间性能优于直接插入排序的原因：当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。因此，希尔排序在效率上较直接插人排序有较大的改进。3.稳定性希尔排序是不稳定的。5.快速排序：快速排序(QuickSort)是对冒泡排序的一种改进。由C.A.R.Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。设要排序的数组是A0AN-1，首先任意选取一个数据(通常选用第一个数据)作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。一趟快速排序的算法是：1)设置两个变量I、J，排序开始的时候：I=1，J=N-1；2)以第一个数组元素作为关键数据，赋值给X，即X=A0；3)从J开始向前搜索，即由后开始向前搜索(J=J-1)，找到第一个小于X的值，让该值与X交换；4)从I开始向后搜索，即由前开始向后搜索(I=I+1)，找到第一个大于X的值，让该值与X交换；5)重复第3、4步，直到I=J；变种算法：快速排序(Quicksort)有三个值得一提的变种算法，这里进行一些简要介绍：平衡快排(Balanced quicksort)：每次尽可能地选择一个能够代表中值的元素作为关键数据，然后遵循普通快排的原则进行比较、替换和递归。外部快排(External quicksort)：与普通快排不同的是，关键数据是一段buffer，首先将之前和之后的M/2个元素读入buffer并对该buffer中的这些元素进行排序，然后从被排序数组的开头(或者结尾)读入下一个元素，假如这个元素小于buffer中最小的元素，把它写到最开头的空位上；假如这个元素大于buffer中最大的元素，则写到最后的空位上；否则把buffer中最大或者最小的元素写入数组，并把这个元素放在buffer里。保持最大值低于这些关键数据，最小值高于这些关键数据，从而避免对已经有序的中间的数据进行重排。完成后，数组的中间空位必然空出，把这个buffer写入数组中间空位。然后递归地对外部更小的部分，循环地对其他部分进行排序。三路基数快排(Three-way radix quicksort，也称作multikey quicksort、multi-key quicksort)：结合了基数排序(radix sort，如一般的字符串比较排序就是基数排序)和快排的特点，是字符串排序中比较高效的算法。该算法被排序数组的元素具有一个特点，即multikey，如一个字符串，每个字母可以看作是一个key。算法每次在被排序数组中任意选择一个元素作为关键数据，首先仅考虑这个元素的第一个key(字母)，然后把其他元素通过key的比较分成小于、等于、大于关键数据的三个部分。然后递归地基于这一个key位置对小于和大于部分进行排序，基于下一个key对等于部分进行排序。6.堆排序：起源1991年计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特弗洛伊德(Robert W.Floyd)和威廉姆斯(J.Williams)在1964年共同发明了著名的堆排序算法(Heap Sort)定义n个关键字序列Kl，K2，Kn称为(Heap)，当且仅当该序列满足如下性质(简称为堆性质)：(1)kiK2i且kiK2i+1或(2)KiK2i且kiK2i+1(1in)若将此序列所存储的向量R1.n看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。(即如果按照线性存储该树，可得到一个不下降序列或不上升序列)【例】关键字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分别满足堆性质(1)和(2)，故它们均是堆，其对应的完全二叉树分别如小根堆示例和大根堆示例所示。大根堆和小根堆：根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆，又称最小堆。根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆，又称最大堆。注意：堆中任一子树亦是堆。以上讨论的堆实际上是二叉堆(Binary Heap)，类似地可定义k叉堆。特点堆排序(HeapSort)是一树形选择排序。堆排序的特点是：在排序过程中，将Rl.n看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系(参见二叉树的顺序存储结构)，在当前无序区中选择关键字最大(或最小)的记录。堆排序与直接选择排序的区别直接选择排序为了从R1.n中选出关键字最小的记录，必须进行n-1次比较，然后在R2.n中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。堆排序可通过树形结构保存部分比较结果，可减少比较次数。堆排序堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。(1)用大根堆排序的基本思想先将初始文件R1.n建成一个大根堆,此堆为初始的无序区再将关键字最大的记录R1(即堆顶)和无序区的最后一个记录Rn交换，由此得到新的无序区R1.n-1和有序区Rn，且满足R1.n-1.keysRn.key由于交换后新的根R1可能违反堆性质，故应将当前无序区R1.n-1调整为堆。然后再次将R1.n-1中关键字最大的记录R1和该区间的最后一个记录Rn-1交换，由此得到新的无序区R1.n-2和有序区Rn-1.n，且仍满足关系R1.n-2.keysRn-1.n.keys，同样要将R1.n-2调整为堆。直到无序区只有一个元素为止。(2)大根堆排序算法的基本操作：初始化操作：将R1.n构造为初始堆；每一趟排序的基本操作：将当前无序区的堆顶记录R1和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。注意：只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。堆排序算法(C+描述)void HeapSort(SeqIAst R)/对R1.n进行堆排序，不妨用R0做暂存单元int i；BuildHeap(R)；/将R1-n建成初始堆for(i=n；i 1；i-)/对当前无序区R1.i进行堆排序，共做n-1趟。R0=R1；R1=R；R=R0；/将堆顶和堆中最后一个记录交换Heapify(R，1，i-1)；/将R1.i-1重新调整为堆，仅有R1可能违反堆性质/endfor/HeapSort因为构造初始堆必须使用到调整堆的操作，先讨论Heapify的实现。Heapify函数思想方法每趟排序开始前Rl.i是以R1为根的堆，在R1与Ri交换后，新的无序区R1.i-1中只有R1的值发生了变化，故除R1可能违反堆性质外，其余任何结点为根的子树均是堆。因此，当被调整区间是Rlow.high时，只须调整以Rlow为根的树即可。筛选法调整堆Rlow的左、右子树(若存在)均已是堆，这两棵子树的根R2low和R2low+1分别是各自子树中关键字最大的结点。若Rlow.key不小于这两个孩子结点的关键字，则Rlow未违反堆性质，以Rlow为根的树已是堆，无须调整；否则必须将Rlow和它的两个孩子结点中关键字较大者进行交换，即Rlow与Rlarge(Rlarge.key=max(R2low.key，R2low+1.key)交换。交换后又可能使结点Rlarge违反堆性质，同样由于该结点的两棵子树(若存在)仍然是堆，故可重复上述的调整过程，对以Rlarge为根的树进行调整。此过程直至当前被调整的结点已满足性质，或者该结点已是叶子为止。上述过程就象过筛子一样，把较小的关键字逐层筛下去，而将较大的关键字逐层选上来。因此，有人将此方法称为筛选法。算法实例：#include stdio.h#include stdlib.h inline int LEFT(int i)；inline int RIGHT(int i)；inline int PATENT(int i)；void MAX_HEAPIFY(int A,int heap_size,int i)；void BUILD_MAX_HEAP(int A,int heap_size)；void HEAPSORT(int A,int heap_size)；void output(int A,int size)；int main()FILE*fin；int m,size,i；fin=fopen(array.in,r)；int*a；fscanf(fin,%d,size)；a=(int*)malloc(size+1)；a0=size；for(i=1；i=size；i+)fscanf(fin,%d,&m)；ai=m；HEAPSORT(a,a0)；printf($The Result$n)；output(a,a0)；free(a)；return 0；inline int LEFT(int i)return 2*i；inline int RIGHT(int i)return 2*i+1；inline int PARENT(int i)return i/2；void MAX_HEAPIFY(int A,int heap_size,int i)int temp,largest,l,r；largest=i；l=LEFT(i)；r=RIGHT(i)；if(l=heap_size)&(AlAlargest)largest=l；if(r=heap_size)&(ArAlargest)largest=r；if(largest！=i)temp=Alargest；Alargest=Ai；Ai=temp；MAX_HEAPIFY(Ai,heap_size,largest)；void BUILD_MAX_HEAP(int A,int heap_size)int i；for(i=heap_size/2；i=1；i-)MAX_HEAPIFY(A,heap_size,i)；void HEAPSORT(int A,int heap_size)int i；BUILD_MAX_HEAP(A,heap_size)；for(i=heap_size；i=2；i-)int temp；temp=A1；A1=Ai；Ai=temp；MAX_HEAPIFY(A,i-1,1)；void output(int A,int size)int i=1；FILE*out=fopen(result.in,w+)；for(；i=size；i+)printf(%d,Ai)；fprintf(out,%d,Ai)；printf(n)；7.基数排序：基数排序法(radix sort)则是属于分配式排序(distribution sort)，基数排序法又称桶子法(bucket sort)或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些桶中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O(nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。解法：基数排序的方式可以采用LSD(Least significant digital)或MSD(Most significant digital)，LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。以LSD为例，假设原来有一串数值如下所示：73,22,93,43,55,14,28,65,39,81首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：0 181 222 373 93 43 414 555 65 67 828 939接下来将这些桶子中的数值重新串接起来，成为以下的数列：81,22,73,93,43,14,55,65,28,39接着再进行一次分配，这次是根据十位数来分配：0 114 222 28 339 443 555 665 773 881 993接下来将这些桶子中的数值重新串接起来，成为以下的数列：14,22,28,39,43,55