内部排序算法：归并排序

基本思想

n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：

  1. 初始状态：无序区为R[1..n]，有序区为空。
  2. 第1趟排序: 在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1] 交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
  3. ……
  4. 第i趟排序: 第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。 该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[i]交换，使R[1..i] 和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。

算法实现

归并排序算法，Java实现，代码如下所示：

01 public abstract class Sorter {
02 public abstract void sort(int[] array);
03 }
04
05 public class MergeSorter extends Sorter {
06
07 @Override
08 public void sort(int[] array) {
09 int[] auxArray = new int[array.length];
10 mergeSort(array, auxArray, 0, array.length - 1);
11 }
12
13 /**
14 * 基于分治思想，执行归并排序
15 * @param low 待排序数组下标下界
16 * @param high 待排序数组下标上界
17 */
18 private void mergeSort(int[] array, int[] auxArray, int low, int high) {
19 int dividedIndex = 0; // 分治位置索引变量
20 if (low < high) {
21 dividedIndex = (low + high) / 2; // 计算分治位置(采用简单的二分思想)
22 mergeSort(array, auxArray, low, dividedIndex); // 左侧递归归并排序
23 mergeSort(array, auxArray, dividedIndex + 1, high); // 右侧递归归并排序
24 merge(array, auxArray, low, dividedIndex, high); // 合并分治结果
25 }
26 }
27
28 private void merge(int[] array, int[] auxArray, int low, int dividedIndex, inthigh) {
29 int i = low; // 指向左半分区数组的指针
30 int j = dividedIndex + 1; // 指向右半分区数组的指针
31 int auxPtr = 0; // 指向辅助区数组的指针
32 // 合并两个有序数组：array[low..dividedIndex]与array[dividedIndex+1..high]。
33 while (i <= dividedIndex && j <= high) { // 将两个有序的数组合并，排序到辅助数组auxArray中
34 if (array[i] > array[j]) { // 左侧数组array[low..dividedIndex]中的array[i]大于右侧数组array[dividedIndex+1..high]中的array[j]
35 auxArray[auxPtr++] = array[j++];
36 } else {
37 auxArray[auxPtr++] = array[i++];
38 }
39 }
40 // 如果array[low..dividedIndex].length>array[dividedIndex+1..high].length，经过上面合并
41 // array[low..dividedIndex]没有合并完，则直接将array[low..dividedIndex]中没有合并的元素复制到辅助数组auxArray中去
42 while (i <= dividedIndex) {
43 auxArray[auxPtr++] = array[i++];
44 }
45 // 如果array[low..dividedIndex].length<array[dividedIndex+1..high].length，经过上面合并
46 // array[dividedIndex+1..high]没有合并完，则直接将array[dividedIndex+1..high]中没有合并的元素复制到辅助数组auxArray中去
47 while (j <= high) {
48 auxArray[auxPtr++] = array[j++];
49 }
50 // 最后把辅助数组auxArray的元素复制到原来的数组中去，归并排序结束
51 for (auxPtr = 0, i = low; i <= high; i++, auxPtr++) {
52 array[i] = auxArray[auxPtr];
53 }
54 }
55 }

归并排序算法，Python实现，代码如下所示：

01 class Sorter:
02 '''
03 Abstract sorter class, which provides shared methods being used by
04 subclasses.
05 '''
06 __metaclass__ = ABCMeta
07
08 @abstractmethod
09 def sort(self, array):
10 pass
11
12 class MergeSorter(Sorter):
13 '''
14 Merge sorter
15 '''
16
17 def sort(self, array):
18 length = len(array)
19 # initialize auxiliary list
20 auxiliary_list = [0 for x in range(length)]
21 self.__merge_sort(array, auxiliary_list, 0, length - 1)
22
23 def __merge_sort(self, array, auxiliary_list, low, high):
24 dividedIndex = 0
25 if low<high:
26 dividedIndex = (low + high) // 2
27 self.__merge_sort(array, auxiliary_list, low, dividedIndex)
28 self.__merge_sort(array, auxiliary_list, dividedIndex + 1, high)
29 self.__merge(array, auxiliary_list, low, dividedIndex, high)
30
31 def __merge(self, array, auxiliary_list, low, dividedIndex, high):
32 i = low
33 j = dividedIndex + 1
34 pointer = 0
35 while i<=dividedIndex and j<=high:
36 if array[i]>array[j]:
37 auxiliary_list[pointer] = array[j]
38 j = j + 1
39 else:
40 auxiliary_list[pointer] = array[i]
41 i = i + 1
42 pointer = pointer + 1
43 while i<=dividedIndex:
44 auxiliary_list[pointer] = array[i]
45 pointer = pointer + 1
46 i = i + 1
47 while j<=high:
48 auxiliary_list[pointer] = array[j]
49 pointer = pointer + 1
50 j = j + 1
51 # copy elements in auxiliary list to the original list
52 pointer = 0
53 i = low
54 while i<=high:
55 array[i] = auxiliary_list[pointer]
56 i = i + 1
57 pointer = pointer + 1

排序过程

假设待排序数组为array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}，数组大小为20，我们以该数组为例，执行归并排序的具体过程，如下所示：

01 [94,12,34,76,26,9,0,37,55,76, 37,5,68,83,90,37,12,65,76,49]
02 [94,12,34,76,26, 9,0,37,55,76]
03 [94,12,34, 76,26]
04 [94,12, 34]
05 [94, 12]
06 {12, 94}
07 {12,34, 94}
08 [76, 26]
09 {26, 76}
10 {12,26,34, 76,94}
11 [9,0,37, 55,76]
12 [9,0, 37]
13 [9, 0]
14 {0, 9}
15 {0,9, 37}
16 [55, 76]
17 {55, 76}
18 {0,9,37, 55,76}
19 {0,9,12,26,34, 37,55,76,76,94}
20 [37,5,68,83,90, 37,12,65,76,49]
21 [37,5,68, 83,90]
22 [37,5, 68]
23 [37, 5]
24 {5, 37}
25 {5,37, 68}
26 [83, 90]
27 {83, 90}
28 {5,37,68, 83,90}
29 [37,12,65, 76,49]
30 [37,12, 65]
31 [37, 12 ]
32 {12, 37 }
33 {12,37, 65 }
34 [76, 49 ]
35 {49, 76}
36 {12,37,49, 65,76}
37 {5,12,37,37,49, 65,68,76,83,90}
38 {0,5,9,12,12,26,34,37,37,37, 49,55,65,68,76,76,76,83,90,94}

上面示例的排序过程中，方括号表示“分解”操作过程中，将原始数组进行递归分解，直到不能再继续分割为止；花括号表示“归并”的过程，将上一步分解后的数组进行归并排序。因为采用递归分治的策略，所以从上面的排序过程可以看到，“分解”和“归并”交叉出现。

算法分析

  • 时间复杂度

对长度为n的文件，需进行FLOOR(logn) 趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。

  • 空间复杂度

需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。

  • 排序稳定性

归并排序是一种稳定的排序。

时间： 2024-10-08 20:11:28

内部排序算法：归并排序的相关文章

基于C++实现的各种内部排序算法汇总_C 语言

提起排序算法相信大家都不陌生,或许很多人已经把它们记得滚瓜烂熟,甚至随时可以写出来.是的,这些都是最基本的算法.这里就把各种内部排序算法总结归纳了一下,包括插入排序(直接插入排序,折半插入排序,希尔排序).交换排序(冒泡排序,快速排序).选择排序(简单选择排序,堆排序).2-路归并排序.(另:至于堆排序算法,前面已经有一篇文章针对堆排序的算法实现做了详细的描述) C++实现代码如下: /*******************************************************

常用内部排序算法之五：希尔排序

前言 在前面介绍常用内部排序算法的文章中,我们知道在简单排序算法中,直接插入排序算法的时间复杂度是要优于冒泡排序和简单选择排序的.而这里要讲的希尔排序则是优于直接插入排序的.而且希尔排序打破了原来简单排序中时间复杂度不能超过O(n2)的神话.这也是希尔排序伟大的地方,而且希尔排序不同于之前三种简单排序,希尔排序是以一个科学家的名字进行命名的. 希尔排序的原理 由于希尔排序是在直接插入排序的基础上进行改进的,所以为了更好理解希尔排序,需要再次将直接插入排序请出来.我们知道直接插入排序的基本思想是将

常用内部排序算法之二：快速排序

前言 快速排序可以说是内部排序算法中的高手,之所以称为快速排序,是因为快速排序算法从整体性能上讲是排序冠军.快速排序算法的思想是:通过一趟快速排序将待排序的记录分割成独立的两部分,其中一部分记录的关键字均比另一部分的记录的关键字小,则可分别对这两部分记录继续进行排序,达到整个记录有序.实现快速排序算法的核心是partition函数,这个函数的主要目的先选取当中的一个关键字(称为枢轴),然后尽可能将他放在一个位置,使得它左边的值都比它小,右边的值比它大. 快速排序算法实现 package com.

内部排序算法的总结

内部排序总结 这篇博文我们简要地总结下各种内部排序方法. 这10种排序算法中,前面7种属于建立在"比较"基础上的排序算法,通过决策树已经证明,任何基于比较进行的排序算法的时 间复杂度不可能再优于O(n*logn).后面3种不是建立在比较的基础上的,因此,可以达到线性运行时间. 下面我们给出各种排序方法的时空复杂度的表格(属于自己总结,有不对的地方,希望大家指正或补充). 返回栏目页:http://www.bianceng.cnhttp://www.bianceng.cn/Program

内部排序：归并排序和快速排序

前言   之所以把归并排序和快速排序放在一起探讨,很明显两者有一些相似之处:这两种排序算法都采用了分治的思想.下面来逐个分析其实现思想. 归并排序 实现思想 归并的含义很明显就是将两个或者两个以上的有序表组合成一个新的有序表.归并排序中一般所用到的是2-路归并排序,即将含有n个元素的序列看成是n个有序的子序列,每个子序列的长度为1,而后两两合并,得到n/2个长度为2或1的有序子序列,再进行两两合并...直到最后由两个有序的子序列合并成为一个长度为n的有序序列.2-路归并的核心操作是将一维数组中前

常用内部排序算法之三：堆排序

前言 堆排序是以堆为原型的排序.堆首先是一棵二叉树,具有以下两个性质:每个节点的值大于或者等于其左右孩子结点的值,称为大顶堆:或者每个节点的值都小于或者等于其左右孩子结点的值,称为小顶堆.从这个定义中可以发现,堆得根节点要么是最大值要么是最小值.实现堆排序的基本思想是:将待排序的序列构造成一个大顶堆或者小顶堆.此时整个堆满足根节点是最大值或者最小值.将根节点移走,并与堆数组的最后一个值进行交换,这样的话最后一个值就是最大值或者最小值了.然后将剩余n-1(假设原来总共有n个元素)未排序的序列重新构

Java排序算法 归并排序

归并排序(Merge)是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的.然后再把有序子序列合并为整体有序序列. 归并排序是建立在归并操作上的一种有效的排序算法.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为2-路归并. 归并排序算法稳定,数组需要O(n)的额外空间,链表需要O(log(n))的

内部排序算法：基数排序

基本思想 基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较.由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数. 基数排序可以采用两种方式: LSD(Least Significant Digital):从待排序元素的最右边开始计算(如果是数字类型,即从最低位个位开始). MSD(Most Significant Digital):从待排序元素的最左边开始计算(如果是数字类型,即从最高位开始). 我们以L

常用内部排序算法之四：简单选择排序、直接插入排序和冒泡排序

前言 之所以把这三类算法放在一块,是因为除此之外的算法都是在这三类算法的基础上进行优化的.简单选择排序的思想是每一趟n−i+1(i=1,2,...,n−1)个记录中选择最小的记录作为有序序列的第i个记录.直接插入排序的思想是将一个记录插入到已经排好序的有序序列中,从而得到一个新的.记录数增加1的有序表.冒泡排序的算法思想是不断在交换,通过交换完成最终的排序,每一趟的交换就会把最大的记录取出来,下一趟则会把第二大的记录取出来,这样每进行一趟交换就把一个记录取出来的过程称为冒泡. 简单选择排序算法