我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:金算盘高手论坛799222 > 排序 >

八大排序算法讲解与比较

归档日期:06-18       文本归类:排序      文章编辑:爱尚语录

  所谓排序,就是根据排序码的递增或者递减顺序把数据元素依次排列起来,使一组任意排列的元素变为一组按其排序码线性有序的元素。本文将介绍八种最为经典常用的内部排序算法的基本思想与实现,包括插入排序(直接插入排序,希尔排序)、选择排序(直接选择排序,堆排序)、交换排序(冒泡排序,快速排序)、归并排序、分配排序(基数排序),并给出各种算法的时间复杂度、空间复杂度和稳定性。

  若读者需要本博文相关完整代码,请移步我的Github自行获取,项目名为 DataStructure(具体算法实现在cn.tju.edu.rico.sort包),项目链接地址为:。

  所谓排序,就是根据排序码的递增或者递减顺序把数据元素依次排列起来,使一组任意排列的元素变为一组按其排序码线性有序的元素。本文将介绍八种最为经典常用的内部排序算法,包括插入排序(直接插入排序,希尔排序)、选择排序(直接选择排序,堆排序)、交换排序(冒泡排序,快速排序)、归并排序、分配排序(基数排序)。实际上,无论是基本排序方法(直接插入排序,直接选择排序,冒泡排序),还是高效排序方法(快速排序,堆排序,归并排序)等,它们各有所长,都拥有特定的使用场景。因此,在实际应用中,我们必须根据实际任务的特点和各种排序算法的特性来做出最合适的选择。一般地,我们衡量一个算法的指标包括:

  稳定性 (该算法的实现是否可以保证排序后相等元素的初始顺序,只要该算法存在一种实现可以保证这种特征,那么该算法就是稳定的)

  笔者将在本文着重探讨上述八种排序算法的思想和实现,并就各算法根据以上指标进行分析和归类,以便进一步熟悉它们各自的应用场景。

  插入排序的基本思想:每步将一个待排序元素,按其排序码大小插入到前面已经排好序的一组元素中,直到元素全部插入为止。在这里,我们介绍三种具体的插入排序算法:直接插入排序,希尔排序与折半插入排序。

  直接插入排序的思想:当插入第i(i=1)个元素时,前面的V[0],…,V[i-1]等i-1个 元素已经有序。这时,将第i个元素与前i-1个元素V[i-1],…,V[0]依次比较,找到插入位置即将V[i]插入,同时原来位置上的元素向后顺移。在这里,插入位置的查找是顺序查找。直接插入排序是一种稳定的排序算法,其实现如下:

  * Deion: 在有序序列中不断插入新的记录以达到扩大有序区到整个数组的目的

  * 时间复杂度:最好情形O(n),平均情形O(n^2),最差情形O(n^2)

  希尔排序的思想:设待排序序列共n个元素,首先取一个整数gapn作为间隔,将全部元素分为间隔为gap的gap个子序列并对每一个子序列进行直接插入排序。然后,缩小间隔gap,重复上述操作,直至gap缩小为1,此时所有元素位于同一个序列且有序。由于刚开始时,gap较大,每个子序列元素较少,排序速度较快;待到排序后期,gap变小,每个子序列元素较多,但大部分元素基本有序,所以排序速度仍较快。一般地,gap取 (gap/3 + 1)。希尔排序是一种不稳定的排序方法,其实现如下:

  * Deion: 分别对间隔为gap的gap个子序列进行直接插入排序,不断缩小gap

  折半插入排序的思想:当插入第i(i=1)个元素时,前面的V[0],…,V[i-1]等i-1个 元素已经有序。这时,折半搜索第i个元素在前i-1个元素V[i-1],…,V[0]中的插入位置,然后直接将V[i]插入,同时原来位置上的元素向后顺移。与直接插入排序不同的是,折半插入排序比直接插入排序明显减少了关键字之间的比较次数,但是移动次数是没有改变。所以,折半插入排序和插入排序的时间复杂度相同都是O(N^2),但其减少了比较次数,所以该算法仍然比直接插入排序好。折半插入排序是一种稳定的排序算法,其实现如下:

  * Deion: 折半搜索出插入位置,并直接插入;与直接插入搜索的区别是,后者

  选择排序的基本思想:每一趟 (例如第i趟,i = 0,1,…)在后面第n-i个待排序元素中选出最小元素作为有序序列的第i个元素,直到第n-1趟结束后,所有元素有序。在这里,我们介绍两种具体的选择排序算法:直接选择排序与堆排序。

  直接选择排序的思想:第一次从R[0]~R[n-1]中选取最小值,与R[0]交换,第二次从R1~R[n-1]中选取最小值,与R1交换,….,第i次从R[i-1]~R[n-1]中选取最小值,与R[i-1]交换,…..,第n-1次从R[n-2]~R[n-1]中选取最小值,与R[n-2]交换,总共通过n-1次,得到一个按排序码从小到大排列的有序序列。直接选择排序是一种不稳定的排序算法,其实现如下:

  堆排序的核心是堆调整算法。首先根据初始输入数据,利用堆调整算法shiftDown()形成初始堆;然后,将堆顶元素与堆尾元素交换,缩小堆的范围并重新调整为堆,如此往复。堆排序是一种不稳定的排序算法,其实现如下:

  * Title: 堆排序(选择排序),升序排序(最大堆),依赖于初始序列

  * Deion: 现将给定序列调整为最大堆,然后每次将堆顶元素与堆尾元素

  交换排序的基本思想:根据序列中两个元素的比较结果来对换这两个记录在序列中的位置,也就是说,将键值较大的记录向序列的尾部移动,键值较小的记录向序列的前部移动。

  冒泡排序的思想:根据序列中两个元素的比较结果来对换这两个记录在序列中的位置,将键值较大的记录向序列的尾部移动,键值较小的记录向序列的前部移动。因此,每一趟都将较小的元素移到前面,较大的元素自然就逐渐沉到最后面了,也就是说,最大的元素最后才能确定,这就是冒泡。冒泡排序是一种稳定的排序算法,其实现如下:

  * Title: 交换排序中的冒泡排序 ,一般情形下指的是优化后的冒泡排序,最多

  * Deion:因为越大的元素会经由交换慢慢浮到数列的顶端(最后位置),

  * 时间复杂度:最好情形O(n),平均情形O(n^2),最差情形O(n^2)

本文链接:http://jdockfish.com/paixu/443.html