有没有更好的排序算法

题目：

我的代码：

void sort_maoPao(int* people,int peopleSize)
{
    int i,j;
    int temp = 0;
    for(i=0;i<peopleSize-1;i++){
        for(j=1;j<peopleSize-i;j++){
            if(people[j-1]<people[j]){
                temp = people[j];
                people[j] = people[j-1];
                people[j-1] = temp;
            }
        }
    }
}

void sort_jiShu(int* const people,int peopleSize,int min,int max)
{
    int i,j;
    int* num;
    num = (int*)malloc(max*4+4);
    memset(num,0,sizeof(int)*(max+1));

    //将数组people中min~max的数字的个数分别存放在num数组的，num数组的下标对应当前存的数字
    for(i=min;i<=max;i++){
        for(j=0;j<peopleSize;j++){
            if(people[j] == i){
                num[i]++;
            }
        }
    }
    /*
    for(i=min;i<=max;i++){
        printf("num[%d]:%d\n",i,num[i]);
    }
    */
    //按照num中各个数字的个数，对people重新赋值
    int n = 0;
    for(i=max;i>=min;i--){
        for(j=0;j<num[i];j++){
            people[n] = i;
            n++;
        }
    }
}

void peopleMinAndMax(int* people,int peopleSize,int* const min,int* const max)
{
    int i;
    for(i=0;i<peopleSize;i++){
        if(*min>people[i]){
            *min = people[i];
        }
        if(*max<people[i]){
            *max = people[i];
        }
    }
}

int numRescueBoats(int* people, int peopleSize, int limit){
    int left = 0;
    int ret = peopleSize-1;
    int num = 0;
    int min = people[0];
    int max = people[0];

    peopleMinAndMax(people,peopleSize,&min,&max);
    //printf("min:%d\nmax:%d\n",min,max);
    //sort_maoPao(people,peopleSize);
    sort_jiShu(people,peopleSize,min,max);
/*
    for(int i=0;i<peopleSize;i++){
        printf("%d ",people[i]);
    }
*/
    for(left=0;left<=ret;left++){
        if(people[left] == limit){
            num++;
            continue;
        }
        if( (people[left]+people[ret]) <= limit){
            num++;
            ret--;
            continue;
        }else{
            num++;
            continue;
        }
        if(left == ret){
            num++;
        }
    }
    return num;
}

问题：
一开始我用的冒泡排序，但是有一组测试案例给的数据量特别大，5000多个，用冒泡排序会超时；
后来我发现这组数据最小值到最大值跨度不是很大，我就用了计数排序；
结果在这个案例后面还有一个案例：数据量大，最小值到最大值跨度也大0.0；
然后冒泡和计数排序都会超时；
请问有没有更好的排序算法，或者解决方法

可以用快速排序或者归并排序，或者希尔排序都是比冒泡快的。
❤️五万字《十大排序算法》动图讲解❤️(建议收藏)_英雄哪里出来-CSDN博客打开算法大门，从排序开始 https://blog.csdn.net/WhereIsHeroFrom/article/details/119976287

本文已收录于专栏🌳《画解数据结构》🌳 ❤️《画解数据结构》目录❤️（进度更新 16/31）,《画解数据结构》「基数排序」算法教程,《画解数据结构》算法时间复杂度,算法,数据结构,C/C++

https://blog.csdn.net/whereisherofrom/category_11227297.html

@[toc]

零、📃前言

「归并排序」 是利用了 「分而治之」 的思想，进行递归计算的排序算法，效率在众多排序算法中的佼佼者，一般也会出现在各种 「数据结构」 的教科书上。于是，我也来简单讲一讲。我会尽量做到「深入浅出」，让 90% 的 「零基础小白」 也都能理解，真正做到 「让天下没有难学的算法」 。我知道这很难，但是我愿意尝试！我会尽量把文章写得有趣。

🔥让天下没有难学的算法🔥
C语言免费动漫教程，和我一起打卡！🌞《光天化日学C语言》🌞 ☀️光天化日学C语言☀️（33）- 函数入门 | 开启下一个篇章！,☀️光天化日学C语言☀️（32）- continue 关键字 | 下一个！,☀️光天化日学C语言☀️（31）- break 关键字 | 当断则断！,C,C++,Hello World https://blog.csdn.net/whereisherofrom/category_11131373.html
入门级C语言真题汇总🧡《C语言入门100例》🧡 【第65题】栈的嵌套应用 (待更新),【第64题】给定字符串 s，求 s 中第一个不重复的字符 | 字符哈希的应用,【第63题】求 n 个数中没有出现的最小的正整数 | 整数哈希的应用,ACM,数据结构,Dancing Links X https://blog.csdn.net/whereisherofrom/category_11158834.html
几张动图学会一种数据结构🌳《画解数据结构》🌳 ❤️《画解数据结构》目录❤️（进度更新 16/31）,《画解数据结构》「基数排序」算法教程,《画解数据结构》算法时间复杂度,算法,数据结构,C/C++ https://blog.csdn.net/whereisherofrom/category_11227297.html
组团学习，抱团生长🌌《算法入门指引》🌌 腾讯文档 https://docs.qq.com/mind/DU01SVGpab2tWdlNj
竞赛选手金典图文教程💜《夜深人静写算法》💜 夜深人静写算法（三十九）- 卢卡斯定理,夜深人静写算法（三十八）- 整数分块,夜深人静写算法（三十七）- 威尔逊定理,ACM,算法,并查集 https://blog.csdn.net/whereisherofrom/category_9273531.html

那么，我的教程和别人的教程有什么不同的地方呢？
「第一步」简单释义：我会简单解释一下这个算法的目的、思想、以及为什么叫这个名字以帮助记忆。
「第二步」核心思想：我会大致介绍一下这个算法的核心思想。
「第三步」动图演示：我会引入一个动图，并且用一个切实的例子展示一下算法执行的全过程。
「第四步」算法前置：在学习这个算法之前，我们需要学习的前置内容有哪些？这些内容是需要事先去攻克的。
「第五步」算法描述：细致的讲解整个算法的执行流程。
「第六步」算法分析：对算法的时间复杂度和空间复杂度进行一个详细的分析。
「第七步」优化方案：介绍一些可以优化的点。
「第八步」代码实践：用 C/C++ 来实现上述算法。
「第九步」代码验证：最后，我会推荐一些比较好用的在线评测系统来验证我们实现的算法的正确性。

一、🎯简单释义

1、算法目的

将原本乱序的数组变成有序，可以是 「升序」 或者 「降序」 （为了描述统一，本文一律只讨论 「升序」 的情况）。

2、算法思想

通过将当前乱序数组分成长度近似的两份，分别进行「递归」 调用，然后再对这两个排好序的数组，利用两个指针，将数据元素依次比较，选择相对较小的元素存到一个「辅助数组」中，再将「辅助数组」中的数据存回「原数组」。

3、命名由来

每次都是将数列分成两份，分别排序后再进行 「归并」，故此命名 「归并排序」 。

二、🧡核心思想

「递归」：函数通过改变参数，自己调用自己。
「比较」：关系运算符小于($\lt$) 的运用。
「归并」：两个数组合并成一个数组的过程。

三、🔆动图演示

1、样例
|||||||||
-|-|-|-|-|-|-|-
8|5|6|4|3|7|10|2

初始情况下的数据如 图二-1-1 所示，基本属于乱序，纯随机出来的数据。

在这里插入图片描述

图二-1-1

2、算法演示

接下来，我们来看下排序过程的动画演示。如 图二-2-1 所示：

图二-2-1

我们发现，首先将 「 8个元素」 分成 「 4个元素」，再将 「 4个元素」 分成 「 2个元素」，然后 「比较」这「 2个元素」的值，使其在自己的原地数组内有序，然后两个 「 2个元素」 的数组归并变成 「 4个元素」 的 「升序」数组，再将两个「 4个元素」 的数组归并变成 「 8个元素」 的 「升序」数组。

四、🌳算法前置

1、递归的实现

这个算法本身需要做一些「递归」计算，所以你至少需要知道「递归」 的含义，这里以 「 C语言」 为例，来看下一个简单的「递归」是怎么写的。代码如下：
```
int sum(int n) {
  if(n <= 0) {
      return 0;
  } 
  return sum(n - 1) + n;
}
```
这就是一个经典的递归函数，求的是从 $1$ 到 $n$ 的和，那么我们把它想象成 $1$ 到 $n-1$ 的和再加 $n$，而 $1$ 到 $n-1$ 的和为sum(n-1)，所以整个函数体就是两者之和，这里sum(n)调用sum(n-1)的过程就被称为「递归」。

2、比较的实现

「比较」两个元素的大小，可以采用关系运算符，本文我们需要排序的数组是按照 「升序」 排列的，所以用到的关系运算符是 「小于运算符（即 <）」 。
我们可以将两个数的「比较」写成一个函数smallerThan，以 「 C语言」 为例，实现如下：
```
#define Type int
bool smallerThan(Type a, Type b) {
  return a < b;
}
```
其中Type代表数组元素的类型，可以是整数，也可以是浮点数，也可以是一个类的实例，这里我们统一用int来讲解，即 32位有符号整型。

3、归并的实现

所谓「归并」，就是将两个有序数组合成一个有序数组的过程。
如下图所示：「红色数组」 和 「黄色数组」 各自有序，然后通过一个额外的数组，「归并」 计算后得到一个有序的数组。

在这里插入图片描述

五、🥦算法描述

1、问题描述

给定一个 $n$ 个元素的数组，数组下标从 $0$ 开始，采用「归并排序」将数组按照 「升序」排列。

2、算法过程

整个算法的执行过程用 mergeSort(a[], l, r)描述，代表当前待排序数组 $a$，左区间下标 $l$，右区间下标 $r$，分以下几步：
1）计算中点 $mid = \frac {l + r}{2}$；
2）递归调用mergeSort(a[], l, mid)和mergeSort(a[], mid+1, r)；
3）将 2）中两个有序数组进行有序合并，再存储到a[l:r]；
4）调用时，调用 mergeSort(a[], 0, n-1)就能得到整个数组的排序结果。

「递归」是自顶向下的，实际上程序真正运行过程是自底向上「回溯」的过程：给定一个 $n$ 个元素的数组，「归并排序」 将执行如下几步：
1）将每对单个元素归并为 2个元素的有序数组；
2）将 2个元素的每对有序数组归并成 4个元素的有序数组，重复这个过程…；
3）最后一步：归并 2 个 $n / 2$ 个元素的排序数组（为了简化讨论，假设 $n$ 是偶数）以获得完全排序的 $n$ 个元素数组。

六、🧶算法分析

1、时间复杂度

我们假设 「比较」 和 「赋值」 的时间复杂度为 $O(1)$。
我们首先讨论「归并排序」算法的最重要的子程序：$O(n)$ 归并，然后解析这个归并排序算法。
给定两个大小为 $n_1$ 和 $n_2$ 的排序数组 $A$ 和 $B$，我们可以在 $O(n)$ 时间内将它们有效地归并成一个大小为 $n = n_1 + n_2$ 的组合排序数组。可以通过简单地比较两个数组的前面并始终取两个中较小的一个来实现的。
问题是这个归并过程被调用了多少次？
由于每次都是对半切，所以整个归并过程类似于一颗二叉树的构建过程，次数就是二叉树的高度，即 $log_2n$，所以归并排序的时间复杂度为 $O(nlog_2n)$。

2、空间复杂度

由于归并排序在归并过程中需要额外的一个「辅助数组」，并且最大长度为原数组长度，所以「归并排序」的空间复杂度为 $O(n)$。
七、🧢优化方案
「归并排序」在众多排序算法中效率较高，时间复杂度为 $O(nlog_2n)$ 。
但是，由于归并排序在归并过程中需要额外的一个「辅助数组」，所以申请「辅助数组」内存空间带来的时间消耗会比较大，比较好的做法是，实现用一个和给定元素个数一样大的数组，作为函数传参传进去，所有的 「辅助数组」 干的事情，都可以在这个传参进去的数组上进行操作，这样就免去了内存的频繁申请和释放。

八、💙源码详解

#include <stdio.h>
#include <malloc.h>
 
#define maxn 1000001

int a[maxn];

void Input(int n, int *a) {
    for(int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
}

void Output(int n, int *a) {
    for(int i = 0; i < n; ++i) {
        if(i)
            printf(" ");
        printf("%d", a[i]);
    }
    puts("");
}

void MergeSort(int *nums, int l, int r) {
    int i, mid, p, lp, rp;
    int *tmp = (int *)malloc( (r-l+1) * sizeof(int) );    // (1)  
    if(l >= r) {
        return ;                                          // (2) 
    }
    mid = (l + r) >> 1;                                   // (3) 
    MergeSort(nums, l, mid);                              // (4) 
    MergeSort(nums, mid+1, r);                            // (5) 
    p = 0;                                                // (6) 
    lp = l, rp = mid+1;                                   // (7) 
    while(lp <= mid || rp <= r) {                         // (8) 
        if(lp > mid) {
            tmp[p++] = nums[rp++];                        // (9) 
        }else if(rp > r) {
            tmp[p++] = nums[lp++];                        // (10) 
        }else {
            if(nums[lp] <= nums[rp]) {                    // (11) 
                tmp[p++] = nums[lp++];
            }else {
                tmp[p++] = nums[rp++];
            }
        }
    }
    for(i = 0; i < r-l+1; ++i) {
        nums[l+i] = tmp[i];                               // (12) 
    } 
    free(tmp);                                            // (13) 
}

int main() {
    int n;
    while(scanf("%d", &n) != EOF) {
        Input(n, a);
        MergeSort(a, 0, n-1);
        Output(n, a);
    }
    return 0;
}

$(1)$ 申请一个辅助数组，用于对原数组进行归并计算；
$(2)$ 只有一个元素，或者没有元素的情况，则不需要排序；
$(3)$ 将数组分为 $[l, mid]$ 和 $[mid+1, r]$ 两部分；
$(4)$ 递归排序 $[l, mid]$ 部分；
$(5)$ 递归排序 $[mid+1, r]$ 部分；
$(6)$ 将需要排序的数组缓存到tmp中，用p作为游标；
$(7)$ 初始化两个数组的指针；
$(8)$ 当两个指针都没有到结尾，则继续迭代；
$(9)$ 只剩下右边的数组，直接排；
$(10)$ 只剩下走右边的数组，直接排；
$(11)$ 取小的那个先进tmp数组；
$(12)$ 别忘了将排序好的数据拷贝回原数组；
$(13)$ 别忘了释放临时数据，否则就内存泄漏了！！！

九、💗代码验证

比如，你可以在百度上搜索 代码在线提交、OnlineJudge、LeetCode、洛谷、HDOJ、POJ 等等的关键词，然后去找对应的题目提交验证你的代码的正确性。

关于 「归并排序」 的内容到这里就结束了。
如果还有不懂的问题，可以通过 「作者主页」找到作者的「联系方式」 进行在线咨询。

有关 🌳《画解数据结构》🌳 ❤️《画解数据结构》目录❤️（进度更新 16/31）,《画解数据结构》「基数排序」算法教程,《画解数据结构》算法时间复杂度,算法,数据结构,C/C++ https://blog.csdn.net/whereisherofrom/category_11227297.html 的源码均开源，链接如下：《画解数据结构》 Contribute to WhereIsHeroFrom/Code_Templates development by creating an account on GitHub. https://github.com/WhereIsHeroFrom/Code_Templates/tree/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/%E7%94%BB%E8%A7%A3%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84

🔥让天下没有难学的算法🔥
C语言免费动漫教程，和我一起打卡！🌞《光天化日学C语言》🌞 ☀️光天化日学C语言☀️（33）- 函数入门 | 开启下一个篇章！,☀️光天化日学C语言☀️（32）- continue 关键字 | 下一个！,☀️光天化日学C语言☀️（31）- break 关键字 | 当断则断！,C,C++,Hello World https://blog.csdn.net/whereisherofrom/category_11131373.html
LeetCode 太难？先看简单题！🧡《C语言入门100例》🧡 【第65题】栈的嵌套应用 (待更新),【第64题】给定字符串 s，求 s 中第一个不重复的字符 | 字符哈希的应用,【第63题】求 n 个数中没有出现的最小的正整数 | 整数哈希的应用,ACM,数据结构,Dancing Links X https://blog.csdn.net/whereisherofrom/category_11158834.html
数据结构难？不存在的！🌳《画解数据结构》🌳 ❤️《画解数据结构》目录❤️（进度更新 16/31）,《画解数据结构》「基数排序」算法教程,《画解数据结构》算法时间复杂度,算法,数据结构,C/C++ https://blog.csdn.net/whereisherofrom/category_11227297.html
闭关刷 LeetCode，剑指大厂Offer！🌌《算法入门指引》🌌 腾讯文档 https://docs.qq.com/mind/DU01SVGpab2tWdlNj
LeetCode 太简单？算法学起来！💜《夜深人静写算法》💜 夜深人静写算法（三十九）- 卢卡斯定理,夜深人静写算法（三十八）- 整数分块,夜深人静写算法（三十七）- 威尔逊定理,ACM,算法,并查集 https://blog.csdn.net/whereisherofrom/category_9273531.html