《算法设计与分析-排序》实验报告

排序问题。

1、归并排序法

1）基本思想

将一个长度为n的数组不停地对半划分成n个数组，对这些小的数组进行排序并归并到一个长度为n的数组。

2）复杂度分析

由于存在如下递推式：

T(n) = 1; n=1

T(n) = 2T(n/2)+n; n>1

由上次作业可知，复杂度为O(nlog2n)

2、快速排序法

1）基本思想

对一个长度为n的数组a[n]，取第一位元素（记为s），剩余的元素大于a[s]的放s右边，小于a[s]的放s的左边。

然后对s的左右两边继续重复上述操作，直至左右两边元素数量为1。

2）复杂度分析

最好情况下，每次左边和右边的元素数量相等，此时有何上面一样的递推式，时间复杂度为O(nlog2n)。

最坏情况下，每次左边为0，右边为n-1。此时要算1+2+3+…+(n-1)次也就是1/2*n*(n-1)次，复杂度为O(n2)。

1、归并排序法

1. #include

3. using namespace std;

5. //对数组a[s]~a[m] 与 a[m+1]~a[e]进行归并

6. void merge(int a[], int b[], int s, int m, int e){

7. int i=s; //第一个数组起始下标

8. int j=m+1; //第二个数组起始下标

9. int k=s; //存入b数组的起始下标

10.

11. //从小到大插入

12. while(i<=m && j<=e){

13. if(a[i]<=a[j]){

14. b[k] = a[i];

15. k++;

16. i++;

17. }else{

18. b[k] = a[j];

19. k++;

20. j++;

21. }

22. }

23.

24. //未插完

25. while(i<=m){

26. b[k] = a[i];

27. k++;

28. i++;

29. }

30. while(j<=e){

31. b[k] = a[j];

32. k++;

33. j++;

34. }

35. }

36.

37. //归并排序

38. void mergeSort(int a[], int s, int e){

39. int m, b[10000];

40. if(s==e)

41. return;

42. else{

43. m = (s+e)/2;

44. mergeSort(a,s,m);

45. mergeSort(a,m+1,e);

46. merge(a,b,s,m,e);

47. for(int i=s; i<=e; ++i)

48. a[i]=b[i];

49. }

50. }

51.

52. int main(){

53. int a[10000];

54. for(int i=0; i<10000; ++i)

55. a[i] = rand();

56. mergeSort(a,0,9999);

57. for(int i=0; i<10000; ++i)

58. cout<

59. }

2、快速排序法

1. #include

3. using namespace std;

5. //调整序列，大的放右边小的放左边

6. int adjust(int a[], int front, int rear){

7. int i=front, j=rear;

8. int x = a[front];

9. while(i

10. while(a[j]>=x && i

11. j--;

12. a[i] = a[j];

13. while(a[i]<=x && i

14. i++;

15. a[j] = a[i];

16. }

17. a[i] = x;

18. return i;

19. }

20.

21. //快速排序

22. void quickSort(int a[],int front, int rear){

23. if(front

24. int empty = adjust(a,front,rear);

25. quickSort(a,front,empty-1);

26. quickSort(a,empty+1,rear);

27. }

28. }

29.

30. int main()

31. {

32. int a[10000];

33. for(int i=0; i<10000; ++i)

34. a[i] = rand();

35. quickSort(a,0,9999);

36. for(int i=0; i<10000; ++i)

37. cout<

38. }

随机产生10000个无序数后排序、贴出程序运行完成时的屏幕截图或者输出文件的内容

归并排序：

…….太多了中间省略

快速排序：

…上次截的最后一张，这次再截张中间的

1、很顺利，这次没有遇到问题。