万字长文|十大基本排序，一次搞定！

缺乏、安全感 2022-09-10 05:19 129阅读 0赞

✨算法系列文章推荐：

*  [LeetCode通关：听说链表是门槛，这就抬脚跨门而入][LeetCode]
 *  [面试刷算法，这些api不可不知！][api]
 *  [LeetCode通关：数组十七连，真是不简单][LeetCode 1]
 *  [LeetCode通关：连刷三十九道二叉树，刷疯了！][LeetCode 2]

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

大家好，我是老三，一个刷不动算法的程序员。排序算法相关题目尽管在力扣中不是很多，但是面试中动不动要手撕一下。接下来，我们看一下十大基本排序。

# 排序基础 #

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

什么是排序算法的稳定性呢？

当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不惟一\[1\]。

在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的：

若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。

![排序算法的稳定性][e4d3bfa92e9009994c80a8ec6b355129.png]

排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，那么这种排序算法就是不稳定的。

## 排序的分类 ##

按在排序过程中是否涉及数据的内、外存交换来分类，排序大致分为两类：`内部排序`和`外部排序`。

按照是否通过比较来决定元素间的相对次序，排序可以分为`比较类排序`和`非比较类排序`。

![排序分类][ad3824ba497be0308974b737efb66006.png]

# 冒泡排序 #

## 冒泡排序原理 ##

柿子挑软的捏，先从最简单的开始。

冒泡排序有着好听的名字，也有着最好理解的思路。

冒泡排序的基本思想是，从一端到另一端遍历，**两两比较相邻元素的大小**，如果是反序则交换。

动图如下（来源参考\[4\]）：

![冒泡排序][73de29c4107e657f1759e383ae6ef6ff.gif]

## 简单代码实现 ##

先简单实现以下，很简单，两层循环，相邻元素比较：

public void sort(int[] nums) { 
            for (int i = 0; i < nums.length; i++) { 
                for (int j = i + 1; j < nums.length; j++) { 
                    //升序
                    if (nums[i] > nums[j]) { 
                        //交换
                        int temp = nums[i];
                        nums[j] = nums[i];
                        nums[i] = temp;
                    }
                }
            }
        }

## 冒泡排序优化 ##

上面的代码实现还存在一个问题，什么问题呢？

哪怕数组有序，它还是会接着遍历。

所以可以用一个标志位来标志数组是否有序，假如有序，就跳出遍历。

public void sort(int[] nums) { 
            //标志位
            boolean flag = true;
            for (int i = 0; i < nums.length; i++) { 
                for (int j = 0; j < nums.length - i - 1; j++) { 
                    //升序
                    if (nums[j] > nums[j + 1]) { 
                        //交换
                        int temp = nums[j];
                        nums[j] = nums[j + 1];
                        nums[j + 1] = temp;
                    }
                }
                //如果是有序的,结束循环
                if (flag) { 
                    break;
                }
            }
        }

## 冒泡排序性能分析 ##

大小相同的元素没有交换位置，所以冒泡排序是稳定的。

<table> 
 <thead> 
  <tr> 
   <th>算法名称</th> 
   <th>最好时间复杂度</th> 
   <th>最坏时间复杂度</th> 
   <th>平均时间复杂度</th> 
   <th>空间复杂度</th> 
   <th>是否稳定</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>冒泡排序</td> 
   <td>O(n)</td> 
   <td>O(n²)</td> 
   <td>O(n²)</td> 
   <td>O(1)</td> 
   <td>稳定</td> 
  </tr> 
 </tbody> 
</table>

# 选择排序 #

## 选择排序原理 ##

选择排序为什么叫选择排序？原理是怎么样的呢？

它的思路：首先在未排序的序列中找到最小或者最大的元素，放到排序序列的起始位置，然后再从未排序的序列中继继续寻找最小或者最大元素，然后放到已经排序序列的末尾。以此类推，直到所有元素排序完毕。

动图如下(来源参考\[4\])：

![选择排序][7611b704f19e8c05c58482a14b61f0f8.gif]

来看一个例子，用选择排序的方式排序数组`[2,5,4,1,3]`。

*  第一趟，找到数组中最小的元素1，将它和数组的第一个元素交换位置。

![选择排序1][1]

*  第二趟，在未排序的元素中找到最小的元素2，和数组的第二个元素交换位置。

![选择排序2][2]

*  第三趟，在未排序的元素中找到最小的元素3，和数组的第三个元素交换位置。

![选择排序-3][-3]

*  第四趟，在未排序的元素中找到最小的元素4，和数组的第四个元素交换位置。

![选择排序4][4]

那么到这，我们的数组就是有序的了。

![选择排序5][5]

## 选择排序代码实现 ##

选择排序的思路很简单，实现起来也不难。

public void sort(int[] nums) { 
            int min = 0;
            for (int i = 0; i < nums.length - 1; i++) { 
                for (int j = i + 1; j < nums.length; j++) { 
                    //寻找最小的数
                    if (nums[j] < nums[min]) { 
                        min = j;
                    }
                }
                //交换
                int temp = nums[i];
                nums[i] = nums[min];
                nums[min] = temp;
            }
        }

## 选择排序性能分析 ##

选择排序稳定吗？

答案是不稳定的，因为在未排序序列中找到最小值之后，和排序序列的末尾元素交换。

<table> 
 <thead> 
  <tr> 
   <th>算法名称</th> 
   <th>最好时间复杂度</th> 
   <th>最坏时间复杂度</th> 
   <th>平均时间复杂度</th> 
   <th>空间复杂度</th> 
   <th>是否稳定</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>选择排序</td> 
   <td>O(n²)</td> 
   <td>O(n²)</td> 
   <td>O(n²)</td> 
   <td>O(1)</td> 
   <td>不稳定</td> 
  </tr> 
 </tbody> 
</table>

# 插入排序 #

## 插入排序原理 ##

关于插入排序，有一个非常形象的比喻。斗地主——摸到的牌都是乱的，我们会把摸到的牌插到合适的位置。

它的思路：将一个元素插入到已经排好序的有序序列中，从而得到一个新的有序序列。

动图如下(来源参考3)：

![插入排序][40d1e27e8046767ce41a6283da721f69.gif]

还是以数组`[2,5,4,1,3]`为例：

*  第一趟：从未排序的序列将元素5插入到已排序的序列的合适位置

![插入排序1][1 1]

*  第二趟：接着从未排序的序列中，将元素4插入到已经排序的序列的合适位置，需要遍历有序序列，找到合适的位置

![插入排序2][2 1]

*  第三趟：继续，把1插入到合适的位置

![插入排序4][4 1]

*  第五趟：继续，把3插入到合适的位置

![插入排序5][5 1]

OK，排序结束。

## 插入排序代码实现 ##

找到插入元素的位置，移动其它元素。

public void sort(int[] nums) { 
            //无序序列从1开始
            for (int i = 1; i < nums.length; i++) { 
                //需要插入有序序列的元素
                int value = nums[i];
                int j = 0;
                for (j = i - 1; j >= 0; j--) { 
                    //移动数据
                    if (nums[j] > value) { 
                        nums[j + 1] = nums[j];
                    } else { 
                        break;
                    }
                }
                //插入元素
                nums[j + 1] = value;
            }
        }

## 插入排序性能分析 ##

插入排序智慧移动比插入元素大的元素，所以相同元素相对位置不变，是稳定的。

从代码里我们可以看出，如果找到了合适的位置，就不会再进行比较了，所以最好情况时间复杂度是O(n)。

<table> 
 <thead> 
  <tr> 
   <th>算法名称</th> 
   <th>最好时间复杂度</th> 
   <th>最坏时间复杂度</th> 
   <th>平均时间复杂度</th> 
   <th>空间复杂度</th> 
   <th>是否稳定</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>插入排序</td> 
   <td>O(n)</td> 
   <td>O(n²)</td> 
   <td>O(n²)</td> 
   <td>O(1)</td> 
   <td>稳定</td> 
  </tr> 
 </tbody> 
</table>

# 希尔排序 #

## 希尔排序原理 ##

希尔排序，名字来自它的发明者Shell。它是直接插入排序的改进版。

希尔排序的思路是：把整个待排序的记录序列分割成若干个子序列，分别进行插入排序。

我们知道直接插入排序在面对大量无序数据的时候不太理想，希尔排序就是通过跳跃性地移动，来达到数组元素地基本有序，再接着用直接插入排序。

希尔排序动图（动图来源参考\[1\]）：

![希尔排序][bed369279a0d2a499aa99655d5a9f740.gif]

还是以数组`[2,5,6,1,7，9，3，8，4]`为例，我们来看一下希尔排序的过程：

*  数组元素个数为9，取7/2=4为下标差值，将下标差值为4的元素分为一组

![希尔排序-1][-1]

*  组内进行插入排序，构成有序序列

![希尔排序-2][-2]

*  再取4/2=2为 下标差值，将下标差值为2的元素分为一组

![希尔排序3][3]

*  组内插入排序，构成有序序列

![希尔排序4][4 2]

*  下标差值=2/2=1，将剩余的元素插入排序

![希尔排序5][5 2]

## 希尔排序代码实现 ##

可以看看前面的插入排序，希尔排序

只是一个有步长的直接插入排序。

public void sort(int[] nums){ 
            //下标差
            int step=nums.length;
            while (step>0){ 
                //这个是可选的，也可以是3
                step=step/2;
                //分组进行插入排序
                for (int i=0;i<step;i++){ 
                    //分组内的元素，从第二个开始
                    for (int j=i+step;j<nums.length;j+=step){ 
                        //要插入的元素
                        int value=nums[j];
                        int k;
                        for (k=j-step;k>=0;k-=step){ 
                          if (nums[k]>value){ 
                              //移动组内元素
                              nums[k+step]=nums[k];
                          }else { 
                              break;
                          }
                        }
                        //插入元素
                        nums[k+step]=value;
                    }
                }
            }
        }

## 希尔排序性能分析 ##

*  稳定度分析

希尔排序是直接插入排序的变形，但是和直接插入排序不同，它进行了分组，所以不同组的相同元素的相对位置可能会发生改变，所以它是不稳定的。

*  时间复杂度分析

希尔排序的时间复杂度跟增量序列的选择有关，范围为 O(n^(1.3-2)) 在此之前的排序算法时间复杂度基本都是 O(n²)，希尔排序是突破这个时间复杂度的第一批算法之一。

<table> 
 <thead> 
  <tr> 
   <th>算法名称</th> 
   <th>时间复杂度</th> 
   <th>空间复杂度</th> 
   <th>是否稳定</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>希尔排序</td> 
   <td>O(n^(1.3-2))</td> 
   <td>O(1)</td> 
   <td>不稳定</td> 
  </tr> 
 </tbody> 
</table>

# 归并排序 #

## 归并排序原理 ##

归并排序是建立在归并操作上的一种有效的排序算法，归并，就是合并的意思，在数据结构上的定义就是把`把若干个有序序列合并成一个新的有序序列`。

归并排序是分治法的典型应用，分治什么意思呢？就是把一个大的问题分解成若干个小的问题来解决。

归并排序的步骤，是把一个数组切分成两个，接着递归，一直到单个元素，然后再合并，单个元素合并成小数组，小数组合并成大数组。

动图如下（来源参考\[4\]）：

![归并排序][a75e11008415aa2b21dcaa3c5fe0b9eb.gif]

我们以数组`[2,5,6,1,7,3,8,4]` 为例，来看一下归并排序的过程：

![归并排序][b30f894733f9916c3ba0dcadbe5bdbcd.png]

拆分就不用多讲了，我们看看怎么`合并`。

## 归并排序代码实现 ##

这里使用递归来实现归并排序：

*  递归终止条件

递归起始位置小于终止位置

*  递归返回结果

直接对传入的数组序列进行排序，所以无返回值

*  递归逻辑

将当前数组分成两组，分别分解两组，最后归并

代码如下：

public class MergeSort { 
    
        public void sortArray(int[] nums) { 
            sort(nums, 0, nums.length - 1);
        }
    
        /** * 归并排序 * * @param nums * @param left * @param right */
        public void sort(int[] nums, int left, int right) { 
            //递归结束条件
            if (left >= right) { 
                return;
            }
            int mid = left + (right - left) / 2;
            //递归当前序列左半部分
            sort(nums, left, mid);
            //递归当前序列右半部分
            sort(nums, mid + 1, right);
            //归并结果
            merge(nums, left, mid, right);
        }
    
        /** * 归并 * * @param arr * @param left * @param mid * @param right */
        public void merge(int[] arr, int left, int mid, int right) { 
            int[] tempArr = new int[right - left + 1];
            //左边首位下标和右边首位下标
            int l = left, r = mid + 1;
            int index = 0;
            //把较小的数先移到新数组中
            while (l <= mid && r <= right) { 
                if (arr[l] <= arr[r]) { 
                    tempArr[index++] = arr[l++];
                } else { 
                    tempArr[index++] = arr[r++];
                }
            }
            //把左边数组剩余的数移入数组
            while (l <= mid) { 
                tempArr[index++] = arr[l++];
            }
            //把右边剩余的数移入数组
            while (r <= right) { 
                tempArr[index++] = arr[r++];
            }
            //将新数组的值赋给原数组
            for (int i = 0; i < tempArr.length; i++) { 
                arr[i+left] = tempArr[i];
            }
        }
    }

## 归并排序性能分析 ##

*  时间复杂度

一趟归并，我们需要把遍历待排序序列遍历一遍，时间复杂度O(n)。

而归并排序的过程，需要把数组不断二分，这个时间复杂度是O(logn)。

所以归并排序的时间复杂度是O(nlogn)。

*  空间复杂度

使用了一个临时数组来存储合并的元素，空间复杂度O(n)。

*  稳定性

归并排序是一种稳定的排序方法。

<table> 
 <thead> 
  <tr> 
   <th>算法名称</th> 
   <th>最好时间复杂度</th> 
   <th>最坏时间复杂度</th> 
   <th>平均时间复杂度</th> 
   <th>空间复杂度</th> 
   <th>是否稳定</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>归并排序</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>O(n)</td> 
   <td>稳定</td> 
  </tr> 
 </tbody> 
</table>

# 快速排序 #

## 快速排序原理 ##

快速排序是面试最高频的排序算法。

快速排序和上面的归并排序一样，都是基于分治思想的，大概过程：

*  选出一个基准数，基准值一般取序列最左边的元素
 *  重新排序序列，比基准值小的放在基准值左边，比基准值大的放在基准值右边，这就是所谓的分区

快速排序动图如下：

![快速排序动图][ae1da741242424194631c2d432b1b09e.gif]

我们来看一个完整的快速排序图示：

![快速排序][965bad5382b4eac08d6b734e5a00f343.png]

## 快速排序代码实现 ##

### 单边扫描快速排序 ###

选择一个数作为基准数pivot，同时设定一个标记 mark 代表左边序列最右侧的下标位置，接下来遍历数组，如果元素大于基准值，无操作，继续遍历，如果元素小于基准值，则把 mark + 1 ，再将 mark 所在位置的元素和遍历到的元素交换位置，mark 这个位置存储的是比基准值小的数据，当遍历结束后，将基准值与 mark 所在元素交换位置。

public class QuickSort0 { 
    
        public void sort(int[] nums) { 
            quickSort(nums, 0, nums.length - 1);
        }
    
        public void quickSort(int[] nums, int left, int right) { 
            //结束条件
            if (left >= right) { 
                return;
            }
            //分区
            int partitonIndex = partion(nums, left, right);
            //递归左分区
            quickSort(nums, left, partitonIndex - 1);
            //递归右分区
            quickSort(nums, partitonIndex + 1, right);
        }
    
        //分区
        public int partion(int[] nums, int left, int right) { 
            //基准值
            int pivot = nums[left];
            //mark标记初始下标
            int mark = left;
            for (int i = left + 1; i <= right; i++) { 
                if (nums[i] < pivot) { 
                    //小于基准值，则mark+1，并交换位置
                    mark++;
                    int temp = nums[mark];
                    nums[mark] = nums[i];
                    nums[i] = temp;
                }
            }
            //基准值与mark对应元素调换位置
            nums[left] = nums[mark];
            nums[mark] = pivot;
            return mark;
        }
    }

### 双边扫描快速排序 ###

还有另外一种双边扫描的做法。

选择一个数作为基准值，然后从数组左右两边进行扫描，先从左往右找到一个大于基准值的元素，将它填入到right指针位置，然后转到从右往左扫描，找到一个小于基准值的元素，将他填入到left指针位置。

public class QuickSort1 { 
    
        public int[] sort(int[] nums) { 
    
            quickSort(nums, 0, nums.length - 1);
            return nums;
    
        }
    
        public void quickSort(int[] nums, int low, int high) { 
    
            if (low < high) { 
                int index = partition(nums, low, high);
                quickSort(nums, low, index - 1);
                quickSort(nums, index + 1, high);
            }
    
        }
    
        public int partition(int[] nums, int left, int right) { 
            //基准值
            int pivot = nums[left];
            while (left < right) { 
                //从右往左扫描
                while (left < right && nums[right] >= pivot) { 
                    right--;
                }
                //找到第一个比pivot小的元素
                if (left < right) nums[left] = nums[right];
                //从左往右扫描
                while (left < right && nums[left] <= pivot) { 
                    left++;
                }
                //找到第一个比pivot大的元素
                if (left < right) nums[right] = nums[left];
            }
            //基准数放到合适的位置
            nums[left] = pivot;
            return left;
        }
    }

## 快速排序性能分析 ##

*  时间复杂度

快速排序的时间复杂度和归并排序一样，都是O(nlogn)，但是这是最优的情况，也就是每次都能把数组切分到两个差不多大小的子数组。

如果出现极端情况，例如一个有序的序列\[5,4,3,2,1\] ，选基准值为5，那么需要切分n-1次才能完成整个快速排序的过程，这种情况时间复杂度就退化到了O(n²)。

*  空间复杂度

快速排序是一种原地排序的算法，空间复杂度是O(1)。

*  稳定性

快排的比较和交换是跳跃进行的，所以快排是一种不稳定的排序算法。

<table> 
 <thead> 
  <tr> 
   <th>算法名称</th> 
   <th>最好时间复杂度</th> 
   <th>最坏时间复杂度</th> 
   <th>平均时间复杂度</th> 
   <th>空间复杂度</th> 
   <th>是否稳定</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>快速排序</td> 
   <td>O(nlogn)</td> 
   <td>O(n²)</td> 
   <td>O(nlogn)</td> 
   <td>O(1)</td> 
   <td>不稳定</td> 
  </tr> 
 </tbody> 
</table>

# 堆排序 #

## 堆排序原理 ##

还记得我们前面的简单选择排序吗？堆排序是简单选择排序的一种升级版。

在学习堆排序之前，什么是堆呢？

完全二叉树是堆的一个比较经典的堆实现。

我们先来了解一下什么是完全二叉树。

简答说，如果节点不满，那它不满的部分只能在最后一层的右侧。

我们来看几个示例。

![完全二叉树和非完全二叉树][84000000e06ccddd3d264a132484cad8.png]

相信看了这几个示例，就清楚什么是`完全二叉树`，什么是`非完全二叉树`。

那`堆`又是什么呢？

*  必须是完全二叉树
 *  任一节点的值必须是其子树的最大值或最小值

>  *  最大值时，称为“最大堆”，也称大顶堆；
>  *  最小值时，称为“最小堆”，也称小顶堆。

![大、小顶堆][484e2fdc75a2cbf94d626f65bfc14fe7.png]

因为堆是完全二叉树，所以堆可以用数组存储。

按层来将元素存储到数组对应位置，从下标1开始存储，可以省略一些计算。

![大顶堆存储][5db6f456065aa27cafd48cf3cfb5bb56.png]

好了，我们现在对堆已经有一些了解了，我们来看一下堆排序是什么样的呢？\[2\]

*  建立一个大顶堆
 *  将堆顶元素（最大值）插入数组末尾
 *  让新的最大元素上浮到堆顶
 *  重复过程，直到排序完成

动图如下（来源参考\[1\]）：

![堆排序动图（来自参考\[1\]）][1 2]

关于建堆，有两种方式，一种是上浮，一种是下沉。

上浮是什么呢？就是把子节点一层层上浮到合适的位置。

下沉是什么呢？就是把堆顶元素一层层下沉到合适的位置。

上面的动图，使用的就是下沉的方式。

## 堆排序代码实现 ##

public class HeapSort { 
    
        public void sort(int[] nums) { 
            int len = nums.length;
            //建堆
            buildHeap(nums, len);
            for (int i = len - 1; i > 0; i--) { 
                //将堆顶元素和堆末元素调换
                swap(nums, 0, i);
                //数组计数长度减1，隐藏堆尾元素
                len--;
                //将堆顶元素下沉，使最大的元素浮到堆顶来
                sink(nums, 0, len);
            }
        }
    
        /** * 建堆 * * @param nums * @param len */
        public void buildHeap(int[] nums, int len) { 
            for (int i = len / 2; i >= 1; i--) { 
                //下沉
                sink(nums, i, len);
            }
        }
    
        /** * 下沉操作 * * @param nums * @param index * @param end */
        public void sink(int[] nums, int index, int end) { 
            //左子节点下标
            int leftChild = 2 * index + 1;
            //右子节点下标
            int rightChild = 2 * index + 2;
            //要调整的节点下标
            int current = index;
            //下沉左子树
            if (leftChild < end && nums[leftChild] > nums[current]) { 
                current = leftChild;
            }
            //下沉右子树
            if (rightChild < end && nums[rightChild] > nums[current]) { 
                current = rightChild;
            }
            //如果下标不相等，证明调换过了
            if (current!=index){ 
                //交换值
                swap(nums,index,current);
                //继续下沉
                sink(nums,current,end);
            }
        }
    
        public void swap(int[] nums, int i, int j) { 
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }

## 堆排序性能分析 ##

*  时间复杂度

堆排的时间复杂度和快排的时间复杂度一样，都是O(nlogn)。

*  空间复杂度

堆排没有引入新的空间，原地排序，空间复杂度O(1)。

*  稳定性

堆顶的元素不断下沉，交换，会改变相同元素的相对位置，所以堆排是不稳定的。

<table> 
 <thead> 
  <tr> 
   <th>算法名称</th> 
   <th>时间复杂度</th> 
   <th>空间复杂度</th> 
   <th>是否稳定</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>堆排序</td> 
   <td>O(nlogn)</td> 
   <td>O(1)</td> 
   <td>不稳定</td> 
  </tr> 
 </tbody> 
</table>

# 计数排序 #

文章开始我们说了，排序分为比较类和非比较类，计数排序是一种非比较类的排序方法。

计数排序是一种线性时间复杂度的排序，利用空间来换时间，我们来看看计数排序是怎么实现的吧。

## 计数排序原理 ##

计数排序的大致过程\[4\]：

*  找出待排序的数组中最大和最小的元素
 *  统计数组中每个值为i的元素出现的次数，存入数组arr的第i项；
 *  对所有的计数累加（从arr中的第一个元素开始，每一项和前一项相加）；
 *  反向填充目标数组：将每个元素i放在新数组的第arr(i)项，每放一个元素就将arr(i)减去1。

我们看一下动图演示（来自参考\[4\]）：

![计数排序动图，来自参考\[4\]][4 3]

我们拿一个数组来看一下完整过程：`[6,8,5,1,2,2,3]`

*  首先，找到数组中最大的数，也就是8，创建一个最大下标为8的空数组arr

![计数排序-1][-1 1]

*  遍历数据，将数据的出现次数填入arr对应的下标位置中

![计数排序-2][-2 1]

*  然后输出数组元素的下标值，元素的值是几，就输出几次

![计数排序-3][-3 1]

## 计数排序代码实现 ##

public class CountSort { 
    
        public void sort(int[] nums) { 
            //查找最大值
            int max = findMax(nums);
            //创建统计次数新数组
            int[] countNums = new int[max + 1];
            //将nums元素出现次数存入对应下标
            for (int i = 0; i < nums.length; i++) { 
                int num = nums[i];
                countNums[num]++;
                nums[i] = 0;
            }
            //排序
            int index = 0;
            for (int i = 0; i < countNums.length; i++) { 
                while (countNums[i] > 0) { 
                    nums[index++] = i;
                    countNums[i]--;
                }
            }
        }
    
        public int findMax(int[] nums) { 
            int max = nums[0];
            for (int i = 0; i < nums.length; i++) { 
                if (nums[i] > max) { 
                    max = nums[i];
                }
            }
            return max;
        }
    }

OK，乍一看没啥问题，但是仔细想想，其实还是有些毛病的，毛病在哪呢？

*  如果我们要排序的元素有0怎么办呢？例如`[0,0,5,2,1,3,4]` ，arr初始都为0，怎么排呢？
    
    这个很难解决，有一种办法，就是计数的时候原数组先加10，\[-1,0,2\]，排序写回去的时候再减，但是如果刚好碰到有-10这个元素就凉凉。
 *  如果元素的范围很大呢？例如`[9992,9998,9993,9999]`，那我们申请一个10000个元素的数组吗？
    
    这个可以用偏移量解决，找到最大和最小的元素，计算偏移量，例如`[9992,9998,9993,9999]`，偏移量=9999-9992=7，我们只需要建立一个容量为8的数组就可以了。

解决第二个问题的版本如下：

public class CountSort1 { 
    
        public void sort(int[] nums) { 
            //查找最大值
            int max = findMax(nums);
            //寻找最小值
            int min = findMin(nums);
            //偏移量
            int gap = max - min;
            //创建统计次数新数组
            int[] countNums = new int[gap + 1];
            //将nums元素出现次数存入对应下标
            for (int i = 0; i < nums.length; i++) { 
                int num = nums[i];
                countNums[num - min]++;
                nums[i] = 0;
            }
            //排序
            int index = 0;
            for (int i = 0; i < countNums.length; i++) { 
                while (countNums[i] > 0) { 
                    nums[index++] = min + i;
                    countNums[i]--;
                }
            }
        }
    
        public int findMax(int[] nums) { 
            int max = nums[0];
            for (int i = 0; i < nums.length; i++) { 
                if (nums[i] > max) { 
                    max = nums[i];
                }
            }
            return max;
        }
    
        public int findMin(int[] nums) { 
            int min = nums[0];
            for (int i = 0; i < nums.length; i++) { 
                if (nums[i] < min) { 
                    min = nums[i];
                }
            }
            return min;
        }
    }

## 计数排序性能分析 ##

*  时间复杂度

我们整体运算次数是n+n+n+k=3n+k，所以使劲复杂度是O(n+k)。

*  空间复杂度

引入了辅助数组，空间复杂度O(n)。

*  稳定性

我们的实现实际上是不稳定的，但是计数排序是有稳定的实现的，可以查看参考\[1\]。

同时我们通过实现也发现，计数排序实际上不适合有负数的，元素偏移值过大的数组。

# 桶排序 #

桶数组可以看做计数排序的升级版，它把元素分到若干个`桶`中，每个桶中的元素再单独排序。

## 桶排序原理 ##

桶排序大概的过程：

*  设置一个定量的数组当作空桶；
 *  遍历输入数据，并且把元素一个一个放到对应的桶里去；
 *  对每个不是空的桶进行排序；
 *  从不是空的桶里把排好序的数据拼接起来。

桶排序动图如下（动图来源参考\[1\]）：

![桶排序动图（来源参考\[1\]）][1 3]

我们上面说了，计数排序不适合偏移量过大的数组，我们拿一个偏移量非常大的数组`[2066,566,166，66,1066，2566，1566]`为例，来看看桶排序的过程。

*  创建6个桶，分别存储0-500,500-1000,1000-1500,1500-2000,2000-2500,2500-3000的元素

![桶排序-1][-1 2]

*  遍历数组，将元素分别分配到对应的桶中

![桶排序-2][-2 2]

*  桶中元素排序，这里我们明显只用排序第一个桶

![桶排序-3][-3 2]

*  将桶中的元素依次取出，取出的元素就是有序的了

![桶排序-4][-4]

## 桶排序代码实现 ##

桶排序的实现我们要考虑几个问题：

*  桶该如何表示？
 *  桶的数量怎么确定？
 *  桶内排序用什么方法？

我们来看一下代码：

public class BucketSort { 
    
        public void sort(int[] nums) { 
            int len = nums.length;
            int max = nums[0];
            int min = nums[0];
            //获取最大值和最小值
            for (int i = 1; i < len; i++) { 
                if (nums[i] > max) { 
                    max = nums[i];
                }
                if (nums[i] < min) { 
                    min = nums[i];
                }
            }
            //计算步长
            int gap = max - min;
            //使用列表作为桶
            List<List<Integer>> buckets = new ArrayList<>();
            //初始化桶
            for (int i = 0; i < gap; i++) { 
                buckets.add(new ArrayList<>());
            }
            //确定桶的存储区间
            int section = gap / len - 1;
            //数组入桶
            for (int i = 0; i < len; i++) { 
                //判断元素应该入哪个桶
                int index = nums[i] / section - 1;
                if (index < 0) { 
                    index = 0;
                }
                //对应的桶添加元素
                buckets.get(index).add(nums[i]);
            }
            //对桶内的元素排序
            for (int i = 0; i < buckets.size(); i++) { 
                //这个底层调用的是 Arrays.sort
                // 这个api不同情况下可能使用三种排序：插入排序，快速排序，归并排序，具体看参考[5]
                Collections.sort(buckets.get(i));
            }
            //将桶内的元素写入原数组
            int index = 0;
            for (List<Integer> bucket : buckets) { 
                for (Integer num : bucket) { 
                    nums[index] = num;
                    index++;
                }
            }
        }
        
    }

## 桶排序性能分析 ##

*  时间复杂度

桶排序最好的情况，就是元素均匀分配到了每个桶，时间复杂度O(n)，最坏情况，是所有元素都分配到一个桶中，时间复杂度是O(n²)。平均的时间复杂度和技术排序一样，都是O(n+k)。

*  空间复杂度

桶排序，需要存储n个额外的桶，桶中又要存储k个元素，所以空间复杂度是O(n+k)。

*  稳定性

稳定性得看桶中排序用的什么排序算法，桶中用的稳定排序算法，那么就是稳定的。用的不稳定的排序算法，那么就是不稳定的。

# 基数排序 #

## 基数排序原理 ##

基数排序是一种非比较型的排序方法。

它的基本原理是将元素按照位数切割成不同的数字，然后按照每个位数进行比较。

大概过程：

*  取得数组中的最大数，并取得位数；
 *  arr为原始数组，从最低位开始取每个位组成radix数组
 *  对radix进行计数排序（利用计数排序适用于小范围数的特点）

动图图示如下（来源参考\[1\]）：

![基数排序-来源参考\[1\]][-_1]

基数排序可以说是桶排序的一个进化，我们以`[ 892， 846， 821， 199， 810，700 ]`来看一下基数排序的过程：

*  创建十个桶用来存储元素

![桶排序-1][-1 3]

*  根据个位数，将元素分别分配到不同的桶中

![基数排序-2][-2 3]

*  然后将桶中的元素依次取出

![基数排序-3][-3 3]

*  接下来排十位数，根据十位数分配桶，再依次取出

![基数排序-3][-3 4]

*  接下来百位数

![基数排序-4][-4 1]

## 基数排序代码实现 ##

public class RadixSort { 
    
        public void sort(int[] nums) { 
            int len = nums.length;
            //最大值
            int max = nums[0];
            for (int i = 0; i < len; i++) { 
                if (nums[i] > max) { 
                    max = nums[i];
                }
            }
            //当前排序位置
            int location = 1;
            //用列表实现桶
            List<List<Integer>> buckets = new ArrayList<>();
            //初始化size为10的一个桶
            for (int i = 0; i < 10; i++) { 
                buckets.add(new ArrayList<>());
            }
            while (true) { 
                //元素最高位数
                int d = (int) Math.pow(10, (location - 1));
                //判断是否排完
                if (max < d) { 
                    break;
                }
                //数据入桶
                for (int i = 0; i < len; i++) { 
                    //计算余数 放入相应的桶
                    int number = ((nums[i] / d) % 10);
                    buckets.get(number).add(nums[i]);
                }
                //写回数组
                int nn = 0;
                for (int i = 0; i < 10; i++) { 
                    int size = buckets.get(i).size();
                    for (int ii = 0; ii < size; ii++) { 
                        nums[nn++] = buckets.get(i).get(ii);
                    }
                    buckets.get(i).clear();
                }
                location++;
            }
        }
    }

## 基数排序性能分析 ##

*  时间复杂度

时间复杂度O(n+k)，其中n数组元素个数，k为数组元素最高位数。

*  空间复杂度

和桶排序一样，因为引入了桶的存储空间，所以空间复杂度O(n+k)。

*  稳定性

因为基数排序过程，每次都是将当前位数是哪个相同数值的元素统一分配到桶中，并不交换位置，所以基数排序是稳定的。

# 总结 #

这篇文章，我们学习了十大基本排序，来简单总结一下。

首先最简单的`冒泡排序`：两层循环，相邻交换；

`选择排序`：未排序和排序两分，从未排序序列中寻找最小的元素，放在排序序列末尾；

`插入排序`：斗地主摸牌思维，把一个元素插入到有序序列合适位置；

`希尔排序`：插入排序plus，先把序列分割，再分别插入排序；

`归并排序`：分治思想第一弹，先将序列切分，再在合并过程排序；

`快速排序`：分治思想第二弹，基准数分区原序列，小的放左边，大的放右边；

`堆排序`：选择排序plus，建立大顶堆，堆顶元素（最大值）插入序列末尾，再让新的元素上浮。

`计数排序`：空间换时间第一弹，利用新数组，统计对应元素出现次数，输出新数组下标，原数组完成排序；

`桶排序`：空间换时间第二弹，将原数组的元素分到若干个桶，每个桶单独排序，再把桶里元素拼起来；

`基数排序`：空间换时间第三弹，桶排序plus，根据数位，把元素分桶，然后按每个位数比较。

十大基本排序性能汇总：

<table> 
 <thead> 
  <tr> 
   <th>排序方法</th> 
   <th>时间复杂度（平均）</th> 
   <th>时间复杂度（最坏）</th> 
   <th>时间复杂度（最好）</th> 
   <th>空间复杂度</th> 
   <th>稳定性</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>冒泡排序</td> 
   <td>O(n²)</td> 
   <td>O(n²)</td> 
   <td>O(n)</td> 
   <td>O(1)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>选择排序</td> 
   <td>O(n²)</td> 
   <td>O(n²)</td> 
   <td>O(n²)</td> 
   <td>O(1)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>插入排序</td> 
   <td>O(n²)</td> 
   <td>O(n²)</td> 
   <td>O(n)</td> 
   <td>O(1)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>希尔排序</td> 
   <td>O(n^(1.3-2))</td> 
   <td>O(n²)</td> 
   <td>O(n)</td> 
   <td>O(1)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>归并排序</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>O(n)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>快速排序</td> 
   <td>O(nlogn)</td> 
   <td>O(n²)</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>堆排序</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>O(1)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>计数排序</td> 
   <td>O(n+k)</td> 
   <td>O(n+k)</td> 
   <td>O(n+k)</td> 
   <td>O(n)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>桶排序</td> 
   <td>O(n+k)</td> 
   <td>O(n²)</td> 
   <td>O(n)</td> 
   <td>O(n+k)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>基数排序</td> 
   <td>O(n*k)</td> 
   <td>O(n*k)</td> 
   <td>O(n*k)</td> 
   <td>O(n+k)</td> 
   <td>稳定</td> 
  </tr> 
 </tbody> 
</table>

> 简单的事情重复做，重复的事情认真做，认真的事情有创造性地去做。
> 
> 我是三分恶，一个能文能武的全栈开发。
> 
> `点赞`、`关注` 不迷路，咱们下期见！

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

**参考：**

\[1\].[这或许是东半球分析十大排序算法最好的一篇文章][Link 1]

\[2\]. https://github.com/chefyuan/algorithm-base

\[2\].《数据结构与算法分析》

\[3\]. [面试高频：Java常用的八大排序算法一网打尽！][Java]

\[4\]. [十大经典排序算法（动图演示）][Link 2]

\[5\]. [剖析JDK8中Arrays.sort底层原理及其排序算法的选择][JDK8_Arrays.sort]

[LeetCode]: https://fighter3.blog.csdn.net/article/details/119095000
[api]: https://fighter3.blog.csdn.net/article/details/118772581
[LeetCode 1]: https://fighter3.blog.csdn.net/article/details/119493527
[LeetCode 2]: https://fighter3.blog.csdn.net/article/details/120075736
[e4d3bfa92e9009994c80a8ec6b355129.png]: /images/20220829/12857ba7ead0422c98e0263c730e0177.png
[ad3824ba497be0308974b737efb66006.png]: /images/20220829/2af621713cb94798bd2d49b8875f3af4.png
[73de29c4107e657f1759e383ae6ef6ff.gif]: /images/20220829/17857824ed784ba69653a99716ea8a94.png
[7611b704f19e8c05c58482a14b61f0f8.gif]: /images/20220829/e1a9107fbe694af98b22523b52767c30.png
[1]: /images/20220829/15b6525a882c43869c3b5d1bbfd6c26f.png
[2]: /images/20220829/f6154b466f964fe4841d53a05cd2cd4e.png
[-3]: /images/20220829/7e17d473d7984614a2b7e483867a892e.png
[4]: /images/20220829/5292b2a685c249999b66952aa89f43da.png
[5]: /images/20220829/9ce454cbdef442379114dc897229dea0.png
[40d1e27e8046767ce41a6283da721f69.gif]: /images/20220829/78f52d3e79f7485b8eb0a4176d480463.png
[1 1]: /images/20220829/fec9266fc3f346a8a2fa3bbcc7d80d28.png
[2 1]: /images/20220829/4568042aecf34f2586b115304eea9a42.png
[4 1]: /images/20220829/f53171856b554c57bb83327a07a40b79.png
[5 1]: /images/20220829/86f9c5a0d825439dbd1a7e0ba40c8bcd.png
[bed369279a0d2a499aa99655d5a9f740.gif]: /images/20220829/2668f1d78b54487193d82eae781c110f.png
[-1]: /images/20220829/91658d9f59794b0ca58289ca16ff6425.png
[-2]: /images/20220829/df0f5c26d454415ab10919f381018259.png
[3]: /images/20220829/6f32d5a32c05415d967be0cff6728f31.png
[4 2]: /images/20220829/95089f9736c143509c0c1774f9d92bc1.png
[5 2]: /images/20220829/bb25cbd8604d4207bc5261e1e405bfbc.png
[a75e11008415aa2b21dcaa3c5fe0b9eb.gif]: /images/20220829/19d284efa08d40c1a87db1446f3b4021.png
[b30f894733f9916c3ba0dcadbe5bdbcd.png]: /images/20220829/bdf0ba0eb4d34863a810881df9258058.png
[ae1da741242424194631c2d432b1b09e.gif]: /images/20220829/3011ac63014c4f648d57854bb52af6fc.png
[965bad5382b4eac08d6b734e5a00f343.png]: /images/20220829/9cf26d65fa5a4f8f881cd91aa9874cda.png
[84000000e06ccddd3d264a132484cad8.png]: /images/20220829/c6ecb4665c134a979cc3832a9af96389.png
[484e2fdc75a2cbf94d626f65bfc14fe7.png]: /images/20220829/a55858c1f6ac4ae9b56508eb53085961.png
[5db6f456065aa27cafd48cf3cfb5bb56.png]: /images/20220829/7cfb0bfaedf346cca64de946a2570911.png
[1 2]: /images/20220829/336123e7719b48fa904bda142839b7bd.png
[4 3]: /images/20220829/d41d247e98ab4ab29f00fcd598a02218.png
[-1 1]: /images/20220829/cfce649459ce43aab4aeac6e6f3d010d.png
[-2 1]: /images/20220829/a96ecfea7f6a42689e5330b25c458e41.png
[-3 1]: /images/20220829/6bbe8ad08a5a4d70a83111004a91b6dc.png
[1 3]: /images/20220829/e0e398bb9ad7471e99256112c57555b9.png
[-1 2]: /images/20220829/539a5d0ecd4f4f32abcbca7957118826.png
[-2 2]: /images/20220829/4c34ea3cc8be4780a181e7fba8685374.png
[-3 2]: /images/20220829/3d781e9a962c4f6899e14f48da5bd22e.png
[-4]: /images/20220829/a341453d2bf34a528c121c3a661635d2.png
[-_1]: /images/20220829/af815a60eb99461db8f6332e4841d4e8.png
[-1 3]: /images/20220829/6557e8fd6e804f408c0232ea5237ca3a.png
[-2 3]: /images/20220829/adc7291bad9642f4aba43bad501714d5.png
[-3 3]: /images/20220829/3f257dd1d7444ce3829997b7063c1aaf.png
[-3 4]: /images/20220829/640e9ff5db8e4fe6aa744247d88ba033.png
[-4 1]: /images/20220829/fda323a16ae2412e95a9e26273b33528.png
[Link 1]: https://www.cxyxiaowu.com/725.html
[Java]: https://www.cxyxiaowu.com/17631.html
[Link 2]: https://www.cnblogs.com/onepixel/p/7674659.html
[JDK8_Arrays.sort]: https://www.jianshu.com/p/d7ba7d919b80