净水机压力罐用充气吗:【排序结构4】 归并排序

归并排序 O(N*logN) 是另一种效率很高的排序方法。"归并"的含义就是将两个或两个以上的有序表组合成一个有序表。加入两个有序表的长度分别为m、n，则一次归并的时间复杂度为O(m+n)。

我们可以用"归并"的思想来实现排序。假如待排序列含有n个关键字，则可看成是n个有序的子序列，每个序列长度为1，然后两两归并，得到[n/2]个长度为2或1的子序列，在两两归并....，知道得到一个长度为n的有序序列为止。这就是2-路归并算法。

下图就是2-路归并排序的一个例子：

  
我们可以用分治的思想解决归并排序，给定一个有N个关键字的有序序列，分治法的步骤如下：

(1)划分： 如果S中有1个元素，则直接返回S，因为它已经有序了。否则(S中至少有两个元素)，把它们分别放入两个序列S1和S2中，S1和S2各包含大约S中的一半元素，即S1包含S中的前[N/2]个元素，S2包含S中的后[N/2]个元素。

(2)递归：递归求解子问题S1和S2。

(3)求解：归并有序序列S1和S2，使得他们成为一个有序序列，将其中的元素放回S中。Java代码

1. #include
2. #include
3. /************************
4. * 归并排序 Merge Sort *
5. ***********************/
6. class MergeSort{
7. public:
8. //递增排序
9. static void inc_sort(int keys[], int size);
10. private:
11. //归并排序算法
12. static void merge_sort(int raw[], int *merged, int s, int t);
13. //归并
14. static void merge(int raw[], int *merged, int si, int mi, int ti);
15. };
17. void MergeSort:: merge(int raw[], int *merged, int si, int mi, int ti){
19. //把已近排序号的si-mi，mi-ti两个序列赋值给raw
20. for(int t=si;t<=ti;t++)
21. raw[t]=merged[t];
22. //归并
23. int i=si,j=mi+1,k=si;
24. for(;i<=mi&&j<=ti;){
25. if(raw[i]<=raw[j]) merged[k++]=raw[i++];
26. else merged[k++]=raw[j++];
27. }
28. if(i<=mi)
29. for(int x=i;x<=mi;)
30. merged[k++]=raw[x++];
31. if(j<=ti)
32. for(int y=j;y<=ti;)
33. merged[k++]=raw[y++];
34. }
35. //划分
36. void MergeSort:: merge_sort(int raw[], int *merged, int s, int t){
38. if(s==t) merged[s]=raw[s];
39. else{
40. int m=(s+t)/2;
41. MergeSort::merge_sort(raw, merged, s, m);
42. MergeSort::merge_sort(raw, merged, m+1,t);
43. MergeSort::merge(raw, merged, s,m,t);
44. }
45. }
47. void MergeSort:: inc_sort(int keys[],int size){
49. int * merged=(int *)malloc(size*sizeof(int));
50. MergeSort::merge_sort(keys,merged,0,size-1);
51. //打印排序结果
52. for(int i=0;i
53. cout<
54. cout<
56. free(merged);
57. }
58. //Test MergeSort
59. void main(){
60. int raw[]={49,38,65,97,76,13,27,49};
61. int size=sizeof(raw)/sizeof(int);
62. MergeSort::inc_sort(raw,size);
63. }

#include#include/************************   * 归并排序 Merge Sort  *    ***********************/   class MergeSort{public://递增排序static void inc_sort(int keys[], int size);private://归并排序算法static void merge_sort(int raw[], int *merged, int s, int t);//归并static void merge(int raw[], int *merged, int si, int mi, int ti);};void MergeSort:: merge(int raw[], int *merged, int si, int mi, int ti){//把已近排序号的si-mi，mi-ti两个序列赋值给rawfor(int t=si;t<=ti;t++)raw[t]=merged[t];//归并int i=si,j=mi+1,k=si;for(;i<=mi&&j<=ti;){if(raw[i]<=raw[j]) merged[k++]=raw[i++];else merged[k++]=raw[j++];}if(i<=mi)for(int x=i;x<=mi;)merged[k++]=raw[x++];if(j<=ti)for(int y=j;y<=ti;)merged[k++]=raw[y++];}//划分void MergeSort:: merge_sort(int raw[], int *merged, int s, int t){if(s==t) merged[s]=raw[s];else{int m=(s+t)/2;MergeSort::merge_sort(raw, merged, s, m);MergeSort::merge_sort(raw, merged, m+1,t);MergeSort::merge(raw, merged, s,m,t);}}void MergeSort:: inc_sort(int keys[],int size){int * merged=(int *)malloc(size*sizeof(int));MergeSort::merge_sort(keys,merged,0,size-1);//打印排序结果for(int i=0;i
代价分析：
上图可以看出，一个N关键字的序列，两两归并可以构造一棵高度为[logN]的归并排序树。而每一次归并的时间复杂度为O(m+n)。因此每一趟归并的时间复杂度为O(N)，如上图。归并排序算法的总时间复杂度为O(N*logN) 。其所需要的辅助空间就是一个能容纳中间合并结果的数量为N的连续空间。因此空间复杂度为O(N) 。是稳定排序方法 。