一.算法分类 分类：
非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 O(nlogn)，因此成为非线性时间比较类程序。
线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。
复杂度：
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
稳定性：
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面
不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面
排序方式：
内排序：所有排序操作都在内存中完成。
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行。
1.排序算法类型
2.排序算法时间复杂度
排序方法
时间复杂度(平均)
时间复杂度(最坏)
时间复杂度(最好)
空间复杂度
稳定性
冒泡排序
O(n2 )
O(n2 )
O(n)
O(1)
稳定
快速排序
O(nlogn)
O(n2 )
O(nlogn)
O(nlogn)
不稳定
简单插入排序
O(n2 )
O(n2 )
O(n)
O(1)
稳定
希尔排序
O(n1.3 )
O(n2 )
O(n)
O(1)
不稳定
简单选择排序
O(n2 )
O(n2 )
O(n2 )
O(1)
不稳定
堆排序
O(nlogn)
O(nlogn)
O(nlogn)
O(1)
不稳定
归并排序
O(nlogn)
O(nlogn)
O(nlogn)
O(n)
稳定
计数排序
O(n+k)
O(n+k)
O(n+k)
O(n+k)
稳定
桶排序
O(n+k)
O(n2 )
O(n)
O(n+k)
稳定
基数排序
O(n+k)
O(n+k)
O(n+k)
O(n+k)
稳定
二. 算法实现 1.冒泡排序（Bubble Sort） ① 算法思想
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
② 算法描述
比较相邻的元素。如果第一个比第二个大，就交换它们两个；
③ 动图演示
④ 代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 public class Solution { /** * 冒泡排序 */ public static void bubbleSort(int[] nums){ //一次 i 之后会产生一个最大的数 for (int i = 0; i < nums.length-1; i++) { //j 和 j+1 是待比较的两个元素的索引值 for (int j = 0; j < nums.length-1-i; j++) { if(nums[j] > nums[j+1]){ int temp = nums[j]; nums[j] = nums[j+1]; nums[j+1] = temp; } } } } /** * 测试程序 */ public static void main(String[] args) { int[] nums = new int[]{4,3,5,2,1}; //冒泡 bubbleSort(nums); for (int i = 0; i < nums.length; i++) { System.out.print(nums[i]+" "); } } }
⑤ 注意
上面的初阶写法，不管什么情况下，时间复杂度都是 O(n2 )。但是，经过下面的优化后，有序数组的时间复杂度在最好的情况下（已经排好序）才能达到 O(n)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 public class Solution { /** * 冒泡排序 */ public static void bubbleSort(int[] nums){ //标志 boolean flag = false; //一次 i 之后会产生一个最大的数 for (int i = 0; i < nums.length-1; i++) { //j 和 j+1 是待比较的两个元素的索引值 for (int j = 0; j < nums.length-1-i; j++) { if(nums[j] > nums[j+1]){ int temp = nums[j]; nums[j] = nums[j+1]; nums[j+1] = temp; //改变了 flag = true; } } //判断是否需要比较 if (!flag){ return; } } } /** * 测试程序 */ public static void main(String[] args) { int[] nums = new int[]{4,3,5,2,1}; //冒泡 bubbleSort(nums); for (int i = 0; i < nums.length; i++) { System.out.print(nums[i]+" "); } } }
2.快速排序（Quick Sort） ① 算法思想
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
② 算法描述
快速排序使用分治法来把一个串分为两个子串。具体算法描述如下：
从数列中挑出一个元素，称为 “基准”，一般选择第一个元素作为基准。
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面。在这个分区退出之后，该基准就处于数列的中间位置。
递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
③ 动图演示
④ 代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 public class Solution { /** * 快速排序 * @param nums */ public static void quickSort(int[] nums, int low, int high){ //区间只有一个元素了 结束 if (low >= high){ return; } //设置索引值 int left = low; int right = high; //设置基准点 int pivot = nums[left]; //当区间元素超过一个时 while (left < right){ //下面的遍历还需要 left < right，是为了防止极端情况 //从区间的右边遍历，只要大于基准就不需要移动 while (left < right && nums[right] > pivot){ right--; } //此时，必定出现了需要向左移动的元素 nums[left] = nums[right]; //从区间的左边遍历，只要小于基准就不需要移动 while (left < right && nums[left] < pivot){ left++; } //此时，必定出现了需要向右移动的元素 nums[right] = nums[left]; } //结束循环时，只有一个可能，left == right, 将基准值填入 nums[left] = pivot; //递归 quickSort(nums, low, left-1); quickSort(nums, left+1, high); } /** * 测试程序 * @param args */ public static void main(String[] args) { int[] nums = new int[]{4,3,5,2,1}; //快速 quickSort(nums,0,nums.length-1); for (int i = 0; i < nums.length; i++) { System.out.print(nums[i]+" "); } } }
⑤ 注意
1> 快速排序是不稳定的。
2> 快速排序的时间复杂度
最好的情况：
基准点的划分比较平均。
一个数组的容量是N,第一层递归遍历的次数是N。因为数组里每个数字都需要和key比较，那么接下来遍历分出来的两个区间，总的遍历次数还会是近似是N，以此类推，直到分为最后一个。
每划分一次，数据规模减半。划分到最后 N / 2树的高度 = 1，也就是说树的高度是logN，也就是递归次数,所以时间复杂度是N*logN.
最坏的情况：
待排序的序列为正序或者逆序。
每次划分只得到一个比上一次划分少一个记录的子序列，注意另一个为空。如果递归树画出来，它就是一棵斜树。
此时需要执行 n‐1 次递归调用，且第 i 次划分需要经过 n‐i 次的比较。2 )。
平均情况：
快速排序的最坏运行情况是O(n2 )，比如说顺序数列的快排。但它的平摊期望时间是O(nlogn) ，且O(nlogn)记号中隐含的常数因子很小，比复杂度稳定等于O(nlogn)的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
3> 快速排序的空间复杂度
就空间复杂度来说，主要是递归造成的栈空间的使用，最好情况，递归树的深度为log2n，其空间复杂度也就为O(logn)，最坏情况，需要进行n‐1递归调用，其空间复杂度为O(n)，平均情况，空间复杂度也为O(logn)。
4> 特性
当 n 较大时，在平均情况下快速排序是所有内部排序方法中速度最快的一种，所以其适合初始记录无序，n 较大的情况。
3.简单插入排序（Insertion Sort） ① 算法思维
插入排序的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
② 算法描述
从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5。
③ 动图演示
④ 代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 public class Solution { /** * 简单插入排序 * @param nums */ public static void insertionSort(int[] nums){ //默认第一个排序好 从第二个开始插入 要插入的元素的索引 i for(int i = 1; i < nums.length; i++){ //保存插入的元素 int insert = nums[i]; //逆着查找能插入的位置 int j; for(j = i-1; j >= 0; j--){ //若前面的数大，后移一位 //当前的位置 j 的元素已经后移，作为待插入的元素 //这个位置下次循环或者结束循环就变成了 j+1 if (nums[j] > insert){ nums[j+1] = nums[j]; }else { //找到了排好序的元素中比插入的元素的小的 break; } } //插入 nums[j+1] = insert; } } /** * 测试程序 * @param args */ public static void main(String[] args) { int[] nums = new int[]{9,7,8,10,6,4,3,5,2,1}; //快速 insertionSort(nums); for (int i = 0; i < nums.length; i++) { System.out.print(nums[i]+" "); } } }
⑤ 注意
时间复杂度：
4.希尔排序（Shell Sort） ① 算法思维
设待排序元素序列有n个元素，首先取一个整数increment（小于n）作为间隔将全部元素分为increment个子序列，所有距离为increment的元素放在同一个子序列中，在每一个子序列中分别实行直接插入排序。然后缩小间隔increment，重复上述子序列划分和排序工作。直到最后取increment=1，将所有元素放在同一个子序列中排序为止。
由于开始时，increment的取值较大，每个子序列中的元素较少，排序速度较快，到排序后期increment取值逐渐变小，子序列中元素个数逐渐增多，但由于前面工作的基础，大多数元素已经基本有序，所以排序速度仍然很快。
② 算法描述
③ 动图演示
④ 代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 public class Solution { /** * 希尔排序 * @param nums */ public static void shellSort(int[] nums){ //i 表示序列的间隔，一直到间隔1，这个时候就只有一个子序列 //0~i-1 for (int i = nums.length / 2; i > 0; i /= 2) { //从 i 之后每个数字都要进行插入排序，在各自的序列中进行简单的插入排序 for (int j = i; j < nums.length; j++) { //保存插入的元素 int insert = nums[j]; //逆着查找能插入的位置 int k; for(k = j-i; k >= 0; k -= i){ //若前面的数大，后移一位 //当前的位置 j 的元素已经后移，作为待插入的元素 //这个位置下次循环或者结束循环就变成了 j+1 if (nums[k] > insert){ nums[k+i] = nums[k]; }else { //找到了排好序的元素中比插入的元素的小的 break; } } //插入 nums[k+i] = insert; } } } /** * 测试程序 * @param args */ public static void main(String[] args) { int[] nums = new int[]{9,7,8,10,6,4,3,5,2,1}; //希尔排序 shellSort(nums); for (int i = 0; i < nums.length; i++) { System.out.print(nums[i]+" "); } } }
⑤ 注意
1> 希尔排序是不稳定的
由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
例子 3 5 10 8 7 2 8 1 20 6，d=2 分成2组 （3 10 7 8 20） 和（5 8 2 1 6） 第一组的8在第二组的后面，排序后（3 7 8 10 20）和 （1 2 5 6 8）， 现在是第一组的8在第二组前面了 。不稳定不是说排序的结果出错，而是说如果初始数据里有相同的数据（如例子里的两个8，可以记为8’,8’’），经过排序后原来在后面的数字排在了前面（变成8’’,8’）。
2> 时间复杂度：
希尔排序的复杂度和增量序列是相关的：
{1,2,4,8,…}这种序列并不是很好的增量序列，使用这个增量序列的时间复杂度（最坏情形）是O(n2 )。
Hibbard提出了另一个增量序列{1,3,7，…,2k−1}，这种序列的时间复杂度（最坏情形）为O(n1.5 )。
Sedgewick提出了几种增量序列，其最坏情形运行时间为O(n1.3 )，其中最好的一个序列是{1,5,19,41,109,…}。
希尔排序的分析是一个复杂的问题，它的时间受所取“增量”序列的函数所影响，这涉及到一些数学上尚未解决的难题。
3> 特性
记录总的比较次数和移动次数都比直接插入排序要少，n越大时，效果越明显。所以适合初始记录无序，n 较大的情况。
5.简单选择排序（Selection Sort） ① 算法思维
选择排序是一种简单直观的排序算法。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始（结束）位置。然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾（开始）。以此类推，直到所有元素均排序完毕。
② 算法描述
n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果
初始状态：无序区为R[1..n]，有序区为空；
第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
n-1趟结束，数组有序化了。
③ 动图演示
④ 代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 public class Solution { /** * 简单选择排序 * @param nums */ public static void selectionSort(int[] nums){ //i 代表 i所在的索引位置按顺序排列应该存放的值 for (int i = 0; i < nums.length-1; i++) { //假设i位置的值就应该放在i出 int minIndex = i; //和后面的数字依次比较，找到 i 位置真正应该存放的值的 索引位置 for (int j = i+1; j < nums.length; j++) { if (nums[minIndex] > nums[j]){ minIndex = j; } } // i 位置存放真正应该存放的值 //同时将 i 位置原本存放的值存放在找到最小值的位置 //即 交换 两处位置的值 int temp = nums[i]; nums[i] = nums[minIndex]; nums[minIndex] = temp; } } /** * 测试程序 * @param args */ public static void main(String[] args) { int[] nums = new int[]{9,7,8,10,6,4,3,5,2,1}; //简单选择排序 selectionSort(nums); for (int i = 0; i < nums.length; i++) { System.out.print(nums[i]+" "); } } }
⑤ 注意
1> 简单选择排序是不稳定的
2> 时间复杂度2 )的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
6.堆排序（Heap Sort） ① 算法思维
n个元素的序列 {k1,k2,…,kn}称之为堆，当且仅当满足以下条件时：ki>=k2i 且 ki>=k2i+1（或 ki=<k2i 且 ki=<k2i+1）。
堆排序 是一种 树形选择排序，它比一般的树形选择排序更优。
将待排序的 nums[1….n]，看成是一个完全二叉树的顺序存储结构，利用完全二叉树中孩子结点和双亲结点之间的关系，在当前无序的序列中选择最大值。
② 算法描述
按堆的定义将待排序序列 nums[1…n] 调整为大根堆（这个过程称之为建初堆），交换 nums[1] 和 nums[n]，则 nums[n] 为关键字最大的记录。
将 nums[1…n-1] 重新调整为堆，交换 nums[1] 和 nums[n-1]，则 nums[n-1] 为关键字次大的记录。
循环 n-1 次，直到交换了 nums[1] 和 nums[2]为止，得到一个非递减的有序序列 nums[1…n]。
③ 动图演示
④ 代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 public class Solution { /** * 堆排序 * @param nums */ public static void heapSort(int[] nums){ //建立大根初堆 createHeap(nums); //每次遍历根据最大堆可以得到一个最大数 for (int i = nums.length-1; i >= 0; i--){ //将最大的数移到最后 int temp = nums[0]; nums[0] = nums[i]; nums[i] = temp; //除开已经确定的最大的数，剩下的数重新调整为新的大根堆 heapAdjust(nums,0,i); } } /** * 调整堆 * @param nums * @param s * @param length */ public static void heapAdjust(int[] nums, int s, int length){ //nums[s+1,length) 已经是堆，将 nums[s,length) 范围内的数据调整为以 nums[s] 为根的大根堆 //保存目前最顶层的根 int root = nums[s]; //沿值较大的孩子结点向下筛选 //假设 左孩子（2(i+1)-1）就是最大的 for (int j = 2*s+1; j < length; j = j*2+1){ //判断到底是左孩子大还是右孩子大 //根据结果调整 j 的值 if (j+1 < length && nums[j] < nums[j+1]){ j++; } //判断当前是否已经是大根堆 if (root >= nums[j]){ break; } //不是的话，交换 左右孩子中大的值 和 root nums[s] = nums[j]; //同样的，nums[j+1,length] 已经是堆，循环筛选调整 s = j; } //此时已经调整完毕，j位置插入应该插入的值 nums[s] = root; } /** * 建初堆 * @param nums */ public static void createHeap(int[] nums){ //遍历叶子节点以外的节点，反复调整 for (int i = nums.length / 2; i > 0; i--){ //调整 heapAdjust(nums,i-1, nums.length); } } /** * 测试程序 * @param args */ public static void main(String[] args) { int[] nums = new int[]{9,7,8,10,6,4,3,5,2,1}; //堆排序 heapSort(nums); for (int i = 0; i < nums.length; i++) { System.out.print(nums[i]+" "); } } }
⑤ 注意
1> 堆排序是一个不稳定的排序
我们知道堆的结构是节点i的孩子为2 * i和2 * i + 1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。
在一个长为n 的序列，堆排序的过程是从第n / 2开始和其子节点共3个值选择最大（大顶堆）或者最小（小顶堆），这3个元素之间的选择当然不会破坏稳定性。但当为n / 2 - 1， n / 2 - 2， … 1这些个父节点选择元素时，就会破坏稳定性。
有可能第n / 2个父节点交换把后面一个元素交换过去了，而第n / 2 - 1个父节点把后面一个相同的元素没 有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。
2> 时间复杂度
构建堆的过程：假设高度为k，则从倒数第二层右边的节点开始，这一层的节点都要执行子节点比较然后交换（如果顺序是对的就不用交换）；倒数第三层呢，则会选择其子节点进行比较和交换，如果没交换就可以不用再执行下去了。如果交换了，那么又要选择一支子树进行比较和交换；那么总的时间计算为：s=2(i−1) ∗(k−i) ;其中 i 表示第几层，2(i−1) 表示该层上有多少个元素，( k - i) 表示子树上要比较的次数，如果在最差的条件下，就是比较次数后还要交换；因为这个是常数，所以提出来后可以忽略。(k-2) ∗1+2(k-3) ∗2…..+2∗(k−2)+20 ∗(k−1) ， 因为叶子层不用交换，所以i从 k-1 开始到 1。等式左右乘上2，然后和原来的等式相减，就变成了：S=2(k−1) +2(k−2) …..+2-(k−1) 。除最后一项外，就是一个等比数列了，直接用求和公式，得到结果：S = 2k -k-1。k 为二叉树的深度，即 k = logn，则 S = n - logn - 1，所以时间复杂度为 O(n)。
更改堆元素重建的过程：循环 n -1 次，每次都是从根节点往下循环查找，所以每一次时间是 logn，总时间：(n-1) logn= nlogn - logn，所以时间复杂度为 O(nlogn)。
总结起来，堆排序的时间复杂度为 O(nlogn)。
3> 特性
初始建堆所需的比较次数较多，因此记录较少时不宜采用。堆排序在最坏情况下时间复杂度为 O(nlogn)，相对于快速排序最坏情况下的 O(n2 ) 而言是一个优点，当记录较多时较为高效。
7.归并排序（Merge Sort） ① 算法思维
该算法采用经典的分治策略。假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1。然后两两归并，得到n/2个长度为2或1的有序子序列，再两两归并，如此反复，直至得到一个长度为n的有序序列为止。（2-路归并排序）
② 算法描述
把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。
③ 动图演示
④ 代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 public class Solution { /** * 归并排序 * @param nums * @param start * @param end */ public static void mergeSort(int[] nums,int start,int end){ //只要划分的区间长度仍然不为1 if (start != end){ int middle = (start+end) / 2; //分 mergeSort(nums,start,middle); mergeSort(nums,middle+1,end); //治 merge(nums,start,end,middle); } } /** * 归并 * @param nums * @param start * @param end * @param middle */ public static void merge(int[] nums,int start,int end,int middle){ //模拟第一个序列的头指针 int i = start; //模拟第二个序列的头指针 int j = middle+1; //模拟临时数组的头指针 int t = 0; //创建临时数组 int[] temp = new int[end-start+1]; //从头比较两个序列，小的放入临时数组temp while (i <= middle && j <= end){ //比较大小 if (nums[i] < nums[j]){ //前一个序列 temp[t++] = nums[i++]; }else { //后一个序列 temp[t++] = nums[j++]; } } //单独处理没有处理完的第一个序列 while (i <= middle){ temp[t++] = nums[i++]; } //单独处理没有处理完的第二个序列 while (j <= end){ temp[t++] = nums[j++]; } //将临时数组的值赋值到原数组 for (int p = 0; p < temp.length; p++) { nums[start+p] = temp[p]; } } /** * 测试程序 * @param args */ public static void main(String[] args) { int[] nums = new int[]{9,7,8,10,6,4,3,5,2,1}; //归并排序 mergeSort(nums,0,nums.length-1); for (int i = 0; i < nums.length; i++) { System.out.print(nums[i]+" "); } } }
⑤ 注意
1> 时间复杂度
时间复杂度主要是 数组划分递归函数mergeSort 和 归并函数 merge。递归深度为logn，每一层递归后归并的时间复杂度是O(n)，所以总的平均时间复杂度为O(nlogn)。
2> 空间复杂度
归并的空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间：n+lognn ；所以空间复杂度为: O(n)。
3> 特性
归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。
8.计数排序（Counting Sort） ① 算法思维
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
② 算法描述
找出待排序的数组中 最大max 和 最小min 的元素，创建辅助数组 help。
统计数组中每个值为 i 的元素出现的次数，存入辅助数组 help 的第 i-min 项。
遍历辅助数组 help，依次将值赋值给 nums数组。
③ 动图演示
④ 代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 public class Solution { /** * 计数排序 * @param nums */ public static void countingSort(int[] nums){ //创建保存两个最值的变量 int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; //找出数组中的最大值，最小值 for (int i = 0; i < nums.length; i++) { max = Math.max(max,nums[i]); min = Math.min(min,nums[i]); } //辅助数组 int[] help = new int[max-min+1]; //找出每个数字出现的次数 for (int i = 0; i < nums.length; i++) { //将该数字向min看齐，方便计算数字出现的次数 int temp = nums[i] - min; //修改次数 help[temp]++; } //模拟目标数组的头指针 int index = 0; //遍历辅助数组，排序 for (int i = 0; i < help.length; i++) { //判断当前位置的数字是否 while (help[i] > 0){ //数字还原，赋值 nums[index++] = i+min; //数字记录数减1 help[i]--; } } } /** * 测试程序 * @param args */ public static void main(String[] args) { int[] nums = new int[]{9,7,8,10,6,4,3,5,2,1}; //计数排序 countingSort(nums); for (int i = 0; i < nums.length; i++) { System.out.print(nums[i]+" "); } } }
⑤ 注意
1> 时间复杂度
O(n+k)
2> 空间复杂度
O(n+k)
9.桶排序（Bucket Sort） ① 算法思维
② 算法描述
找出待排序数组 nums 中的最大值max、最小值min。
我们使用 动态数组ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为 (max-min)/nums.length+1。
遍历数组 nums，计算每个元素 nums[i] 放的桶。
每个桶各自排序。
遍历桶数组，把排序好的元素放进输出数组。
③ 动图演示
④ 代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 public class Solution { /** * 桶排序 * @param nums */ public static void bucketSort(int[] nums){ //创建保存两个最值的变量 int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; //找出数组中的最大值，最小值 for (int i = 0; i < nums.length; i++) { max = Math.max(max,nums[i]); min = Math.min(min,nums[i]); } //计算桶的数目 int bucketNum = (max-min)/nums.length+1; List<List<Integer>> bucket = new ArrayList<>(); for (int i = 0; i < bucketNum; i++) { bucket.add(new ArrayList<Integer>()); } //将每个元素放入桶中 for (int i = 0; i < nums.length; i++) { //得到应该存放的桶的索引 int index = (nums[i]-min) / nums.length; //加入到对应的桶 bucket.get(index).add(nums[i]); } //每个桶内内部排序 for (int i = 0; i < bucket.size(); i++) { Collections.sort(bucket.get(i)); } //改变传来的数组 int index = 0; for (int i = 0; i < bucket.size(); i++) { for (int j = 0; j < bucket.get(i).size(); j++) { nums[index++] = bucket.get(i).get(j); } } } /** * 测试程序 */ public static void main(String[] args) { int[] nums = new int[]{9,7,8,10,6,4,3,5,2,1}; //桶排序 bucketSort(nums); for (int i = 0; i < nums.length; i++) { System.out.print(nums[i]+" "); } } }
⑤ 注意
1> 时间复杂度
O(n+k)
2> 空间复杂度
O(n+k)
10.基数排序（Radix Sort） ① 算法思维
按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
② 算法描述
③ 动图演示
④ 代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 public class Solution { /** * 基数排序 * @param nums */ public static void radixSort(int[] nums){ //找到最大数 int max = Integer.MIN_VALUE; for (int num : nums) { if (max < num){ max = num; } } //从个位开始，对数组进行排序 for (int i = 1; max / i > 0; i *= 10){ //存储待排序的临时数组 int[] temp = new int[nums.length]; //范围个数桶 10进制的：0,1,2,3,4,5,6,7,8,9 List[] bucket = new List[10]; for (int j = 0; j < 10; j++) { bucket[j] = new ArrayList<>(); } //将数据出现的次数存储在桶里面 for (int num : nums) { //从最低位(个位)开始 bucket[(num / i) % 10].add(num); } //将数据存储到临时数组中 int index = 0; for(int j = 0; j < 10; j++){ //依次取出桶里面的每一个数据 for (int k = 0; k < bucket[j].size(); k++) { temp[index++] = (Integer) bucket[j].get(k); } } //将有序元素temp赋给nums2 System.arraycopy(temp, 0, nums, 0, nums.length); } } /** * 测试程序 */ public static void main(String[] args) { int[] nums = new int[]{9,87,18,20,6,34,3,65,22,61}; //基数 radixSort(nums); for (int i = 0; i < nums.length; i++) { System.out.print(nums[i]+" "); } } }
⑤ 注意
1> 时间复杂度
O(n+k)
2> 空间复杂度
O(n+k)
3> 区别
首先，基数排序和计数排序都可以看作是桶排序。
计数排序本质上是一种特殊的桶排序，当桶的个数取最大( maxV-minV+1 )的时候，就变成了计数排序。
基数排序也是一种桶排序。桶排序是按值区间划分桶，基数排序是按数位来划分；基数排序可以看做是多轮桶排序，每个数位上都进行一轮桶排序。
当用最大值作为基数时，基数排序就退化成了计数排序。
当使用2进制时， k=2 最小，位数 d 最大，时间复杂度 O(nd) 会变大，空间复杂度 O(n+k) 会变小。当用最大值作为基数时， k=maxV 最大， d=1 最小，此时时间复杂度 O(nd) 变小，但是空间复杂度 O(n+k) 会急剧增大，此时基数排序退化成了计数排序。
参考文章 java实现八大排序
十大排序算法以及关系
各个排序算法及其时间复杂度
巧解快速排序的时间复杂度
快速排序最好、最坏、平均时间复杂度分析
彻底搞懂稳定排序与不稳定排序
图解排序算法(四)之归并排序
计数排序和桶排序（Java实现）
基数排序、桶排序和计数排序的区别
