《算法设计与分析-排序》实验报告
一、实验内容：
排序问题。
二、所用算法的基本思想及复杂度分析：
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 <iostream>
2.
3. using namespace std;
4.
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<<a[i]<<" ";
59. }
2、快速排序法
1. #include <iostream>
2.
3. using namespace std;
4.
5. //调整序列，大的放右边 小的放左边
6. int adjust(int a[], int front, int rear){
7. int i=front, j=rear;
8. int x = a[front];
9. while(i<j){
10. while(a[j]>=x && i<j)
11. j--;
12. a[i] = a[j];
13. while(a[i]<=x && i<j)
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<rear){
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<<a[i]<<" ";
38. }
四、运行输出结果：
随机产生10000个无序数后排序、贴出程序运行完成时的屏幕截图或者输出文件的内容
归并排序：
…….太多了中间省略
快速排序：
…上次截的最后一张，这次再截张中间的
五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训：
1、很顺利，这次没有遇到问题。