排序算法，最全的10大排序算法详解（Sort Algorithm）

Love The Way You Lie 2022-09-05 01:42 181阅读 0赞

### 文章目录 ###

*  排序算法，最全的10大排序算法详解（Sort Algorithm）
 *  排序算法分类
 *  排序算法稳定性
 *  时间复杂度（time complexity）
 *   *  1\#时间复杂度的意义
     *  2\#基本操作执行次数
     *  如何推导出时间复杂度呢？有如下几个原则：
     *  3\#让我们回头看看刚才的四个场景。
 *  对数（log、logarithm）
 *   *  对数数轴与天文数字
 *  1\# 基数排序（radix sort）
 *  2\# 冒泡排序（Bubble Sort）
 *  3\# 希尔排序（shellSort）
 *  4\# 快速排序（quickSort）
 *  5\# 堆排序（heapSort）
 *  6\# 归并排序（mergeSort）
 *  7\# 插入排序（Insertion Sort）
 *  8\# 选择排序（Selection sort）
 *  9\# 计数排序（CountingSort）
 *  10\# 桶排序（bucketSort）
 *  PS\#桶排序&计数排序&基数排序
 *  参考资料
 *  参考书目
 *  参考程序
 *  参考习题

# 排序算法，最全的10大排序算法详解（Sort Algorithm） #

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析。

也就说，把一串数通过一通操作变成有序的一串数，这个操作就要用到排序算法。

下面是十大经典排序算法。

(1)冒泡排序；

(2)选择排序；

(3)插入排序；；

(4)希尔排序；

(5)归并排序；；

(6)快速排序；

(7)基数排序；

(8)堆排序；

(9)计数排序；

(10)桶排序。

我将会采用自己的方法和别人的各种讲法汇总起来讲解

# 排序算法分类 #

十种常见排序算法可以分为两大类：

*  **比较类排序**：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
 *  **非比较类排序**：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等

# 排序算法稳定性 #

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。  
不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面

需要注意的是，排序算法是否为稳定的是由具体算法决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。

![img][]

![img][img 1]

# 时间复杂度（time complexity） #

在[计算机科学][Link 1]中，[算法][Link 2]的**时间复杂度**（Time complexity）是一个[函数][Link 3]，它定性描述该算法的运行时间。这是一个代表算法输入值的[字符串][Link 4]的长度的函数。时间复杂度常用[大O符号][O]表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是[渐近][Link 5]的，亦即考察输入值大小趋近无穷时的情况。例如，如果一个算法对于任何大小为 *n* （必须比 *n0* 大）的输入，它至多需要 5*n*3 + 3*n* 的时间运行完毕，那么它的渐近时间复杂度是 O(*n*3)。

为了计算时间复杂度，我们通常会估计算法的操作单元数量，每个单元运行的时间都是相同的。因此，总运行时间和算法的操作单元数量最多相差一个常量系数。

相同大小的不同输入值仍可能造成算法的运行时间不同，因此我们通常使用算法的[最坏情况复杂度][Link 6]，记为 ***T\*(\*n\*)** ，定义为任何大小的输入 n 所需的最大运行时间。另一种较少使用的方法是[平均情况复杂度][Link 7]，通常有特别指定才会使用。时间复杂度可以用函数 T(n) 的自然特性加以分类，举例来说，有着 T(n) = O(n) 的算法被称作“线性时间算法”；而 T(n) = O(M\*n*) 和 *M\*\*n*= O(*T*(*n*)) ，其中 *M* ≥ *n* > 1 的算法被称作“指数时间算法”。

## 1\#时间复杂度的意义 ##

究竟什么是时间复杂度呢？让我们来想象一个场景：某一天，小灰和大黄同时加入了一个公司…

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

一天过后，小灰和大黄各自交付了代码，两端代码实现的功能都差不多。大黄的代码运行一次要花100毫秒，内存占用5MB。小灰的代码运行一次要花100秒，内存占用500MB。于是…

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 2]

由此可见，衡量代码的好坏，包括两个非常重要的指标：

1.运行时间；

2.占用空间。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 3]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 4]

## 2\#基本操作执行次数 ##

关于代码的基本操作执行次数，我们用四个生活中的场景，来做一下比喻：

\*\*场景1：\*\*给小灰一条长10寸的面包，小灰每3天吃掉1寸，那么吃掉整个面包需要几天？

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 5]

答案自然是 3 X 10 = 30天。

如果面包的长度是 N 寸呢？

此时吃掉整个面包，需要 3 X n = 3n 天。

如果用一个函数来表达这个相对时间，可以记作 T（n） = 3n。

\*\*场景2：\*\*给小灰一条长16寸的面包，小灰每5天吃掉面包剩余长度的一半，第一次吃掉8寸，第二次吃掉4寸，第三次吃掉2寸…那么小灰把面包吃得只剩下1寸，需要多少天呢？

这个问题翻译一下，就是数字16不断地除以2，除几次以后的结果等于1？这里要涉及到数学当中的对数，以2位底，16的对数，可以简写为log16。

因此，把面包吃得只剩下1寸，需要 5 X log16 = 5 X 4 = 20 天。

如果面包的长度是 N 寸呢？

需要 5 X logn = 5logn天，记作 T（n） = 5logn。

--------------------

\*\*场景3：\*\*给小灰一条长10寸的面包和一个鸡腿，小灰每2天吃掉一个鸡腿。那么小灰吃掉整个鸡腿需要多少天呢？

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 6]

答案自然是2天。因为只说是吃掉鸡腿，和10寸的面包没有关系 。

如果面包的长度是 N 寸呢？

无论面包有多长，吃掉鸡腿的时间仍然是2天，记作 T（n） = 2。

\*\*场景4：\*\*给小灰一条长10寸的面包，小灰吃掉第一个一寸需要1天时间，吃掉第二个一寸需要2天时间，吃掉第三个一寸需要3天时间…每多吃一寸，所花的时间也多一天。那么小灰吃掉整个面包需要多少天呢？

答案是从1累加到10的总和，也就是55天。

如果面包的长度是 N 寸呢？

此时吃掉整个面包，需要 1+2+3+…+ n-1 + n = (1+n)\*n/2 = 0.5n^2 + 0.5n。

记作 T（n） = 0.5n^2 + 0.5n。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 7]

上面所讲的是吃东西所花费的相对时间，这一思想同样适用于对程序基本操作执行次数的统计。刚才的四个场景，分别对应了程序中最常见的四种执行方式：

## 如何推导出时间复杂度呢？有如下几个原则： ##

1.  如果运行时间是常数量级，用常数1表示；
2.  只保留时间函数中的最高阶项；
3.  如果最高阶项存在，则省去最高阶项前面的系数。

## 3\#让我们回头看看刚才的四个场景。 ##

**场景1：**

T（n） = 3n

最高阶项为3n，省去系数3，转化的时间复杂度为：

T（n） = O（n）

![640?wx\_fmt=png][640_wx_fmt_png]

**场景2：**

T（n） = 5logn

最高阶项为5logn，省去系数5，转化的时间复杂度为：

T（n） = O（logn）

![640?wx\_fmt=png][640_wx_fmt_png 1]

**场景3：**

T（n） = 2

只有常数量级，转化的时间复杂度为：

T（n） = O（1）

![640?wx\_fmt=png][640_wx_fmt_png 2]

**场景4：**

T（n） = 0.5n^2 + 0.5n

最高阶项为0.5n^2，省去系数0.5，转化的时间复杂度为：

T（n） = O（n^2）

![640?wx\_fmt=png][640_wx_fmt_png 3]

这四种时间复杂度究竟谁用时更长，谁节省时间呢？稍微思考一下就可以得出结论：

O（1）< O（logn）< O（n）< O（n^2）

在编程的世界中有着各种各样的算法，除了上述的四个场景，还有许多不同形式的时间复杂度，比如：

O（nlogn）, O（n^3）, O（m\*n），O（2^n），O（n！）

遨游在代码的海洋里，我们会陆续遇到上述时间复杂度的算法。

![640?wx\_fmt=png][640_wx_fmt_png 4]

# 对数（log、logarithm） #

在数学中，对数是对求幂的逆运算，正如除法是乘法的倒数，反之亦然。 这意味着一个数字的对数是必须产生另一个固定数字（基数）的指数。 在简单的情况下，乘数中的对数计数因子。更一般来说，乘幂允许将任何正实数提高到任何实际功率，总是产生正的结果，因此可以对于b不等于1的任何两个正实数b和x计算对数。

如果a的x次方等于N（a>0，且a≠1），那么数x叫做以a为底N的对数（logarithm），记作x=log\_a N。其中，a叫做对数的[底数][Link 8]，N叫做[真数][Link 9]。

**例**：23是8，指数为3，底数为2，结果是8。那么以2为底8的对数就是求指数3。

## 对数数轴与天文数字 ##

**对数数轴**

我们要是想把为 \[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IExzVVJ3-1629094072579)(https://www.zhihu.com/equation?tex=%5Ctimes+2)\] 坐标系继续画下去是困难的，因为指数增长太快了（指数级增长）：

![img][img 2]

尽量缩小才画到对数为5的地方，我相信你已经快看不清了，如果画到对数为100的地方，地球都摆不下这个长度。

我们可以保持对数值等距离摆放，这就是对数坐标系：

![img][img 3]

是不是可以摆下更多的对数了？

**天文数字**

对数是将数轴进行强力的缩放，再大的数字都经不起对数缩放，如果我选用10为底的话，一亿这么大的数字，在对数数轴上也不过是8。这对于天文学里的天文数字简直是强有力的武器。

要是不进行缩放的话，地球和太阳是不可能同框的：

> ![img][img 4]

# 1\# 基数排序（radix sort） #

时间复杂度：O (nlog®m)

首先，基数排序的名字和计数排序很像，而且原理都是基于桶的原理，但是略有不同，不要记混了。

通俗解释：输入的n个数，对于这n个数，对照每一位比较，每一位的数字只能是0~9，所以最多有10个桶，最后排序到最后一个位，逐个排列。（好吧，总觉得解释的听不懂）

科学解释（但我一开始看不懂）：基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

看不懂文字，就看图！

[https://visualgo.net/zh/sorting][https_visualgo.net_zh_sorting]，这里是排序算法集合，很多排序算法的演示都有。visualgo主站还有其他数据结构的演示，比如链表。

![在这里插入图片描述][f5af707e866748acbddc91373bf5bf6a.gif_pic_center]

行了，上代码

Java

public class RadixSort implements IArraySort { 
    
        @Override
        public int[] sort(int[] sourceArray) throws Exception { 
            // 对 arr 进行拷贝，不改变参数内容
            int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
    
            int maxDigit = getMaxDigit(arr);
            return radixSort(arr, maxDigit);
        }
    
        /** * 获取最高位数 */
        private int getMaxDigit(int[] arr) { 
            int maxValue = getMaxValue(arr);
            return getNumLenght(maxValue);
        }
    
        private int getMaxValue(int[] arr) { 
            int maxValue = arr[0];
            for (int value : arr) { 
                if (maxValue < value) { 
                    maxValue = value;
                }
            }
            return maxValue;
        }
    
        protected int getNumLenght(long num) { 
            if (num == 0) { 
                return 1;
            }
            int lenght = 0;
            for (long temp = num; temp != 0; temp /= 10) { 
                lenght++;
            }
            return lenght;
        }
    
        private int[] radixSort(int[] arr, int maxDigit) { 
            int mod = 10;
            int dev = 1;
    
            for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) { 
                // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
                int[][] counter = new int[mod * 2][0];
    
                for (int j = 0; j < arr.length; j++) { 
                    int bucket = ((arr[j] % mod) / dev) + mod;
                    counter[bucket] = arrayAppend(counter[bucket], arr[j]);
                }
    
                int pos = 0;
                for (int[] bucket : counter) { 
                    for (int value : bucket) { 
                        arr[pos++] = value;
                    }
                }
            }
    
            return arr;
        }
    
        /** * 自动扩容，并保存数据 * * @param arr * @param value */
        private int[] arrayAppend(int[] arr, int value) { 
            arr = Arrays.copyOf(arr, arr.length + 1);
            arr[arr.length - 1] = value;
            return arr;
        }
    }

C++

int maxbit(int data[], int n) //辅助函数，求数据的最大位数
    { 
        int maxData = data[0];              ///< 最大数
        /// 先求出最大数，再求其位数，这样有原先依次每个数判断其位数，稍微优化点。
        for (int i = 1; i < n; ++i)
        { 
            if (maxData < data[i])
                maxData = data[i];
        }
        int d = 1;
        int p = 10;
        while (maxData >= p)
        { 
            //p *= 10; // Maybe overflow
            maxData /= 10;
            ++d;
        }
        return d;
    /* int d = 1; //保存最大的位数 int p = 10; for(int i = 0; i < n; ++i) { while(data[i] >= p) { p *= 10; ++d; } } return d;*/
    }
    void radixsort(int data[], int n) //基数排序
    { 
        int d = maxbit(data, n);
        int *tmp = new int[n];
        int *count = new int[10]; //计数器
        int i, j, k;
        int radix = 1;
        for(i = 1; i <= d; i++) //进行d次排序
        { 
            for(j = 0; j < 10; j++)
                count[j] = 0; //每次分配前清空计数器
            for(j = 0; j < n; j++)
            { 
                k = (data[j] / radix) % 10; //统计每个桶中的记录数
                count[k]++;
            }
            for(j = 1; j < 10; j++)
                count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
            for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
            { 
                k = (data[j] / radix) % 10;
                tmp[count[k] - 1] = data[j];
                count[k]--;
            }
            for(j = 0; j < n; j++) //将临时数组的内容复制到data中
                data[j] = tmp[j];
            radix = radix * 10;
        }
        delete []tmp;
        delete []count;
    }

# 2\# 冒泡排序（Bubble Sort） #

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

作为最简单的排序算法之一，冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来

算法描述：  
1.比较相邻两个数据如果。第一个比第二个大，就交换两个数  
2对每一个相邻的数做同样1的工作，这样从开始一队到结尾一队在最后的数就是最大的数  
3.针对所有元素上面的操作，除了最后一个  
4.重复1~3步骤，知道顺序完成。

1.  原理：比较两个相邻的元素，将值大的元素交换到右边
2.  思路：依次比较相邻的两个数，将比较小的数放在前面，比较大的数放在后面。

(1)第一次比较：首先比较第一和第二个数，将小数放在前面，将大数放在后面。

(2)比较第2和第3个数，将小数 放在前面，大数放在后面。

…

(3)如此继续，知道比较到最后的两个数，将小数放在前面，大数放在后面，重复步骤，直至全部排序完成

(4)在上面一趟比较完成后，最后一个数一定是数组中最大的一个数，所以在比较第二趟的时候，最后一个数是不参加比较的。

(5)在第二趟比较完成后，倒数第二个数也一定是数组中倒数第二大数，所以在第三趟的比较中，最后两个数是不参与比较的。

(6)依次类推，每一趟比较次数减少依次

![img][img 5]

C语言：

#include <stdio.h>
    void bubble_sort(int arr[], int len) { 
            int i, j, temp;
            for (i = 0; i < len - 1; i++)
                    for (j = 0; j < len - 1 - i; j++)
                            if (arr[j] > arr[j + 1]) { 
                                    temp = arr[j];
                                    arr[j] = arr[j + 1];
                                    arr[j + 1] = temp;
                            }
    }
    int main() { 
            int arr[] = {  22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
            int len = (int) sizeof(arr) / sizeof(*arr);
            bubble_sort(arr, len);
            int i;
            for (i = 0; i < len; i++)
                    printf("%d ", arr[i]);
            return 0;
    }

C++中可以把交换部分变成swap函数，`swap(arr[i], arr[j]);`

我们只需要记住

for (int i=0;i<n-1;i++)
    	for (int j=n-1;j>i;j--)
    		if (a[j]>a[j-1]) swap(a[j],a[j-1]);

稍微加入改进

for (int i = 0 ;i<n;i++) { 
        bool flag = 1 ;
        for (int j = n-1;j>i;j--){ 
            if (a[j]>a[j-1]) { 
                swap(a[j],a[j-1]) ;
                flag =0 ;
            }
        }
        if (flag) break; // 中途结束算法
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70]

#include <bits/stdc++.h>
    using namespace std;
    int a[10000001] ;
    int main(){ 
    	int n , sum = 0 ;
    	cin>>n ;
    	for (int i = 1;i<= n;i++) 
    		cin>> a[i] ;
    	for (int i = 1 ;i<n;i++)
    		for (int j =1;j<=n-i;j++)
    			if (a[j] > a[j+1]) sum ++ ;
    	cout<< sum <<endl;
    	return 0 ;
    }

# 3\# 希尔排序（shellSort） #

看懂了插入排序再来，对不起编排顺序有误。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 2]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 3]

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入[排序算法][Link 10]的一种更[高效][Link 11]的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的[关键词][Link 12]越来越多，当增量减至 1 时，整个文件恰被分成一组，[算法][Link 13]便终止。

**基本思想**

先取一个小于n的整数d1作为第一个[增量][Link 14]，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行[直接插入排序][Link 15]；然后，取第二个增量d2 =1( d t    d t − 1 \{d\_t\}\\ \\ \{d\_\{t-1\}\} dt  dt−1 …

**该方法实质上是一种分组插入方法**

比较相隔较远距离（称为[增量][Link 14]）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的[排序算法][Link 16]中实现了这一思想。算法先将要排序的一组数按某个[增量][Link 14]d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当[增量][Link 14]减到1时，整个要排序的数被分成一组，排序完成。

一般的初次取序列的一半为[增量][Link 14]，以后每次减半，直到增量为1。

**给定实例的shell排序的排序过程**

假设待排序文件有10个记录，其关键字分别是：

49，38，65，97，76，13，27，49，55，04。

[增量][Link 14]序列的取值依次为：

5，2，1

[![希尔排序][45094c75d8417b7d87db86803ff89610.png]][45094c75d8417b7d87db86803ff89610.png 1]

![img][img 6]

#include <stdio.h>
    int shsort(int s[], int n)    /* 自定义函数 shsort()*/
    { 
        int i,j,d;
        d=n/2;    /*确定固定增虽值*/
        while(d>=1)
        { 
            for(i=d+1;i<=n;i++)    /*数组下标从d+1开始进行直接插入排序*/
            { 
                s[0]=s[i];    /*设置监视哨*/
                j=i-d;    /*确定要进行比较的元素的最右边位置*/
                while((j>0)&&(s[0]<s[j]))
                { 
                    s[j+d]=s[j];    /*数据右移*/
                    j=j-d;    /*向左移d个位置V*/
                }
                s[j + d]=s[0];    /*在确定的位罝插入s[i]*/
            }
            d = d/2;    /*增里变为原来的一半*/
        }
    return 0;
    }
    
    int main()
    { 
        int a[11],i;    /*定义数组及变量为基本整型*/
        printf("请输入 10 个数据：\n");
        for(i=1;i<=10;i++)
        scanf("%d",&a[i]);    /*从键盘中输入10个数据*/
        shsort(a, 10);    /* 调用 shsort()函数*/
        printf("排序后的顺序是：\n");
        for(i=1;i<=10;i++)
        printf("%5d",a[i]);    /*输出排序后的数组*/
        printf("\n");
        return 0;
    }

请输入 10 个数据：

69 56 12 136 3 55 46 99 88 25
    排序后的顺序是：
      3  12  25  46  55  56  69  88  99 136

# 4\# 快速排序（quickSort） #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 8]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 9]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 10]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 11]

当然，我们可以使用algorithm库自带的sort函数，这是c++给你提供的最方便最快捷的排序函数，可以排序数组和动态数组。例如

bool cmp(int a, int b) // 数组类型适当更改
    { 
        return a > b; // 重载从大到小
    }
    
    vector<int>a;
    int t;
    while (cin >> t)
        a.push_back(t);
    sort(a.begin(), a.end()); // 默认从小到大排序
    sort(a.begin(), a.end(), cmp); // 改为从大到小
    int array[5] = { 6, 7, 2, 3, 5};
    sort(array, array + 5); // 从小到大
    sort(array, array + 5, cmp); // 同理，改为从大到小

我这个伪代码写得很匆忙，不理解可以百度一下，看看别人的详细代码。

sort函数大概就是这个意思，但是真正快速排序的原理是什么呢？我们要自己写出代码才能明白。，

**基本思想：**  
通过一趟排序将要排序的数据分割成独立的两部分：分割点左边都是比它小的数，右边都是比它大的数。

然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

详细的图解往往比大堆的文字更有说明力，所以直接上图：

![img][img 7]

上图中，演示了快速排序的处理过程：

初始状态为一组无序的数组：2、4、5、1、3。

经过以上操作步骤后，完成了第一次的排序，得到新的数组：1、2、5、4、3。

新的数组中，以2为分割点，左边都是比2小的数，右边都是比2大的数。

因为2已经在数组中找到了合适的位置，所以不用再动。

2左边的数组只有一个元素1，所以显然不用再排序，位置也被确定。（注：这种情况时，left指针和right指针显然是重合的。因此在代码中，我们可以通过设置判定条件left必须小于right，如果不满足，则不用排序了）。

而对于2右边的数组5、4、3，设置left指向5，right指向3，开始继续重复图中的一、二、三、四步骤，对新的数组进行排序。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]

核心代码:

public int division(int[] list, int left, int right) { 
        // 以最左边的数(left)为基准
        int base = list[left];
        while (left < right) { 
            // 从序列右端开始，向左遍历，直到找到小于base的数
            while (left < right && list[right] >= base)
                right--;
            // 找到了比base小的元素，将这个元素放到最左边的位置
            list[left] = list[right];
    
            // 从序列左端开始，向右遍历，直到找到大于base的数
            while (left < right && list[left] <= base)
                left++;
            // 找到了比base大的元素，将这个元素放到最右边的位置
            list[right] = list[left];
        }
    
        // 最后将base放到left位置。此时，left位置的左侧数值应该都比left小；
        // 而left位置的右侧数值应该都比left大。
        list[left] = base;
        return left;
    }
    
    private void quickSort(int[] list, int left, int right){ 
    
        // 左下标一定小于右下标，否则就越界了
        if (left < right) { 
            // 对数组进行分割，取出下次分割的基准标号
            int base = division(list, left, right);
    
            System.out.format("base = %d:\t", list[base]);
            printPart(list, left, right);
    
            // 对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值完整的排序
            quickSort(list, left, base - 1);
    
            // 对“基准标号“右侧的一组数值进行递归的切割，以至于将这些数值完整的排序
            quickSort(list, base + 1, right);
        }
    }

C++:

#include <stdio.h>
    #include <stdlib.h>
    
    void display(int* array, int size) { 
        for (int i = 0; i < size; i++) { 
            printf("%d ", array[i]);
        }
        printf("\n");
    }
    
    int getStandard(int array[], int i, int j) { 
        // 基准数据
        int key = array[i];
        while (i < j) { 
            // 因为默认基准是从左边开始，所以从右边开始比较
            // 当队尾的元素大于等于基准数据 时,就一直向前挪动 j 指针
            while (i < j && array[j] >= key) { 
                j--;
            }
            // 当找到比 array[i] 小的时，就把后面的值 array[j] 赋给它
            if (i < j) { 
                array[i] = array[j];
            }
            // 当队首元素小于等于基准数据 时,就一直向后挪动 i 指针
            while (i < j && array[i] <= key) { 
                i++;
            }
            // 当找到比 array[j] 大的时，就把前面的值 array[i] 赋给它
            if (i < j) { 
                array[j] = array[i];
            }
        }
        // 跳出循环时 i 和 j 相等,此时的 i 或 j 就是 key 的正确索引位置
        // 把基准数据赋给正确位置
        array[i] = key;
        return i;
    }
    
    void QuickSort(int array[], int low, int high) { 
        // 开始默认基准为 low
        if (low < high) { 
            // 分段位置下标
            int standard = getStandard(array, low, high);
            // 递归调用排序
            // 左边排序
            QuickSort(array, low, standard - 1);
            // 右边排序
            QuickSort(array, standard + 1, high);
        }
    }
    
    // 合并到一起快速排序
    // void QuickSort(int array[], int low, int high) { 
    // if (low < high) { 
    // int i = low;
    // int j = high;
    // int key = array[i];
    // while (i < j) { 
    // while (i < j && array[j] >= key) { 
    // j--;
    // }
    // if (i < j) { 
    // array[i] = array[j];
    // }
    // while (i < j && array[i] <= key) { 
    // i++;
    // }
    // if (i < j) { 
    // array[j] = array[i];
    // }
    // }
    // array[i] = key;
    // QuickSort(array, low, i - 1);
    // QuickSort(array, i + 1, high);
    // }
    // }
    
    int main() { 
        int array[] = { 49, 38, 65, 97, 76, 13, 27, 49, 10};
        int size    = sizeof(array) / sizeof(int);
    
        // 打印数据
        printf("%d \n", size);
        QuickSort(array, 0, size - 1);
        display(array, size);
    
        // int size = 20;
        // int array[20] = {0}; // 数组初始化
        // for (int i = 0; i < 10; i++) { // 数组个数
        // for (int j = 0; j < size; j++) { // 数组大小
        // array[j] = rand() % 1000; // 随机生成数大小 0~999
        // }
        // printf("原来的数组：");
        // display(array, size);
        // QuickSort(array, 0, size - 1);
        // printf("排序后数组：");
        // display(array, size);
        // printf("\n");
        // }
    
        return 0;
    }

#include<iostream>
    using namespace std;
    int n,a[1000001];
    void qsort(int l,int r)//应用二分思想
    { 
        int mid=a[(l+r)/2];//中间数
        int i=l,j=r;
        do{ 
            while(a[i]<mid) i++;//查找左半部分比中间数大的数
            while(a[j]>mid) j--;//查找右半部分比中间数小的数
            if(i<=j)//如果有一组不满足排序条件（左小右大）的数
            { 
                swap(a[i],a[j]);//交换
                i++;
                j--;
            }
        }while(i<=j);//这里注意要有=
        if(l<j) qsort(l,j);//递归搜索左半部分
        if(i<r) qsort(i,r);//递归搜索右半部分
    }
    int main()
    { 
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        qsort(1,n);
        for(int i=1;i<=n;i++) cout<<a[i]<<" ";
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70 2]

**快速排序算法的性能**

![img][img 8]

**时间复杂度**

当数据有序时，以第一个关键字为基准分为两个子序列，前一个子序列为空，此时执行效率最差。

而当数据随机分布时，以第一个关键字为基准分为两个子序列，两个子序列的元素个数接近相等，此时执行效率最好。

所以，数据越随机分布时，快速排序性能越好；数据越接近有序，快速排序性能越差。

**空间复杂度**

快速排序在每次分割的过程中，需要 1 个空间存储基准值。而快速排序的大概需要 Nlog2N次的分割处理，所以占用空间也是 Nlog2N 个。

**算法稳定性**

在快速排序中，相等元素可能会因为分区而交换顺序，所以它是不稳定的算法。

时间复杂度：

最好： O ( n l o g 2 n ) O(n log\_\{2\} n) O(nlog2n)  
最坏： O ( n 2 ) O(n^2) O(n2)  
平均： O ( n l o g 2 n ) O(n log\_\{2\} n) O(nlog2n)  
空间复杂度： O ( n l o g 2 n ) O(n log\_\{2\} n) O(nlog2n)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70 3]

# 5\# 堆排序（heapSort） #

**简介**

堆排序（英语：Heapsort）是指利用 二叉堆 这种数据结构所设计的一种排序算法。堆排序的适用数据结构为数组。

**工作原理**

本质是建立在堆上的选择排序。

**排序过程**  
首先建立大顶堆，然后将堆顶的元素取出，作为最大值，与数组尾部的元素交换，并维持残余堆的性质；

之后将堆顶的元素取出，作为次大值，与数组倒数第二位元素交换，并维持残余堆的性质；

以此类推，在第n-1 次操作后，整个数组就完成了排序。

**在数组上建立二叉堆**

从根节点开始，依次将每一层的节点排列在数组里。

于是有数组中下标为 i 的节点，对应的父结点、左子结点和右子结点如下：

iParent(i) = (i - 1) / 2;
    iLeftChild(i) = 2 * i + 1;
    iRightChild(i) = 2 * i + 2;

**算法评估**  
稳定性：不稳定，如同选择排序  
速度：O(nlogn)，算是高效算法  
空间：由于可以在输入数组上建立堆，所以这是一个原地算法。

// C++ Version
    void sift_down(int arr[], int start, int end) { 
      // 计算父结点和子结点的下标
      int parent = start;
      int child = parent * 2 + 1;
      while (child <= end) {   // 子结点下标在范围内才做比较
        // 先比较两个子结点大小，选择最大的
        if (child + 1 <= end && arr[child] < arr[child + 1]) child++;
        // 如果父结点比子结点大，代表调整完毕，直接跳出函数
        if (arr[parent] >= arr[child])
          return;
        else {   // 否则交换父子内容，子结点再和孙结点比较
          swap(arr[parent], arr[child]);
          parent = child;
          child = parent * 2 + 1;
        }
      }
    }
    
    void heap_sort(int arr[], int len) { 
      // 从最后一个节点的父节点开始 sift down 以完成堆化 (heapify)
      for (int i = (len - 1 - 1) / 2; i >= 0; i--) sift_down(arr, i, len - 1);
      // 先将第一个元素和已经排好的元素前一位做交换，再重新调整（刚调整的元素之前的元素），直到排序完毕
      for (int i = len - 1; i > 0; i--) { 
        swap(arr[0], arr[i]);
        sift_down(arr, 0, i - 1);
      }
    }

# 6\# 归并排序（mergeSort） #

归并排序（英语：Merge sort，或 mergesort），是创建在归并操作上的一种有效的排序算法。1945年由约翰·冯·诺伊曼首次提出。

该算法是采用分治法（ Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 12]

*  分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。
 *  再来看看 治 阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将【45,7，8】和【1,2,3,6】  
    两个已经有序的子序列，合并为最终序列【1,2,3,4,5,6,7,8】，来看下实现步骤

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 13]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 14]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70 5]  
伪代码  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70 6]

归并排序评估：

*  最好最坏平均时间复杂度nlogn
 *  空间复杂度高O(n)
 *  是高效算法中唯一“稳定”的排序算法
 *  较少用于内部排序，较多用于外部排序

模板：

// C++ Version
    void merge(int ll, int rr) { 
      // 用来把 a 数组 [ll, rr - 1] 这一区间的数排序。 t
      // 数组是临时存放有序的版本用的。
      if (rr - ll <= 1) return;
      int mid = ll + (rr - ll >> 1);
      merge(ll, mid);
      merge(mid, rr);
      int p = ll, q = mid, s = ll;
      while (s < rr) { 
        if (p >= mid || (q < rr && a[p] > a[q])) { 
          t[s++] = a[q++];
          // ans += mid - p;
        } else
          t[s++] = a[p++];
      }
      for (int i = ll; i < rr; ++i) a[i] = t[i];
    }
    // 关键点在于一次性创建数组，避免在每次递归调用时创建，以避免内存分配的耗时。

我们发现去掉代码中的注释，ans中保存的就是逆序对的数量

# 7\# 插入排序（Insertion Sort） #

**基本思想：每一步将一个待排序的数据插入到前面已经排好序的有序序列中，直到插完所有元素为止。**

![img][img 9]

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

![img][img 10]

程序在设计的时候应该注意一些点：每次要定一个基准数，逐个比较，覆盖的时候要留有备份。

C++函数代码：

void insertion_sort(int arr[],int len){ 
            for(int i=1;i<len;i++){ 
                    int key=arr[i]; // 标兵
                    int j=i-1;
                    while((j>=0) && (key<arr[j])){  // 后移操作
                            arr[j+1]=arr[j];
                            j--;
                    }
                    arr[j+1]=key; // 最终赋值标兵
            }
    }

C\#函数代码：

public static void InsertSort(int[] array)
    { 
        for(int i = 1;i < array.length;i++)
        { 
            int temp = array[i];
            for(int j = i - 1;j >= 0;j--)
            { 
                if(array[j] > temp)
                { 
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
                else
                    break;
            }
        }
    }

程序需要，把这个函数复制，传递对应参数。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70 7]

在插入排序中，我们可以用二分法来优化，从而更快确定数字  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70 8]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70 9]

# 8\# 选择排序（Selection sort） #

选择排序是一种**最**简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

这是首批的O(n2)算法，如下是算法步骤。

1.  首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
2.  再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3.  重复第二步，直到所有元素均排序完毕。

C 语言

void swap(int *a,int *b) 
    { 
      int temp = *a;
      *a = *b;
      *b = temp;
    }
    void selection_sort(int arr[], int len)
    { 
      int i,j;
      for (i = 0 ; i < len - 1 ; i++)
      { 
            int min = i;
            for (j = i + 1; j < len; j++)   
                if (arr[j] < arr[min])   
                    min = j;   
            swap(&arr[min], &arr[i]);   
      }
    }

注：这种排序算法非常的\*\*慢！慢！慢！\*\*初学者可以使用这种算法，进阶后绝对不要使用这种算法，至少也要用上插入排序、桶排序之类的，除非排序时n<10000，或者简单的做个测试的时候使用。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 15]

# 9\# 计数排序（CountingSort） #

**评估**  
稳定性：稳定  
速度：O(n+m)，m代表待排序数据的值域大小

工作原理：  
计数排序的工作原理是使用一个额外的数组 C，其中第 i个元素是待排序数组 A 中值等于 i的元素的个数，然后根据数组 C来将 A中的元素排到正确的位置。

它的工作过程分为三个步骤：

1.  计算每个数出现了几次；
2.  求出每个数出现次数的 前缀和；
3.  利用出现次数的前缀和，从右至左计算每个数的排名。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70 10]

// C++ Version
    const int N = 100010;
    const int W = 100010;
    
    int n, w, a[N], cnt[W], b[N];
    
    void counting_sort() { 
      memset(cnt, 0, sizeof(cnt));
      for (int i = 1; i <= n; ++i) ++cnt[a[i]];
      for (int i = 1; i <= w; ++i) cnt[i] += cnt[i - 1];
      for (int i = n; i >= 1; --i) b[cnt[a[i]]--] = a[i];
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70 11]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70 12]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70 13]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70 14]

# 10\# 桶排序（bucketSort） #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 16]

桶排序评估：  
速度：O(n)  
空间复杂度：需要建立一个容量为输入数字中的最大数+1的数组，所以空间复杂度超高，所以输入数字最好不要超过10000000

// C++ Version
    #include <iostream>
    #include <cstring>
    using namespace std;
    #define N 100010
    int a[N];
    int n, t;
    int main()
    { 
    	memset(a, 0, sizeof(a));
    	cin >> n;
    	for (int i = 0; i < n; i++)
    	{ 
    		cin >> t;
    		a[t]++;
    	}
    	// 从小到大，要从大到小只需要改一下for循环开头
    	// for (int i = N - 1; i >= 0; i--)
    	for(int i = 0; i < N; i++)
    	{ 
    		for (int j = 0; j < a[i]; j++)
    			cout << i << " " ;
    	}
    	cout << endl;
    	return 0;
    }

# PS\#桶排序&计数排序&基数排序 #

基数排序有两种方法：

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

*  基数排序：根据键值的每位数字来分配桶；
 *  计数排序：每个桶只存储单一键值；
 *  桶排序：每个桶存储一定范围的数值；

# 参考资料 #

*  漫画科普排序时间复杂度：[https://blog.csdn.net/qq\_41523096/article/details/82142747][https_blog.csdn.net_qq_41523096_article_details_82142747]
 *  时间复杂度：[https://zh.wikipedia.org/wiki/时间复杂度][https_zh.wikipedia.org_wiki]
 *  对数（logarithm）：[https://baike.baidu.com/item/对数/91326?fromtitle=log&fromid=39110&fr=aladdin][https_baike.baidu.com_item_91326_fromtitle_log_fromid_39110_fr_aladdin]
 *  如何理解对数：[https://www.zhihu.com/question/26097157/answer/265975884][https_www.zhihu.com_question_26097157_answer_265975884]
 *  基数排序：[https://www.runoob.com/w3cnote/radix-sort.html][https_www.runoob.com_w3cnote_radix-sort.html]
 *  基数排序：[https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/10.radixSort.md][https_github.com_hustcc_JS-Sorting-Algorithm_blob_master_10.radixSort.md]
 *  冒泡排序-三分钟彻底理解冒泡排序：[https://www.cnblogs.com/bigdata-stone/p/10464243.html][https_www.cnblogs.com_bigdata-stone_p_10464243.html]
 *  冒泡排序：[https://github.com/Github-Programer/JS-Sorting-Algorithm/blob/master/1.bubbleSort.md][https_github.com_Github-Programer_JS-Sorting-Algorithm_blob_master_1.bubbleSort.md]
 *  插入排序（插入排序（图解））：[https://blog.csdn.net/qq\_33289077/article/details/90370899][https_blog.csdn.net_qq_33289077_article_details_90370899]
 *  十大经典排序算法（动图演示）：[https://zhuanlan.zhihu.com/p/73714165][https_zhuanlan.zhihu.com_p_73714165] （知乎，引用图片和简介）
 *  百度百科，选择排序：[https://baike.baidu.com/item/选择排序/9762418?fr=aladdin][https_baike.baidu.com_item_9762418_fr_aladdin]
 *  希尔排序，CSDN：[https://blog.csdn.net/qq\_39207948/article/details/80006224][https_blog.csdn.net_qq_39207948_article_details_80006224]
 *  希尔排序，百度百科：[https://baike.baidu.com/item/希尔排序][https_baike.baidu.com_item]
 *  快速排序算法详解（原理、实现和时间复杂度）:[http://data.biancheng.net/view/117.html][http_data.biancheng.net_view_117.html]
 *  快排：[https://www.jianshu.com/p/5f38dd54b11f][https_www.jianshu.com_p_5f38dd54b11f]
 *  《排序算法和高精度运算》贾志勇，中国计算机学会
 *  桶排序：[https://oi-wiki.org/basic/heap-sort/][https_oi-wiki.org_basic_heap-sort]
 *  计数排序：[https://oi-wiki.org/basic/counting-sort/][https_oi-wiki.org_basic_counting-sort]

# 参考书目 #

*  《信息学奥赛课课通》
 *  《信息学奥赛一本通，C++篇》
 *  《啊哈！算法》
 *  《数据结构与算法分析，C语言描述》\[美\]马克·艾伦·维斯 著

# 参考程序 #

我将7种常用排序放集合在了一个程序里，你只需要在文件的同目录下创建一个`RandintModel.txt`，其中的输入格式如下

n   (一共n个数，至少大于1000，要不然测不出速度，当然你可以自己写一个随机数生成程序)
    n个数

输出的是排序时间和一个文件Lastlog.txt，里面是最后一次的排序结果，不要用notepad打开，会卡死。（建议使用notepad++）

// SortingSpeed.cpp : This file contains the 'main' function. Program execution begins and ends there.
    //
    
    #include <iostream>
    #include <windows.h>
    #include <cstdio>
    #include <fstream>
    #include <vector>
    #include <array>
    #include <algorithm>
    #include <numeric>
    //numeric_limits
    using namespace std;
    DWORD time_start, time_end;
    int a[100010], n;
    
    void max_heapify(int arr[], int start, int end) { 
        int dad = start;
        int son = dad * 2 + 1;
        while (son <= end) { 
            if (son + 1 <= end && arr[son] < arr[son + 1])
                son++;
            if (arr[dad] > arr[son])
                return;
            else { 
                swap(arr[dad], arr[son]);
                dad = son;
                son = dad * 2 + 1;
            }
        }
    }
    
    void heap_sort(int arr[], int len) { 
        for (int i = len / 2 - 1; i >= 0; i--)
            max_heapify(arr, i, len - 1);
        for (int i = len - 1; i > 0; i--) { 
            swap(arr[0], arr[i]);
            max_heapify(arr, 0, i - 1);
        }
    }
    typedef struct _Range { 
        int start, end;
    } Range;
    
    Range new_Range(int s, int e) { 
        Range r;
        r.start = s;
        r.end = e;
        return r;
    }
    
    void swap(int* x, int* y) { 
        int t = *x;
        *x = *y;
        *y = t;
    }
    
    void quick_sort(int arr[], const int len) { 
        if (len <= 0)
            return;
        Range* r = new Range[len];
        int p = 0;
        r[p++] = new_Range(0, len - 1);
        while (p) { 
            Range range = r[--p];
            if (range.start >= range.end)
                continue;
            int mid = arr[(range.start + range.end) / 2];
            int left = range.start, right = range.end;
            do { 
                while (arr[left] < mid) ++left;
                while (arr[right] > mid) --right;
                if (left <= right) { 
                    swap(&arr[left], &arr[right]);
                    left++;
                    right--;
                }
            } while (left <= right);
            if (range.start < right) r[p++] = new_Range(range.start, right);
            if (range.end > left) r[p++] = new_Range(left, range.end);
        }
    }
    //void Merge(vector<int>& Array, int front, int mid, int end) { 
    // // preconditions:
    // // Array[front...mid] is sorted
    // // Array[mid+1 ... end] is sorted
    // // Copy Array[front ... mid] to LeftSubArray
    // // Copy Array[mid+1 ... end] to RightSubArray
    // vector<int> LeftSubArray(Array.begin() + front, Array.begin() + mid + 1);
    // vector<int> RightSubArray(Array.begin() + mid + 1, Array.begin() + end + 1);
    // int idxLeft = 0, idxRight = 0;
    // LeftSubArray.insert(LeftSubArray.end(), numeric_limits<int>::max());
    // RightSubArray.insert(RightSubArray.end(), numeric_limits<int>::max());
    // // Pick min of LeftSubArray[idxLeft] and RightSubArray[idxRight], and put into Array[i]
    // for (int i = front; i <= end; i++) { 
    // if (LeftSubArray[idxLeft] < RightSubArray[idxRight]) { 
    // Array[i] = LeftSubArray[idxLeft];
    // idxLeft++;
    // }
    // else { 
    // Array[i] = RightSubArray[idxRight];
    // idxRight++;
    // }
    // }
    //}
    //
    //void MergeSort_Rec(vector<int>& Array, int front, int end) { 
    // if (front >= end)
    // return;
    // int mid = (front + end) / 2;
    // MergeSort_Rec(Array, front, mid);
    // MergeSort_Rec(Array, mid + 1, end);
    // Merge(Array, front, mid, end);
    //}
    void insertion_sort(int arr[], int len) { 
        for (int i = 1; i < len; i++) { 
            int key = arr[i];
            int j = i - 1;
            while ((j >= 0) && (key < arr[j])) { 
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
    int maxbit(int data[], int n) //辅助函数，求数据的最大位数
    { 
        int maxData = data[0];              ///< 最大数
        /// 先求出最大数，再求其位数，这样有原先依次每个数判断其位数，稍微优化点。
        for (int i = 1; i < n; ++i)
        { 
            if (maxData < data[i])
                maxData = data[i];
        }
        int d = 1;
        int p = 10;
        while (maxData >= p)
        { 
            //p *= 10; // Maybe overflow
            maxData /= 10;
            ++d;
        }
        return d;
        /* int d = 1; //保存最大的位数 int p = 10; for(int i = 0; i < n; ++i) { while(data[i] >= p) { p *= 10; ++d; } } return d;*/
    }
    void radixsort(int data[], int n) //基数排序
    { 
        int d = maxbit(data, n);
        int* tmp = new int[n];
        int* count = new int[10]; //计数器
        int i, j, k;
        int radix = 1;
        for (i = 1; i <= d; i++) //进行d次排序
        { 
            for (j = 0; j < 10; j++)
                count[j] = 0; //每次分配前清空计数器
            for (j = 0; j < n; j++)
            { 
                k = (data[j] / radix) % 10; //统计每个桶中的记录数
                count[k]++;
            }
            for (j = 1; j < 10; j++)
                count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
            for (j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
            { 
                k = (data[j] / radix) % 10;
                tmp[count[k] - 1] = data[j];
                count[k]--;
            }
            for (j = 0; j < n; j++) //将临时数组的内容复制到data中
                data[j] = tmp[j];
            radix = radix * 10;
        }
        delete[]tmp;
        delete[]count;
    }
    void selection_sort(int arr[], int len)
    { 
        int i, j;
        for (i = 0; i < len - 1; i++)
        { 
            for (j = i + 1; j < len; j++)
                if (arr[j] < arr[i])
                    swap(arr[j], arr[i]);    
        }
    }
    void shell_sort(int arr[], int len) { 
        int gap, i, j;
        int temp;
        for (gap = len >> 1; gap > 0; gap >>= 1)
            for (i = gap; i < len; i++) { 
                temp = arr[i];
                for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                    arr[j + gap] = arr[j];
                arr[j + gap] = temp;
            }
    }
    void bubble_sort(int arr[], int len)
    { 
        int i, j, temp;
        for (i = 0; i < len - 1; i++)
            for (j = 0; j < len - 1 - i; j++)
                if (arr[j] > arr[j + 1]) { 
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
    }
    void menu()
    { 
        printf("Sorting Algorithm\n------------------\n");
        printf("1.希尔排序\n");
        printf("2.冒泡排序\n");
        printf("3.选择排序\n");
        printf("4.基数排序\n");
        printf("5.插入排序\n");
        printf("6.堆排序\n");
        printf("7.快速排序\n");
        // new
        printf("--Choose Number--\n------------------\n");
    }
    void game()
    { 
        menu();
        int choose;
        cin >> choose;
        time_start = GetTickCount();
        if (choose == 1)
            shell_sort(a, n);
        else if (choose == 2)
            bubble_sort(a, n);
        else if (choose == 3)
            selection_sort(a, n);
        else if (choose == 4)
            radixsort(a, n);
        else if (choose == 5)
            insertion_sort(a, n);
        else if (choose == 6)
            heap_sort(a, n);
        else if (choose == 7)
            quick_sort(a, n);
        // new
        time_end = GetTickCount();
        cout << "Time = " << (time_end - time_start) << "ms\n ";
    }
    int main()
    { 
        ifstream fin("RandintModel.txt");
        ofstream fout("Lastlog.txt");
        fin >> n;
        for (int i = 0; i < n; i++)
            fin >> a[i];
        game();
        printf("-----排序结果-----\n");
        for (int i = 0; i < n; i++)
        { 
            fout << a[i] << " ";
        } fout << endl;
    
        std::cout << "Hello World!\n";
        return 0;
    }

# 参考习题 #

[P1097 \[NOIP2007 提高组\] 统计数字][P1097 _NOIP2007 _]

[P1093 \[NOIP2007 普及组\] 奖学金][P1093 _NOIP2007 _]

[P1059 \[NOIP2006 普及组\] 明明的随机数][P1059 _NOIP2006 _]

[P1094 \[NOIP2007 普及组\] 纪念品分组][P1094 _NOIP2007 _]

[P1161 开灯][P1161]

洛谷中选择`排序`算法题目可以找到更多题目。

[img]: /images/20220829/a86d463417214d7f96aee10c01caa623.png
[img 1]: /images/20220829/bb528da224154f3897ac80e2a384edf2.png
[Link 1]: https://zh.wikipedia.org/wiki/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6
[Link 2]: https://zh.wikipedia.org/wiki/%E7%AE%97%E6%B3%95
[Link 3]: https://zh.wikipedia.org/wiki/%E5%87%BD%E6%95%B0
[Link 4]: https://zh.wikipedia.org/wiki/%E5%AD%97%E7%AC%A6%E4%B8%B2
[O]: https://zh.wikipedia.org/wiki/%E5%A4%A7O%E7%AC%A6%E5%8F%B7
[Link 5]: https://zh.wikipedia.org/wiki/%E6%B8%90%E8%BF%91%E5%88%86%E6%9E%90
[Link 6]: https://zh.wikipedia.org/w/index.php?title=%E6%9C%80%E5%A3%9E%E6%83%85%E6%B3%81%E8%A4%87%E9%9B%9C%E5%BA%A6&action=edit&redlink=1
[Link 7]: https://zh.wikipedia.org/w/index.php?title=%E5%B9%B3%E5%9D%87%E6%83%85%E6%B3%81%E8%A4%87%E9%9B%9C%E5%BA%A6&action=edit&redlink=1
[640_wx_fmt_jpeg]: /images/20220829/ab1a4f8d58bd4650a001658ae06bcc7e.png
[640_wx_fmt_jpeg 1]: /images/20220829/1171dbeab1864d458a65dd4ac6afb99e.png
[640_wx_fmt_jpeg 2]: /images/20220829/d68c9e84ab1a4b9e944512eb9d6648af.png
[640_wx_fmt_jpeg 3]: /images/20220829/8cb70b8bd49f4d8d94611b3441b5a332.png
[640_wx_fmt_jpeg 4]: /images/20220829/11c040e89fda4996bc351fc05089d9fa.png
[640_wx_fmt_jpeg 5]: /images/20220829/43cc7aaa588b4f6a8a9b41c9e8c92261.png
[640_wx_fmt_jpeg 6]: /images/20220829/8bef02f2bc234801b2f2bdf3bd3d0946.png
[640_wx_fmt_jpeg 7]: /images/20220829/c513fa9e8c5147498b0f30dfb37c398b.png
[640_wx_fmt_png]: /images/20220829/773ddbd67be74856b93b90b5959737ed.png
[640_wx_fmt_png 1]: /images/20220829/6e33034df7e74b68acccc791de4f4746.png
[640_wx_fmt_png 2]: /images/20220829/822b95ad07cf4d4ab69ebf32f438c27a.png
[640_wx_fmt_png 3]: /images/20220829/a3dce7253ef141bf937cb62854d8f0d6.png
[640_wx_fmt_png 4]: /images/20220829/7f9bed7aba7f4a0086bbc51e396b06fb.png
[Link 8]: https://baike.baidu.com/item/%E5%BA%95%E6%95%B0/5416651
[Link 9]: https://baike.baidu.com/item/%E7%9C%9F%E6%95%B0/20402544
[img 2]: /images/20220829/d5bfa191069e4da18f78bed84e0b7349.png
[img 3]: /images/20220829/bc762ef947204b048126ff0edf153f2d.png
[img 4]: /images/20220829/432ccba41555437185f9fd2004c3e7af.png
[https_visualgo.net_zh_sorting]: https://visualgo.net/zh/sorting
[f5af707e866748acbddc91373bf5bf6a.gif_pic_center]: /images/20220829/fb36bd497ba14d55a9928e6fd85f9afa.png
[img 5]: /images/20220829/4ab01e3c959445b08e028be608c4a8ff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70]: /images/20220829/ea9e18a1817e4f0db8a1e83c63eccf44.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20220829/a4da7959da6a4ee8be2fe3662fd912f4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20220829/b17e669916624e5390a37bd924f21b3a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20220829/36ee2743ae0a47acab1819bbe160407c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20220829/7f2abd2b755b4e8eadbf8ee346968795.png
[Link 10]: https://baike.baidu.com/item/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/5399605
[Link 11]: https://baike.baidu.com/item/%E9%AB%98%E6%95%88/6764908
[Link 12]: https://baike.baidu.com/item/%E5%85%B3%E9%94%AE%E8%AF%8D/254446
[Link 13]: https://baike.baidu.com/item/%E7%AE%97%E6%B3%95/209025
[Link 14]: https://baike.baidu.com/item/%E5%A2%9E%E9%87%8F
[Link 15]: https://baike.baidu.com/item/%E7%9B%B4%E6%8E%A5%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F
[Link 16]: https://baike.baidu.com/item/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95
[45094c75d8417b7d87db86803ff89610.png]: https://img-blog.csdnimg.cn/img_convert/45094c75d8417b7d87db86803ff89610.png
[45094c75d8417b7d87db86803ff89610.png 1]: /images/20220829/89371e141fb846d4966e4e9573f90cd4.png
[img 6]: /images/20220829/8ca3d6ac0320462a9e58aebc40240ab8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20220829/01174158ba0240be87cf4514b3835dd0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20220829/2444a53fdd7e494cb3ca56fc0ccb5b69.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20220829/e9c0562c24b7428a82509608f8c1c21d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20220829/ff23c205381941b7bb4ff3c14e125d17.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20220829/c8ef428af47948b98389a61a7c083b01.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20220829/50862c2673fc44f3a467ced748c0db81.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20220829/557fc82cfde6488880c62dbbfcfa98ef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 11]: /images/20220829/e07b2d49351846feadb49ee166a9bed2.png
[img 7]: /images/20220829/148943626380482aade5414ea1f2b7b5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]: /images/20220829/d3e558903b0d43da8b1aa0757cde3758.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70 1]: /images/20220829/04a13b91ec954f9895601cc8508f0246.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70 2]: /images/20220829/563ed842a3794d0a9e5bb8d6f154e813.png
[img 8]: /images/20220829/346282f50046478890da10810c827c86.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70 3]: /images/20220829/4478089f3d8e45faa15821f5f6855c16.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 12]: /images/20220829/b8c0d15c5c7549bebc6d447f4af4eff6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 13]: /images/20220829/2960f3d2af0c40829626a05facb7d062.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 14]: /images/20220829/11133e2f92ed479287a3cf9826bedd1f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70 4]: /images/20220829/e4d0a698aa3b469f93623a46a13e1c7e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70 5]: /images/20220829/337394d68d554be781666314a10336b5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70 6]: /images/20220829/2dd95ce7b927409093e91cfacdb9c7eb.png
[img 9]: /images/20220829/ae6e75fe4fd54d6b80625bc52eebebb9.png
[img 10]: /images/20220829/c828c76f1929489a909e2533973bd538.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70 7]: /images/20220829/40528030cb1f45bdb1d68fd4ca44a9c8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70 8]: /images/20220829/f9c76a05a8dd4980820ce983ab66e14a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70 9]: /images/20220829/876e28f199124c659df43a1a36202b17.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 15]: /images/20220829/41609d784c2d4dbb99d3ce41a6fcabe5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70 10]: /images/20220829/f10b5989d2bf4dd5a1ab8fbecfd45994.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70 11]: /images/20220829/88c08c7f7fb941579bee162573436613.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70 12]: /images/20220829/1c0ca05f38aa43e897a7078d0d34901b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70 13]: /images/20220829/30de441ac113433fa47e326c1a4364ce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70 14]: /images/20220829/d3aa0a8b4ed844c3805dda8730314939.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 16]: /images/20220829/6c51ade067df4ed189d8c03e515aa359.png
[https_blog.csdn.net_qq_41523096_article_details_82142747]: https://blog.csdn.net/qq_41523096/article/details/82142747
[https_zh.wikipedia.org_wiki]: https://zh.wikipedia.org/wiki/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6
[https_baike.baidu.com_item_91326_fromtitle_log_fromid_39110_fr_aladdin]: https://baike.baidu.com/item/%E5%AF%B9%E6%95%B0/91326?fromtitle=log&fromid=39110&fr=aladdin
[https_www.zhihu.com_question_26097157_answer_265975884]: https://www.zhihu.com/question/26097157/answer/265975884
[https_www.runoob.com_w3cnote_radix-sort.html]: https://www.runoob.com/w3cnote/radix-sort.html
[https_github.com_hustcc_JS-Sorting-Algorithm_blob_master_10.radixSort.md]: https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/10.radixSort.md
[https_www.cnblogs.com_bigdata-stone_p_10464243.html]: https://www.cnblogs.com/bigdata-stone/p/10464243.html
[https_github.com_Github-Programer_JS-Sorting-Algorithm_blob_master_1.bubbleSort.md]: https://github.com/Github-Programer/JS-Sorting-Algorithm/blob/master/1.bubbleSort.md
[https_blog.csdn.net_qq_33289077_article_details_90370899]: https://blog.csdn.net/qq_33289077/article/details/90370899
[https_zhuanlan.zhihu.com_p_73714165]: https://zhuanlan.zhihu.com/p/73714165
[https_baike.baidu.com_item_9762418_fr_aladdin]: https://baike.baidu.com/item/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F/9762418?fr=aladdin
[https_blog.csdn.net_qq_39207948_article_details_80006224]: https://blog.csdn.net/qq_39207948/article/details/80006224
[https_baike.baidu.com_item]: https://baike.baidu.com/item/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F
[http_data.biancheng.net_view_117.html]: http://data.biancheng.net/view/117.html
[https_www.jianshu.com_p_5f38dd54b11f]: https://www.jianshu.com/p/5f38dd54b11f
[https_oi-wiki.org_basic_heap-sort]: https://oi-wiki.org/basic/heap-sort/
[https_oi-wiki.org_basic_counting-sort]: https://oi-wiki.org/basic/counting-sort/
[P1097 _NOIP2007 _]: https://www.luogu.com.cn/problem/P1097
[P1093 _NOIP2007 _]: https://www.luogu.com.cn/problem/P1093
[P1059 _NOIP2006 _]: https://www.luogu.com.cn/problem/P1059
[P1094 _NOIP2007 _]: https://www.luogu.com.cn/problem/P1094
[P1161]: https://www.luogu.com.cn/problem/P1161