# 程序员面试题精选--归并排序

2013-03-23 06:30:02 阅读( 87 )

1、分解：将n个元素分成各含n/2个元素的子序列

2、解决：用合并排序法对两个子序列递归的排序

3、合并：合并两个已排序的子序列以得到排序结果。

cpp] view plaincopy
01.#include<iostream>
02.using namespace std;
03.
04.#define MAX 0x7FFFFFFF //最大可能值，用于哨兵
05.
06.void Merge(int *A, int low, int mid, int high)
07.{
08. if(A == NULL)return;
09.
10. int n1 = mid-low+1;
11. int n2 = high-mid;
12. int *left = new int[n1+1];
13. int *right = new int[n2+1];
14. for(int i=0; i<n1; i++)
15. left[i] = A[i+low];
16. for(int j=0; j<n2; j++)
17. right[j] = A[j+mid+1];
18.
19. //哨兵元素
20. left[n1] = MAX;
21. right[n2] = MAX;
22.
23. //将left[low...mid]和right[mid+1, high]共high-low+1 个元素有序合并
24. int i=0,j=0;
25. for(int k=low; k<=high; k++)
26. {
27. if(left[i]<=right[j])
28. {
29. A[k] = left[i];
30. i++;
31. }
32. else
33. {
34. A[k] = right[j];
35. j++;
36. }
37. }
38.}
39.
40.//归并排序
41.void Merge_Sort(int *A, int low, int high)
42.{
43. if(low<high)
44. {
45. int mid = (low+high)/2;
46. Merge_Sort(A, low, mid);
47. Merge_Sort(A, mid+1, high);
48. Merge(A, low, mid, high);
49. }
50.}
51.
52.void Print(int *A, int low, int high)
53.{
54. for(int i=low; i<=high; i++)
55. cout<<A[i]<<" ";
56. cout<<endl;
57.}
58.
59.int main()
60.{
61. int array[11] = {3, 5, 1, 9, 20, 4, 13, 6, 4, 12, 8};
62. int low = 0;
63. int high = sizeof(array)/sizeof(int)-1;
64. Merge_Sort(array, low, high);
65. Print(array, low, high);
66. system("pause");
67. return 0;
68.}

（1）稳定性

（2）存储结构

（3）时间复杂度

（4）空间复杂度