归并排序(Merging Sort)----(排序算法十三)

谁践踏了优雅 2022-09-17 14:25 297阅读 0赞

1.算法原理

2.代码实现

  1. #include <stdio.h>
  2. //printArray打印出数组
  3. void printArray(int a[],int size){
  4. printf("数组为:%d ",a[0]);
  5. for (int i=1;i<size;i++)
  6. {
  7. printf(" %d ",a[i]);
  8. }
  9. printf("\n");
  10. }
  11. //将有二个有序数列a[first...mid]和a[mid...last]合并。
  12. void mergearray(int a[], int first, int mid, int last, int temp[])
  13. {
  14. printArray(a,last);
  15. int i = first, j = mid + 1;
  16. int m = mid, n = last;
  17. int k = 0;
  18. while (i <= m && j <= n)
  19. {
  20. if (a[i] <= a[j])
  21. temp[k++] = a[i++];
  22. else
  23. temp[k++] = a[j++];
  24. }
  25. while (i <= m)
  26. temp[k++] = a[i++];
  27. while (j <= n)
  28. temp[k++] = a[j++];
  29. for (i = 0; i < k; i++)
  30. a[first + i] = temp[i];
  31. }
  32. //递归归并排序
  33. void mergesort(int a[], int first, int last, int temp[])
  34. {
  35. if (first < last)
  36. {
  37. int mid = (first + last) / 2;
  38. mergesort(a, first, mid, temp); //左边有序
  39. mergesort(a, mid + 1, last, temp); //右边有序
  40. mergearray(a, first, mid, last, temp); //再将二个有序数列合并
  41. }
  42. }
  43. bool MergeSort(int a[], int n)
  44. {
  45. int *p = new int[n];
  46. if (p == NULL)
  47. return false;
  48. mergesort(a, 0, n - 1, p);
  49. delete[] p;
  50. return true;
  51. }
  52. void main()
  53. {
  54. int a[10] ={9,8,7,6,5,4,3,2,1,0};
  55. MergeSort(a,10);
  56. printArray(a,10);
  57. }

3.结果

  1. 数组为:9
  2. 数组为:8 9
  3. 数组为:7 8 9 6
  4. 数组为:7 8 9 5
  5. 数组为:5 6 7 8 9 4
  6. 数组为:5 6 7 8 9 3 4
  7. 数组为:5 6 7 8 9 2 3 4 1
  8. 数组为:5 6 7 8 9 2 3 4 0
  9. 数组为:5 6 7 8 9 0 1 2 3
  10. 数组为:0 1 2 3 4 5 6 7 8 9

发表评论

表情:
评论列表 (有 0 条评论,297人围观)

还没有评论,来说两句吧...

相关阅读

    相关 归并排序merge sort

    归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。(出自[维基百科][Li