微信

使用微信服务,更方便

职友集>程序员面试题 > 程序员面试题精选--归并排序

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

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

2226人 收藏本页

标签:程序员面试题

采用分治策略

一般有三个步骤:

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

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

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

在归并排序时,其长度为1时递归结束。单个元素被视为是已排序好的。

参考代码如下:

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)时间复杂度

对长度为n的文件,需进行 趟二路归并,每趟归并的时间为O(n),故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。

(4)空间复杂度

需要一个辅助向量来暂存两有序子文件归并的结果,故其辅助空间复杂度为O(n),显然它不是就地排序。

下一篇:我的算法路【感想篇】 - Codeforces, USACO

上一篇:字符串的组合 --程序员面试题精选

亲~ 如果您有更好的答案 可在评论区发表您独到的见解。

您想查看更多的信息: 面试题