排序算法描述之插入排序、希尔排序、快速排序、链式基数排序、二(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]调整为堆。

……

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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说公务员考试排序算法描述之插入排序、希尔排序、快速排序、链式基数排序、二(2)在线全文阅读。