排序算法描述之插入排序、希尔排序、快速排序、链式基数排序、二路归并排序、堆排序

排序算法描述之插入排序、希尔排序、快速排序、链式基数排序、二路归并排序、堆排序

排序算法描述之插入排序、希尔排序、快速排序、链式基数排序、二路归并排序、堆排序。 2010-02-13 18:31

1、插入排序的基本方法是：

每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。

(1)直接插入排序 (Insert Sort)

直接插入排序的基本思想是：

当插入第i (i≥ 1) 个对象时，前面的V[0], V[1], …, v[i-1]已经排好序。这时，用v[i]的关键码与v[i-1], v[i-2], …的关键码顺序进行比较，找到插入位置即将v[i]插入，原来位置上的对象向后顺移。

(2) 折半插入排序 (Binary Insert Sort)

折半插入排序的基本思想是：

设在顺序表中有一个对象序列V[0], V[1], …, v[n-1]。其中，v[0], V[1], …, v[i-1]是已经排好序的对象。在插入v[i]时，利用折半查找法寻找v[i]的插入位置。

(3)链表插入排序

1.链表插入排序的基本思想是：在每个对象的结点中增加一个链接指针数据成员 link。

2.对于存放于数组中的一组对象V[1], V[2], …, v[n]，若v[1], V[2], …, v[i-1]已经通过指针link，按其关键码的大小，从小到大链接起来，现在要插入v[i], i = 2, 3, …, n，则必须在前面i-1个链接起来的对象当中，循链顺序检测比较，找到v[i]应插入(或链入)的位置，把v[i]插入，并修改相应的链接指针。这样就可得到v[1], V[2], …, v[i]的一个通过链接指针排列好的链表。

3.如此重复执行，直到把v[n]也插入到链表中排好序为止。

(4)(缩小增量法)

属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序。

排序过程：先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止。

初始：d＝5

49 38 65 97 76 13 27 49* 55 04

|----------------------------|

38 27

|---------------------------|

65 49*

|----------------------------|

97 55

|--------------------------|

76 04

|-----------------------------|

一趟结果

13 27 49 55 04 49 38 65 97 76

d=3

13 27 49 55 04 49 38 65 97 76

排序算法描述之插入排序、希尔排序、快速排序、链式基数排序、二路归并排序、堆排序

|---------------|----------------|--------------------|

27 04 65

|----------------|----------------|

49 49 97

|----------------|-----------------|

二趟结果

13 04 49 38 27 49 66 65 97 76

d=1

13 04 49 38 27 49 66 65 97 76

|-----|-----|-----|-----|-----|-----|-----|-----|-----|

三趟结果

04 13 27 38 49 49 55 65 76 97

依照参考资料上的说法：“由于复杂的数学原因避免使用2的幂次步长，它能降低算法效率。”另外算法的复杂度为n的1.2次幂。因为非常复杂的原因（我也不知道过程），所以就不写了。

2、快速排序

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按这种方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此使整个数据变成有序序列。

假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据（也称基准元素），然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。一趟快速排序的算法是：

1）设置两个变量I、J，排序开始的时候I：=1，J：=N；

2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；

3）从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换；

4）从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换；

5）重复第3、4步，直到I=J；

例如：待排序的数组A的值分别是：（初始关键数据X：=49）

A[1] A[2] A[3] A[4] A[5] A[6] A[7]：

49 38 65 97 76 13 27

-|------------------------------------------------------|-

I(基准数据) J

进行第一次交换后： 27 38 65 97 76 13 49

排序算法描述之插入排序、希尔排序、快速排序、链式基数排序、二路归并排序、堆排序

-|------------------------------------------------------|-

I J

进行第二次交换后： 27 38 49 97 76 13 65

-|------------------------------------|-

I J

进行第三次交换后： 27 38 13 97 76 49 65

-|--------------------------|-

I J

( 按照算法的第五步将又一次执行算法的第三步从后开始找

进行第四次交换后： 27 38 13 49 76 97 65

( 按照算法的第四步从前面开始找大于X的值，97>49,两者交换，此时J：=4 )

此时再执行第三不的时候就发现I=J，从而结束一躺快速排序，那么经过一躺快速排序之后的结果是： 27 38 13 49 76 97 65，即所以大于49的数全部在49的后面，所以小于49 的数全部在49的前面。

快速排序就是递归调用此过程——在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列。

4、链式基数排序

链式基数排序是借助“分配”和“收集”两种操作对单逻辑关键字进行排序的一种内部排序方法。有的逻辑关键字可以看成是由若干个关键字复合而成。

5、二路归并排序

合并排序（MERGE SORT）是又一类不同的排序方法，合并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列，因此它又叫归并算法。它的基本思想就是假设数组A有N个元素，那么可以看成数组A是又N个有序的子序列组成，每个子序列的长度为1，然后再两两合并，得到了一个 N/2 个长度为2或1的有序子序列，再两两合并，如此重复，值得得到一个长度为N的有序数据序列为止，这种排序方法称为2—路合并排序。

例如数组A有7个数据，分别是： 49 38 65 97 76 13 27，那么采用归并排序算法的操作过程如图7所示：

初始值 [49] [38] [65] [97] [76] [13] [27]

看成由长度为1的7个子序列组成

第一次合并之后 [38 49] [65 97] [13 76] [27]

看成由长度为1或2的4个子序列组成

排序算法描述之插入排序、希尔排序、快速排序、链式基数排序、二路归并排序、堆排序

第二次合并之后 [38 49 65 97] [13 27 76]

看成由长度为4或3的2个子序列组成

第三次合并之后 [13 27 38 49 65 76 97]

合并算法的核心操作就是将一维数组中前后相邻的两个两个有序序列合并成一个有序序列。合并算法也可以采用递归算法来实现，形式上较为简单,但实用性很差。合并算法的合并次数是一个非常重要的量,根据计算当数组中有3到4个元素时,合并次数是2次,当有5到8个元素时,合并次数是3次,当有9到16个元素时,合并次数是4次，按照这一规律,当有N个子序列时可以推断出合并的次数是X(2 >=N,符合此条件的最小那个X)。

6、堆排序。

用最大堆排序的基本思想

① 先将初始文件R[1..n]建成一个最大堆，此堆为初始的无序区

② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key

③ 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。

……

直到无序区只有一个元素为止。

本文来源：https://www.bwwdw.com/article/fl2m.html