C++ 归并排序(merge sort)案例详解

C++ 归并排序(merge sort)案例详解

核心思想：“分”与“合”。

主体流程

先将一个序列分成很多个不能再分割的子序列，将各个子序列分别排序后再将子序列合并。其实就是重复两个步骤：【1】分【2】合并。

首先是第一个小问题，怎么分?

比如说一个序列:12 ,23,1,44,233,10,9,8。我们先分成两段：12 ,23,1,44 和 233,10,9,8，

发现还能再分成4段：12 ,23 和 1,44------233,10 和 9,8。

再分成8段：12--23--1--44 和233--10--9--8。

这时候开始把子序列进行排序合并，一个元素就是有序的。所以不用排序。

合并成2个一组排序得到：12，23----1，44---10，233---8，9。

再合并成4个一组排序得到：1，12，23，44---8，9，10，233。

最后合并得到最终结果：1，8，9，10，12，23，44，233。

下面是分段的代码，用递归实现。

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); //再将二个有序数列合并

}

}

整体思路很清晰，还差一个小问题没解决，怎么合并？

现在问题就变成了怎么合并两个有序序列，思路是比较两个有序序列的第一个元素，谁小把谁放进最终序列的结尾，并把它从原来的队列里面删掉直到有个序列为空。

这时候另一个序列可能还有剩余的数据。没关系，因为他们本身是有序的，所以我们只要按顺序把他们添加到最终序列的尾部就好了。

这样两个有序序列就合并成一个有序序列了。

实现代码：

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

{

int i = first, j = mid + 1;

int http://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++];

}

整体测试代码：

#include

#include

#include

using namespace std;

//将有二个有序数列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, SUEXFDi0, n - 1, p);

delete[] p; //删除p临时数组

return true;

}

int main()

{

int i=0,temp=0;

int a[10]={0};

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

{

a[i]=rand();

cout<

}

cout<

MergeSort(a,10);

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

{

cout<

}

return 0;

}

}

cout<

MergeSort(a,10);

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

{

cout<

}

return 0;

}

MergeSort(a,10);

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

{

cout<

}

return 0;

}

}

return 0;

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。