【算法专题】秒懂八种排序算法的原理

分手后的思念是犯贱 2023-10-05 22:59 44阅读 0赞

#### 文章目录 ####

*   *  一、衡量排序算法的指标
     *   *  1.1 算法的执行效率
         *  1.2 算法的内存消耗
         *  1.3 算法的排序稳定性
     *  二、O(n^2)的排序算法
     *   *  2.1 冒泡排序
         *  2.2 插入排序
         *  2.3 选择排序
         *  2.4 小结
     *  三、O(nlogn)的排序算法
     *   *  3.1 快速排序
         *  3.2 归并排序
         *  3.3 小结
     *  四、O(n)的排序算法
     *   *  4.1 桶排序
         *  4.2 计数排序
         *  4.3 基数排序
         *  4.4 小结
     *  五、排序算法总结

最经典最常用的排序算法有：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序和桶排序。这些排序算法可以按照时间复杂度分为三类：

*  O(n^2)——冒泡、插入、选择
 *  O(nlogn)——快速、归并
 *  O(n)——计数、基数、桶

### 一、衡量排序算法的指标 ###

#### 1.1 算法的执行效率 ####

*  最好、最坏和平均情况下的时间复杂度；
    
    原始数据的杂乱程度会导致同一种算法在不同情况下的时间复杂度呈现不同量级的差异，所以在选择排序算法的时候，需要给出这三个指标，结合实际业务情况的原始数据，来选择算法。
 *  时间复杂度的系数、常数和低阶；
    
    不同的排序算法可能会出现算法复杂度处在同一量级的情况，此时就需要根据时间复杂度的系数、常数和低阶来决定使用哪一种算法。
 *  算法的比较次数和移动次数；
    
    比较次数和移动次数会分别导致CPU和IO操作，所以也需要纳入到选择排序算法的指标中来。

#### 1.2 算法的内存消耗 ####

*  原地排序，是指空间复杂度为O(1)的排序算法，不需要借助很多外部存储空间就能完成排序；
 *  非原地排序，需要借助外部存储空间才能完成排序；

#### 1.3 算法的排序稳定性 ####

*  稳定，原始数据中相等的元素在排序后它们之间的顺序不发生改变；
 *  非稳定，原始数据中相等的元素在排序后它们之间的顺序有可能发生改变；

### 二、O(n^2)的排序算法 ###

#### 2.1 冒泡排序 ####

冒泡排序每次只会比较相邻的两个元素，只有在不满足要求的大小关系情况下，才会发生交换行为。一次冒泡迭代会让至少一个元素移动到它最终应该在的位置上，最多n次冒泡迭代，当某次冒泡迭代没有发生元素的交换行为，就可以判定数列已经完成了排序。

比如我们需要对如下数列进行从小到大的排列：

![img][]

冒泡排序过程示意图

对应的实现代码如下：

public static void main(String[] args) {
        
            int[] data = {
        4,5,6,3,2,1};
            int size = 6;
            log.info("原始数列为：{}",data);
            bubbleSort(data,size);
            log.info("冒泡排序后的结果为：{}",data);
        }
    
        public static void bubbleSort(int[] data, int n){
        
            if(n <= 1){
        
                log.info("数组中元素少于2个，无需进行排序！");
                return;
            }
    
            // 最多需要迭代n次冒泡
            for(int i=0;i<n;i++){
        
                // 表示当前迭代冒泡中是否发生了元素交换
                boolean switchFlag = false;
                for(int j=0;j<n-i-1;j++){
        
                    if(data[j] > data[j+1]){
        
                        // 不满足从小到大的关系，需要交换
                        int temp = data[j];
                        data[j] = data[j+1];
                        data[j+1] = temp;
                        switchFlag = true;
                    }
                }
    
                // 当前冒泡迭代中没有发生元素交换，说明数列已经有序，完成了排序，可以提前结束
                if(!switchFlag){
        
                    break;
                }
            }
        }

冒泡排序没有借助很多额外的存储空间，因此是原地排序；

冒泡排序只有在前后两个元素不满足大小关系时才发生交换，因此是稳定的排序算法；

最好情况下原始数列就是满足要求的大小关系的，那么只需要迭代一个冒泡就完成了排序，时间复杂度为O(n)；最坏情况下原始数列正好和要求的大小关系完全相反，那么需要迭代n此冒泡，因此时间复杂度为O(n^2)。

#### 2.2 插入排序 ####

插入排序将整个数列划分为已排序和未排序两个区间，初始情况下，已排序区间只有一个元素，那就是数列的第一个元素，然后重复取未排序区间中的元素逐个插入到已排序区间中，直至未排序区间元素数量为0，需要注意的是，将元素插入已排序区间会引起插入位置后方所有元素的移动。

比如，我们对如下数列进行插入排序的过程为：

![img][img 1]

插入排序过程示意图

对应的实现代码如下：

public static void main(String[] args) {
        
            int[] data = {
        4,5,6,3,2,1};
            int size = 6;
            log.info("原始数列为：{}",data);
            insertionSort(data,size);
            log.info("插入排序后的结果为：{}",data);
        }
    
        public static void insertionSort(int data[], int n){
        
            if(n <= 1){
        
                log.info("数组中元素少于2个，无需进行排序！");
                return;
            }
    
            // 从未排序区间开始遍历
            for(int i=1;i<n;i++){
        
                // 放到临时空间保存，因为后续已排序区间元素的向后移动会覆盖掉data[i]的值
                int value = data[i];
                int j=i-1;
                for(;j>=0;j--){
        
                    // 已排序区间从后往前遍历和当前需要插入的元素进行比较
                    if(data[j] > value){
        
                        // 当前已排序区间的元素往后移动一位
                        data[j+1] = data[j];
                    } else {
        
                        break;
                    }
                }
                // 插入到已排序区间中小于等于自己元素的后面，保证排序算法的稳定性
                data[j+1] = value;
            }
        }

插入排序没有借助很多额外的存储空间，因此是原地排序；

插入排序可以在算法中约定，将未排序区间的元素插入到排序区间相同元素的后方，因此也是稳定的排序算法；

最好情况下原始数列就是满足要求的大小关系的，那么只需要迭代一遍数列就完成了排序，时间复杂度为O(n)；最坏情况下，每将一个元素插入已排序区间，都会引起所有已排序区间元素的向后移动，那么时间复杂度就是O(n^2)。

#### 2.3 选择排序 ####

选择排序也是将整个数列分为已排序区间和未排序区间，和插入排序的区别是，每次迭代都是从未排序区间中寻找到最小值，然后将其和未排序区间中的第一个元素进行交换，直至未排序区间元素为空。

![img][img 2]

选择排序过程示意图

选择排序也是原地排序；

选择排序是不稳定的，在交换元素的时候，极有可能改变相同元素的前后顺序，比如：

1，2，| 5，4，5，3

此时未排序区间最小元素为3，会和未排序区间第一个元素5进行交换：

1，2，3，| 4，5，5

此时，未排序区间的两个5实际上已经发生了顺序上的变化，在排序完成后，它们也极有可能是维持现在变化了的顺序的。

最好情况和最坏情况下的时间复杂度都是O(n2)，无论最好还是最坏，每次迭代都要从未排序区间中找到最小值，每次找最小值的时间复杂度为O(n)，所以无论哪种情况，选择排序的时间复杂度都是O(n2)。

#### 2.4 小结 ####

冒泡排序和插入排序虽然时间复杂度在同一量级，并且都是稳定的、原地排序算法，但是通常来说，插入排序的性能要优于冒泡排序。因为插入排序的交换次数和赋值次数更少，在大数据量数列排序时，效果尤为明显。

插入排序还存在优化的空间，在大数据量和比较无序的情况下使用[希尔排序][Link 1]能很好地提升排序性能，希尔排序的核心思想是对数列按照增量序列进行逻辑分组，对分组的数列使用插入排序，保证基本有序，然后逐步减小增量序列，迭代进行插入排序。

希尔排序的时间复杂度视增量序列值的不同而不同，最坏情况是O(n^2)，并且不是稳定的排序算法。

总之，这三种排序算法的时间复杂度都是O(n^2)，比较适合小数据量的排序场景。

### 三、O(nlogn)的排序算法 ###

#### 3.1 快速排序 ####

快速排序是由冒泡排序进化而来，能够迭代更少的次数，更加快速地完成排序，因此得名。其使用了分治思想和递归的实现方式，其大致的思路如下：

*  选取最前面或者最后面的一个元素作为基准元素（我们以最前面一个元素作为基准元素为例），并在数列的头部left和尾部right上各设置一个指针；
 *  从right开始将元素和基准元素比较，如果大于等于基准元素，则right-1，如果小于基准元素，那么将right的值赋值到left所在的位置，然后切换到left，left+=1，将此时的left元素和基准元素比较，如果小于等于基准元素，则left+1，如果大于基准元素，那么将left的值赋值到right所在的位置；
 *  对如上过程递归迭代，直至left=right，然后将它们指向的元素赋值为基准元素，此时就完成了排序；

排序过程示意图可以参考：[什么是快速排序][Link 2]

快速排序在排序的过程中并不会借助很多的额外存储空间，因此属于原地排序；

快速排序可能会改变相同元素的顺序，因此是不稳定的排序算法；

快速排序的时间复杂度是O(nlogn)，前提是每次递归选取的基准元素正好可以将数列分成两个差不多的子数列，在最坏情况下，每次选取的基准元素不是最大值就是最小值的话，那么时间复杂度就会退化为O(n^2)。

#### 3.2 归并排序 ####

归并排序也是使用了分治思想和递归的实现方式，其大致的思路如下：

*  找到待排序数列的中间位置，将数列分解成前后两个子数列；
 *  使用同样的方法迭代分解子数列，直至所有子数列都只有一个元素为止；
 *  使用额外的存储空间从下往上，开始合并相邻子数列，直至合并为一个数列为止，即完成了排序；

分解和合并的大致示意图如下：

![img][img 3]

归并排序的分解合并过程

需要注意的是，在合并的过程中，算法需要借助额外的存储空间来合并相邻的两个子数列，合并的过程如下：

![img][img 4]

归并排序合并过程示意图

递归的代码示例如下：

public static void MergeSort(int[] data, int begin, int end){
        
        if(begin >= end){
        
            log.info("当前子数列仅有一个元素，无需再分解");
            return;
        }
        int middle = (begin + end) / 2;
        MergeSort(data,begin,middle);
        MergeSort(data,middle+1,end);
        
        Merge(data,begin,middle,end);
    }

归并排序在合并的时候需要借助很多额外的存储空间，空间复杂度为O(n)，因此它不是原地排序算法；

归并排序在合并的时候，我们可以通过代码控制相同的元素保持原始数列的顺序，因此是稳定的；

归并排序在任何情况下的时间复杂度都是O(nlogn)；

#### 3.3 小结 ####

快速排序和归并排序都是比较复杂的排序算法，它们都是采用了分治思想和递归的实现方法，区别在于：

*  快速排序是自上而下地进行排序，归并排序是先分解然后再自下而上地完成排序；
 *  快速排序平均时间复杂度是O(nlogn)，但是最坏情况会退化为O(n^2)，虽然概率很小，但是归并排序在任何情况下时间复杂度都是O(nlogn)；
 *  快速排序是不稳定的，属于原地排序算法，归并排序是稳定的，属于非原地排序算法；
 *  因为归并排序的空间复杂度是O(n)，所以相对来说，快速排序更加受欢迎，并被使用地最多；

### 四、O(n)的排序算法 ###

#### 4.1 桶排序 ####

*  首先得出待排序数列的区间范围，按照范围平均分为若干个有序的桶；
 *  遍历待排序数列，将这些数据分别放到各个桶里面；
 *  单个桶里面的数据可以使用快速排序进行排序；
 *  将所有桶中的数据按照桶的次序合并起来就得到了最终有序的数列；

![img][img 5]

桶排序示意图

桶排序需要借助额外的存储空间“桶”，因此，不是原地排序算法；

桶排序是否稳定取决于单个桶内排序使用的算法，如果使用的快速排序，因为快排本身就不是稳定的，因此桶排序就不是稳定的；

桶排序的空间复杂度为O(n)，因为它需要将全部元素都放到桶中；时间复杂度也是O(n)，这个是由公式推到而来，假设n个元素被平均放到m个桶里面，那么每个桶中的元素个数为k=n/m，每个桶中排序的时间复杂度就是快速排序的时间复杂度，为O(klogk)，因为有m个桶，因此总的时间复杂度就是O(mklogk)，我们把k替换为n/m，那么时间复杂度就可以表示为O(nlog(n/m)，当桶的个数m接近元素个数n时，log(n/m)就是很小的常数可以忽略，因此时间复杂度就接近O(n)；

桶排序对待排序数列的要求比较高，即待排序数列必须是**容易被划分**为m个桶的，并且每个桶中的元素要能**均匀**，否则，有的桶中元素很多，有的很少，那么就会退化为O(nlogn)的时间复杂度；

桶排序比较适用于大数据量的外部排序场景中（非内存排序），比如对10GB的订单数据按照金额进行排序，内存一次性加载不了这么大的数据，可以使用桶排序划分若干个有次序的相同大小的文件，一次只把一个文件中的数据加载到内存进行快速排序；但是订单金额分布不一定是均匀的，有的桶中的数据比较多，会导致该桶文件也无法被一次性加载到内存中进行排序，此时可以对该文件迭代进行桶排序，直至所有桶文件都可以被加载到内存中为止。

#### 4.2 计数排序 ####

计数排序是桶排序的一种特殊情形，当待排序数列的范围区间不是很大的时候，我们为每一个数值划分一个桶，桶之间要有顺序，然后遍历数列，将元素放到它对应的桶中，最后再将桶按照顺序合并起来就得到了有序的数列；每个桶中的元素都是相同的，因此我们省掉了桶内快速排序的时间；

计数排序需要借助额外的存储空间“桶”，因此，不是原地排序算法；

计数排序再将相同的元素放到同一个桶中的时候，可以设置保持它们在原始数列中顺序来保证算法的稳定性；

计数排序的空间复杂度是O(n)，时间复杂度为O(n+k)，k表示数据范围即有多少各个桶，当数据范围不大，可以考虑为常数，那么时间复杂度就是O(n)；

计数排序只能适用在数列范围区间不大的场景中，比如给50万考生的分数进行排名，分数范围k为0~600，数据元素m为50万，k远远小于m，所以适合适用计数排序；计数排序只能给非负整数进行排序，如果待排序数列不是非负整数，需要先想办法把数列转换为非负整数后才能使用计数排序进行排序；

#### 4.3 基数排序 ####

有时候待排序数列的范围区间非常大，分布也不一定是均匀的，且数列本身位数比较多，可以考虑基数排序；基数排序是从最低位开始排序，逐步遍历到最高位，等到最高位完成排序后，整个数列就是有序的。

![在这里插入图片描述][e68b12e78ff441bdb37e63e0572ae3d5.jpeg_pic_center]

有一个要求，对每一位的排序算法一定要使用稳定的排序算法，不然高位的排序会弄乱低位已经排好的顺序，排序算法就不对了。

基数排序在每一位上会使用到线性排序算法，比如计数排序，需要使用额外的存储空间，因此不是原地排序算法；

基数排序每一位的排序算法都是采用的稳定的算法，因此整体上也是稳定的；

基数排序的空间复杂度为O(1)，时间复杂度为O(kn)，当k（元素的位数）不大的时候，并且每一位的排序采用的是线性排序算法（比如计数排序，这就要求每一位上的范围区间不是很大），那时间复杂度就是O(n)；如果每一位排序采用的不是线性排序算法，那么时间复杂度就很难保证是O(n)了。

基数排序的适用场景有给手机号、身份证号、银行卡号排序，这些场景下，数列的范围区间非常大，并且分布不一定均匀，不适合使用桶排序和计数排序，但是却非常适合基数排序。

有的待排序数列不是等长的，比如单词表序列的排序，可以把每一个单词元素通过补0的方式补充到一样长，再通过基数排序进行排序。

#### 4.4 小结 ####

这三种排序算法的时间复杂度是线性的，因此也被成为线性排序算法，虽然它们在时间复杂度上面很占优势，但是对待排序数列的要求比较高，只有待排序数列符合它们各自的特点时，使用它们进行排序才能得到O(n)的效率，因此，实际使用中也不是太多。

### 五、排序算法总结 ###

如下是八种基本排序算法的总结：

![img][img 6]

八大排序算法总结

以上是比较基本的排序算法，还有其它的排序算法会在以后总结。

当你拿到一个数列考虑使用哪一种排序算法的时候：

*  优先考虑是否可以使用线性排序算法；
 *  如果数据不符合线性排序算法的特征，再看下数据量是否比较大，不大的话就选用O(n^2)的算法即可，比较简单；
 *  如果数据量比较大，还是优先考虑使用O(nlogn)的排序算法；
    
    其中因为归并算法空间复杂度较高，因此快速排序会被更多地被考虑使用。
    
    快速排序的缺点在于最坏情况下时间复杂度会到O(n^2)，这个取决于你每次迭代选取基准元素的方式和数列的特点决定的，通常可以对选取基准元素的方式进行优化来尽量避免这个问题。
    
    比如原先是选取第一个或者最后一个元素，可以改进为随机选取或者别的方式，目标是使得基准元素左右两边的数据元素个数都差不多，这样才能维持O(nlogn)的时间复杂度。

[img]: https://img-blog.csdnimg.cn/img_convert/7eec5355c86c25f50e759925d91ff7c0.png
[img 1]: https://img-blog.csdnimg.cn/img_convert/739e3ba771788dc89193624c7a6f5afc.png
[img 2]: https://img-blog.csdnimg.cn/img_convert/fca5f8d303fc51b82338bb6ac5077a46.png
[Link 1]: https://links.jianshu.com/go?to=https%3A%2F%2Fblog.csdn.net%2Fqq_39207948%2Farticle%2Fdetails%2F80006224
[Link 2]: https://links.jianshu.com/go?to=https%3A%2F%2Fwww.sohu.com%2Fa%2F246785807_684445
[img 3]: https://img-blog.csdnimg.cn/img_convert/bb13b7d7e20a339b5e38969e76c519fb.png
[img 4]: https://img-blog.csdnimg.cn/img_convert/0d7fcb92ef80454b76c3e0bfc3ba37c0.png
[img 5]: https://img-blog.csdnimg.cn/img_convert/25eb5ae6a719b2b2ebba1afa67e0501c.png
[e68b12e78ff441bdb37e63e0572ae3d5.jpeg_pic_center]: https://img-blog.csdnimg.cn/e68b12e78ff441bdb37e63e0572ae3d5.jpeg#pic_center
[img 6]: https://img-blog.csdnimg.cn/img_convert/e181925a405f3b2792ead39ef54c3d22.png