数据结构之归并排序的实例详解

归并排序

基本思想                                                                                                

归并排序是建立在二路归并和分治法的基础上的一个高效排序算法,将已有序的子序列合并,得到完全有序的序列;即先使每个子序

列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

将待排序序列R[0...n-1]看成是n个长度为1的有序序列,将相邻的有序表成对归并,得到n/2个长度为2的有序表;将这些有序序列

再次归并,得到n/4个长度为4的有序序列;如此反复进行下去,最后得到一个长度为n的有序序列。所以呢,我们总结一下归并排序

其实就只有两步:

分解:将有序序列不断地分裂,直到每个区间都只有一个数据为止.

合并:将两个区间合并为一个有序的区间,一直合并知道只有一个区间为止.

图是我偷来的,但是学习是认真的.

分解的过程我们很容易想明白的,用递归就可以.但是我们今天最主要的步骤是合并,你要将两个区间合并为一个有序的区间你会怎么思考呢?

这个非常简单,只要从比较二个数列的第一个数,谁小就先取谁,取了后就在对应数列中删除这个数。然后再进行比较,如果有数

列为空,那直接将另一个数列的数据依次取出即可。

代码实现:

//将有序数组a[]和b[]合并到c[]中

void MemeryArray(int a[], int n, int b[], int m, int c[])

{

int i, j, k;

i = j = k = 0;

while (i < n && j < m)

{

if (a[i] < b[j])

c[k++] = a[i++];

else

c[k++] = b[j++];

}

while (i < n)

c[k++] = a[i++];

while (j < m)

c[k++] = b[j++];

}

其实我们发现这种做法效率其实还是蛮高的,效率达到了O(N).现在我们解决了合并的问题.

现在总的来看一下归并排序的做法,通过先递归的分解数列(将数列分解成只有一个元素的区间),再合并数列就完成了归并排序。

代码实现                                                                                                 

//将有二个有序数列a[first...mid]和a[mid...last]合并。

void mergearray(int a[], int first, int mid, int last, int temp[])

{

int i = first, j = mid + 1;

int m = mid, n = last;

int k = 0;

while (i <= m && j <= n)

{

if (a[i] <= a[j])

temp[k++] = a[i++];

else

temp[k++] = a[j++];

}

while (i <= m)

temp[k++] = a[i++];

while (j <= n)

temp[k++] = a[j++];

for (i = 0; i < k; i++)

a[first + i] = temp[i];

}

void mergesort(int a[], int first, int last, int temp[])

{

if (first < last)

{

int mid = (first + last) / 2;

mergesort(a, first, mid, temp); //左边有序

mergesort(a, mid + 1, last, temp); //右边有序

mergearray(a, first, mid, last, temp); //再将二个有序数列合并

}

}

bool MergeSort(int a[], int n)

{

int *p = new int[n];

if (p == NULL)

return false;

mergesort(a, 0, n - 1, p);

delete[] p;

return true;

}

总结                                                                                                  

归并排序的效率是比较高的,设数列长为N,将数列分开成小数列一共要logN步,每步都是一个合并有序数列的过程,时间复杂度

可以记为O(N),故一共为O(N*logN)。因为归并排序每次都是在相邻的数据中进行操作,所以归并排序在O(N*logN)的几种排序方

法(快速排序,归并排序,希尔排序堆排序)也是效率比较高的。

算法名称  最差时间复杂度  平均时间复杂度  最优时间复杂度  空间复杂度  稳定性

归并排序    O(NlogN)    O(NlogN)              O(NlogN)       O(n)        稳定

所有排序当中用的最多的就是堆排序,快速排序,归并排序.

若从空间复杂度来考虑:首选堆排序,其次是快速排序,最后是归并排序。

若从稳定性来考虑,应选取归并排序,因为堆排序和快速排序都是不稳定的。

若从平均情况下的排序速度考虑,应该选择快速排序。

以上是 数据结构之归并排序的实例详解 的全部内容, 来源链接: utcz.com/z/346615.html

回到顶部