数据结构之归并排序的实例详解
|
归并排序 基本思想 归并排序是建立在二路归并和分治法的基础上的一个高效排序算法,将已有序的子序列合并，得到完全有序的序列；即先使每个子序 列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 将待排序序列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 temp[])
{
if (first < last)
{
int mid = (first + last) / 2;
mergesort(a,first,mid,temp); //左边有序
mergesort(a,mid + 1,last,temp); //右边有序
mergearray(a,temp); //再将二个有序数列合并
}
}
bool MergeSort(int a[],int n)
{
int *p = new int[n];
if (p == NULL)
return false;
mergesort(a,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) 稳定 所有排序当中用的最多的就是堆排序，快速排序，归并排序. 若从空间复杂度来考虑：首选堆排序，其次是快速排序，最后是归并排序。 若从稳定性来考虑，应选取归并排序，因为堆排序和快速排序都是不稳定的。 若从平均情况下的排序速度考虑，应该选择快速排序。 以上就是数据结构中归并排序的实例详解，如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！ （编辑：武汉站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
