【数据结构初阶】八大排序(三)——归并排序&&计数排序

大家好���是沐曦希

往期博客：【数据结构初阶】八大排序(一)——希尔排序&&堆排序&&直接插入排序&&直接选择排序

【数据结构初阶】八大排序(二)——快速排序&&冒泡排序

文章目录

• 1.归并排序(递归)
• • 1.1 基本思想
  • 1.2 具体思路
  • 1.2 代码
  • 1.3 特性总结
  • 排序性能对比
  • 2.归并排序(非递归)
  • • 2.1 具体思路
    • 2.3 代码
    • 3.非比较排序——计数排序
    • • 3.1 基本思想
      • 代码
      • 特性总结
      • 排序性能对比
      • 4.排序算法复杂度及稳定性分析
      • 5.选择题练习
      • • 5.1 选择题一
        • 5.2 选择题二
        • 5.3 选择题三
        • 5.4 选择题四
        • 5.5 选择题五
        • 5.6 选择题六
        • 5.7 选择题七
        • 4.写在最后

          1.归并排序(递归)

          1.1 基本思想

          归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：

          1.2 具体思路

          第一步：递归分解数组。通过递归将数组a分解成n个数组，其中每个数组只有一个元素，类似与二叉树。那么此时每个数组都是有序的，那么就可以进行归并。例如:

          第二步：将上述的n个数组，进行相邻两两数组的全部元素进行比较，创建一个新的数组tmp，数组tmp大小和数组a的大小相同。取小的尾插进数组tmp,将两个数组中剩余元素尾插进入数组tmp。

          (当数组元素不为奇数)进行一次归并后，每个数组的元素为两个，那么继续相邻的两个数组进行元素比较，取小的尾插到tmp，最后将两个数组中剩余元素尾插进入数组tmp。

          (当数组元素个数为2^n)此时每个数组的元素个数为四个，继续按照上面步骤直到数组有序。

          第三步，最后将数组tmp的元素拷贝回原数组a–归并哪了部分就拷贝哪部分回原数组a。

          memcpy(a + left, tmp + left, (right - left + 1) * sizeof(int));

          归并排序的动图

          因为需要分解和比较元素大小，那么可以创建三个变量left,mid,right。将数组分解成[left,mid] [mid+1,right]继续进行递归直到每个数组元素只有一个。

          此时要解决边界的问题：即数组一的left1是left,right1是mid。

          数组二的left2是mid+1,right2是right。

          比较大小

          while (left1 if (a[left1] if (left = right)return;int mid = (right - left) / 2 + left;//[left,mid] [mid+1,right]//递归将数组分成n个数组--类似二叉树_MergeSort(a, left, mid, tmp);_MergeSort(a, mid + 1, right, tmp);//归并一趟int left1 = left, right1 = mid;int left2 = mid + 1, right2 = right;int i = left;while (left1 if (a[left1] int* tmp = (int*)malloc(n * sizeof(int));if (tmp == NULL){perror("malloc fail");return;}_MergeSort(a, 0, n - 1, tmp);}srand((unsigned int)time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);assert(a1);int* a2 = (int*)malloc(sizeof(int) * N);assert(a2);int* a3 = (int*)malloc(sizeof(int) * N);assert(a3);int* a4 = (int*)malloc(sizeof(int) * N);assert(a4);int* a5 = (int*)malloc(sizeof(int) * N);assert(a5);int* a6 = (int*)malloc(sizeof(int) * N);assert(a6);int* a7 = (int*)malloc(sizeof(int) * N);assert(a7);for (int i = 0; i