
void _MergeSort(int* arr, int left, int right, int* tmp)
{
    if(left >= right)
    {
        return;
    }
    //分解
    int mid = (left + right) / 2;
    //左序列
    _MergeSort(arr, left, mid, tmp);
    //右序列
    _MergeSort(arr, mid + 1, right, tmp);
 
    //左序列
    int begin1 = left;
    int end1 = mid;
    //右序列
    int begin2 = mid + 1;
    int end2 = right;
 
    int index = begin1;
    //合并
    while(begin1 <= end1 && begin2 <= end2)
    {
        if(arr[begin1] < arr[begin2])
        {
            tmp[index++] = arr[begin1++];
        }
        else
        {
            tmp[index] = arr[begin2++];
        }
    }
    //begin1越界
    while(begin1 <= end1)
    {
        tmp[index++] = arr[begin1];
    }
    //或者begin2越界
    while(begin2 <= end2)
    {
        tmp[index++] = arr[begin2];
    }
    //根据tmp数组更新arr数组
    for(int i = left; i <= right; i ++)
    {
        arr[i] = tmp[i];
    }
}
 
void MergeSort(int* arr, int n)
{
    int* tmp = (int*)malloc(sizeof(int)*n);
    _MergeSort(arr, 0, n - 1, tmp);
    free(tmp);
}

(4) 代码解释

1.首先，我们来看主函数MergeSort()：创建一个与原数组等大小的数组tmp，然后进行归并排序。

2.接着，在_MergeSort中：

分解时，我们通过下标找到该序列的left和right，那么就可以找到左子序列[left , mid]和右子序列[mid + 1 , right]，然后递归左右子序列，直至left>=right，结束递归。

合并时，我们创建变量begin1、end1、begin2、end2来表示左右子序列的两端，用index来表示tmp数组的下标。在两个序列中，我们将其中的数据进行排序。当跳出循环时，说明左子序列遍历完成或者右子序列遍历完成，将剩下的序列中的数据存放入tmp序列中即可。至此我们完成了合并。

3.完成了排序，此时排列好的数据仍然存放在tmp数组中，我们根据tmp将arr数组进行更新，到此就完成了整个归并排序。

（5）复杂度

1.时间复杂度：O(N*logN)；

2.空间复杂度：O(N)。

二、非比较排序（计数排序）

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。

（1）操作步骤

1.统计出每个元素出现的次数；

2.将统计的结果保存在数组中。

（2）图示

例如：数组{6，1，2，9，4，2，4，1，1}中，1的个数为3，我们就让下标为1的位置存放3；2的个数为2，我们就让下标为2的位置存放2……

由此我们可以知道，我们申请空间的大小为数组中的最大值。

（3）思考

1.如果数组为{101，102，109，105，101，105}，难道我们要申请109个空间吗？

就上述数组来说，如果我们申请了109个空间，不存在100之前的数据，那么那些空间不就浪费了吗？

因此单单按数据开辟空间是行不通的。

2.我们知道不存在为负数的下标，那如果数组中有负数怎么进行排序呢？

通过思考可能会想到将负数取绝对值，不就变成正数了吗？可是，如果负数是-5，同时数组中存在5，将负数取绝对值后，-5和5不就分不清了吗？因此这个方法也行不通。

为了不让空间浪费，并且解决负数排序的情况，我们可以开辟空间存放最小值和最大值之间的数据，即空间的大小为max - min + 1。这样，即使最小值为负数，我们让一个数减去最小的负数，结果必然是整数！

（4）代码实现


void CountSort(int* arr, int n)
{
    //找最大值和最小值
    int min = arr[0];
    int max = arr[0];
    for(int i = 1; i < n; i++)
    {
        if(arr[i] < min)
            min = arr[i];
        if(arr[i] > max)
            max = arr[i];
    }
 
    //确定新数组的大小
    int range = max - min + 1;
    //创建新数组
    int* count = (int*)malloc(sizeof(int) * n);
    if(count == NULL)
    {
        perror("malloc fail!");
        return;
    }
 
    //统计数组中各元素的个数
    for(int i = 0; i < n; i++)
    {
        count[arr[i] - min] ++;
    }
 
    //排序、输出
    int j = 0;
    for(int i = 0; i < range; i++)
    {
        while(count[i]--)
        {
            arr[j++] = i + min;
        }
    
    }
}

(5)注意

1.统计数组中的元素时，数据arr[i]对应的新数组的下标为arr[i] - min；

2.在排序、输出时，数据arr[i]对应的新数组的数据为i + min。

（6）代码解释

首先我们找到要排序的数组的最大值和最小值，创建一个新数组保存统计的数据个数的结果，最后按照新数组的数据进行排序（更新原数组）。

（7）复杂度

1.时间复杂度：O(N + range)；

2.空间复杂度：O(range)。

三、排序性能对比


//测试排序性能对比
void TestOP()
{
    srand(time(0));
    const int N = 100000;
    int* a1 = (int*)malloc(sizeof(int) * N);
    int* a2 = (int*)malloc(sizeof(int) * N);
    int* a3 = (int*)malloc(sizeof(int) * N);
    int* a4 = (int*)malloc(sizeof(int) * N);
    int* a5 = (int*)malloc(sizeof(int) * N);
    int* a6 = (int*)malloc(sizeof(int) * N);
    int* a7 = (int*)malloc(sizeof(int) * N);
    int* a8 = (int*)malloc(sizeof(int) * N);
 
    for(int i = 0; i < N; i ++)
    {
        arr1[i] = rand();
        arr2[i] = arr1[i];
        arr3[i] = arr1[i];
        arr4[i] = arr1[i];
        arr5[i] = arr1[i];
        arr6[i] = arr1[i];
        arr7[i] = arr1[i];
        arr8[i] = arr1[i];
    }
    //直接插入排序
    int begin1 = clock();
    InsertSort(arr1,N);
    int end1 = clock();
 
    //希尔排序
    int begin2 = clock();
    ShellSort(arr1,N);
    int end2 = clock();
 
    //直接选择排序
    int begin3 = clock();
    SelectSort(arr1,N);
    int end3 = clock();
 
    //堆排序
    int begin4 = clock();
    HeapSort(arr1,N);
    int end4 = clock();
 
    //冒泡排序
    int begin5 = clock();
    BubbleSort(arr1,N);
    int end5 = clock();
 
    //快速排序
    int begin6 = clock();
    QuickSort(arr1,N);
    int end6 = clock();
 
    //归并排序
    int begin7 = clock();
    MergeSort(arr1,N);
    int end7 = clock();
 
    //计数排序
    int begin8 = clock();
    CountSort(arr1,N);
    int end8 = clock();
 
    printf("InsertSort:%d\n",end1 - begin1);
    printf("ShellSort:%d\n",end2 - begin2);
    printf("SelectSort:%d\n",end3 - begin3);
    printf("HeapSort:%d\n",end4 - begin4);
    printf("BubbleSort:%d\n",end5 - begin5);
    printf("QuickSort:%d\n",end6 - begin6);
    printf("MergeSort:%d\n",end7 - begin7);
    printf("CountSort:%d\n",end8 - begin8);
 
    free(arr1);
    free(arr2);
    free(arr3);
    free(arr4);
    free(arr5);
    free(arr6);
    free(arr7);
    free(arr8);
}

四、排序算法特性

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

稳定性验证案例

直接选择排序：58529；

希尔排序：58259；

堆排序：2222；

快速排序：53343891011。

五、写在最后

至此我们学习了顺序表、链表、栈、队列、二叉树、排序，初阶数据结构完结~撒花！

我们C++见！！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/人工智能uu/article/detail/1008588