动画+原理+代码+优化，解读十大经典排序算法
动画+原理+代码+优化，解读十大经典排序算法
排序算法是《数据结构与算法》中最基本的算法之一。
排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括：
关于时间复杂度：
1、平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。 2、线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序； 3、O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序 4、线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。
关于稳定性：
1、稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。 2、不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。
名词解释：
n：数据规模k：“桶”的个数In-place：占用常数内存，不占用额外内存Out-place：占用额外内存稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同
一、冒泡排序
冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
作为最简单的排序算法之一，冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。
1. 算法步骤
1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。 2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。 3、针对所有的元素重复以上的步骤，除了最后一个。 4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
2. 动图演示
3. 什么时候最快
当输入的数据已经是正序时（都已经是正序了，我还要你冒泡排序有何用啊）。
4. 什么时候最慢
当输入的数据是反序时（写一个 for 循环反序输出数据不就行了，干嘛要用你冒泡排序呢，我是闲的吗）。
5. java代码实现
1. public static void BubbleSort(int[] arr) {2. int temp; //临时变量3. for (int i = 0; i < arr.length - 1; i++) { //表示趟数，一共arr.length-1次。4. for (int j = arr.length - 1; j > i; j--) {5. if (arr[j] < arr[j - 1]) {6. temp = arr[j];7. arr[j] = arr[j - 1];8. arr[j - 1] = temp;9. }10. }11. }12. }6. 优化
针对问题：
数据的顺序排好之后，冒泡算法仍然会继续进行下一轮的比较，直到arr.length-1次，后面的比较没有意义的。
方案：
设置标志位flag，如果发生了交换flag设置为true；如果没有交换就设置为false。 这样当一轮比较结束后如果flag仍为false，即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去。
1. public static void BubbleSort1(int [] arr){2. int temp;//临时变量3. boolean flag;//是否交换的标志4. for(int i=0; i<arr.length-1; i++){ //表示趟数，一共arr.length-1次。5. flag = false;6. for(int j=arr.length-1; j>i; j--){7. if(arr[j] < arr[j-1]){8. temp = arr[j];9. arr[j] = arr[j-1];10. arr[j-1] = temp;11. flag = true;12. }13. }14. if(!flag) break;15. }16. }二、选择排序
选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
1. 算法步骤
1、首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置 2、再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。 3、重复第二步，直到所有元素均排序完毕。
2. 动图演示
3. java代码实现
1. public static void select_sort(int array[], int lenth) {2. for (int i = 0; i < lenth - 1; i++) {3. int minIndex = i;4. for (int j = i + 1; j < lenth; j++) {5. if (array[j] < array[minIndex]) {6. minIndex = j;7. }8. }9. if (minIndex != i) {10. int temp = array[i];11. array[i] = array[minIndex];12. array[minIndex] = temp;13. }14. }15. }三、插入排序
插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。
1. 算法步骤
1、将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。 2、从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
2. 动图演示
3. java代码实现
1. public static void insert_sort(int array[], int lenth) {2. int temp;3. for (int i = 0; i < lenth - 1; i++) {4. for (int j = i + 1; j > 0; j--) {5. if (array[j] < array[j - 1]) {6. temp = array[j - 1];7. array[j - 1] = array[j];8. array[j] = temp;9. } else { //不需要交换10. break;11. }12. }13. }14. }四、希尔排序
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率； 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
1. 算法步骤
1、选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
2、按增量序列个数 k，对序列进行 k 趟排序； 3、每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
2. java代码实现
1. public static void shell_sort(int array[], int lenth) {2. int temp = 0;3. int incre = lenth;4. while (true) {5. incre = incre / 2;6. for (int k = 0; k < incre; k++) { //根据增量分为若干子序列7. for (int i = k + incre; i < lenth; i += incre) {8. for (int j = i; j > k; j -= incre) {9. if (array[j] < array[j - incre]) {10. temp = array[j - incre];11. array[j - incre] = array[j];12. array[j] = temp;13. } else {14. break;15. }16. }17. }18. }19. if (incre == 1) {20. break;21. }22. }23. }五、归并排序
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
1、自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
2、自下而上的迭代；在《数据结构与算法 JavaScript 描述》中，作者给出了自下而上的迭代方法。但是对于递归法，作者却认为：However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.然而，在 JavaScript 中这种方式不太可行，因为这个算法的递归深度对它来讲太深了。说实话，我不太理解这句话。意思是 JavaScript 编译器内存太小，递归太深容易造成内存溢出吗？还望有大神能够指教。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。
1. 算法步骤
1、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2、设定两个指针，最初位置分别为两个已经排序序列的起始位置； 3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置； 4、重复步骤 3 直到某一指针达到序列尾； 5、将另一序列剩下的所有元素直接复制到合并序列尾。
2. 动图演示
3. java 代码实现
1. /将有序数组a[]和b[]合并到c[]中2. void MemeryArray(int a[], int n, int b[], int m, int c[]){4. int i, j, k;5. i = j = k = 0;6. while (i < n && j < m){ 8. if (a[i] < b[j])9. c[k++] = a[i++];10. else11. c[k++] = b[j++];12. }13. while (i < n)14. c[k++] = a[i++];15. while (j < m)16. c[k++] = b[j++];17. }六、快速排序
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好，可是这是为什么呢，我也不知道。好在我的强迫症又犯了，查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案：
快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
1. 算法步骤
1、从数列中挑出一个元素，称为 “基准”（pivot）;
2、重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作； 3、递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
基本思想：（分治）
- 先从数列中取出一个数作为key值；
- 将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
- 对左右两个小数列重复第二步，直至各区间只有1个数。
辅助理解：挖坑填数
初始时 i = 0; j = 9; key=72
1、由于已经将a[0]中的数保存到key中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。 2、从j开始向前找一个比key小的数。当j=8，符合条件，a[0] = a[8] ; i++ ; 将a[8]挖出再填到上一个坑a[0]中。 3、这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。 4、这次从i开始向后找一个大于key的数，当i=3，符合条件，a[8] = a[3] ; j– ; 将a[3]挖出再填到上一个坑中。
1. 数组：72 - 6 - 57 - 88 - 60 - 42 - 83 - 73 - 48 - 85
2. 0 1 2 3 4 5 6 7 8 9- 1、此时 i = 3; j = 7; key=72
- 2、再重复上面的步骤，先从后向前找，再从前向后找。
- 3、从j开始向前找，当j=5，符合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; i++;
- 4、从i开始向后找，当i=5时，由于i==j退出。
- 5、此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将key填入a[5]。
1. 数组：48 - 6 - 57 - 88 - 60 - 42 - 83 - 73 - 88 - 85
2. 0 1 2 3 4 5 6 7 8 9可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。
1. 数组：48 - 6 - 57 - 42 - 60 - 72 - 83 - 73 - 88 - 85
2. 0 1 2 3 4 5 6 7 8 92. 动图演示
3. java版
1. public static void quickSort(int a[], int l, int r) {2. if (l >= r) return;3. int i = l;4. int j = r;5. int key = a[l]; //选择第一个数为key6. while (i < j) {7. while (i < j && a[j] >= key) //从右向左找第一个小于key的值8. j--;9. if (i < j) {10. a[i] = a[j];11. i++;12. }
13. while (i < j && a[i] < key) //从左向右找第一个大于key的值14. i++;15. if (i < j) {16. a[j] = a[i];17. j--;18. }19. }20. //i == j21. a[i] = key;22. quickSort(a, l, i - 1); //递归调用23. quickSort(a, i + 1, r); //递归调用24. }key值的选取可以有多种形式，例如中间数或者随机数，分别会对算法的复杂度产生不同的影响。
七、堆排序
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
1、大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列； 2、小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
堆排序的平均时间复杂度为 Ο(nlogn)。
1. 算法步骤
1、创建一个堆 H[0……n-1]； 2、把堆首（最大值）和堆尾互换； 3、把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置； 4、重复步骤 2，直到堆的尺寸为 1。
2. 动图演示
3. java代码实现
1. //构建最小堆2. public static void MakeMinHeap(int a[], int n) {3. for (int i = (n - 1) / 2; i >= 0; i--) {4. MinHeapFixdown(a, i, n);5. }6. }
7. //从i节点开始调整,n为节点总数 从0开始计算 i节点的子节点为 2*i+1, 2*i+2 8. public static void MinHeapFixdown(int a[], int i, int n) {9. int j = 2 * i + 1; //子节点10. int temp = 0;11. while (j < n) {12. //在左右子节点中寻找最小的13. if (j + 1 < n && a[j + 1] < a[j]) {14. j++;15. }16. if (a[i] <= a[j]) break;17. //较大节点下移18. temp = a[i];19. a[i] = a[j];20. a[j] = temp;21. i = j;22. j = 2 * i + 1;23. }24. }
25. public static void MinHeap_Sort(int a[], int n) {26. int temp = 0;27. MakeMinHeap(a, n);28. for (int i = n - 1; i > 0; i--) {29. temp = a[0];30. a[0] = a[i];31. a[i] = temp;32. MinHeapFixdown(a, 0, i);33. }34. }八、计数排序
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
1、计数排序是一种非常快捷的稳定性强的排序方法，时间复杂度O(n+k),其中n为要排序的数的个数，k为要排序的数的组大值。计数排序对一定量的整数排序时候的速度非常快，一般快于其他排序算法。但计数排序局限性比较大，只限于对整数进行排序。计数排序是消耗空间发杂度来获取快捷的排序方法，其空间发展度为O（K）同理K为要排序的最大值。
2、计数排序的基本思想为一组数在排序之前先统计这组数中其他数小于这个数的个数，则可以确定这个数的位置。例如要排序的数为 7 4 2 1 5 3 1 5；则比7小的有7个数，所有7应该在排序好的数列的第八位，同理3在第四位，对于重复的数字，1在1位和2位（暂且认为第一个1比第二个1小），5和1一样位于6位和7位。
1. 动图演示
2. java 代码实现
1. public static void main(String[] args) throws Exception {2. int[] array = {3. 9, 8, 7, 6, 5, 4, 3, 2, 6, 1, 04. };
5. System.out.println("Before sort:");6. ArrayUtils.printArray(array);7. countingSort(array, 9);
8. System.out.println("After sort:");9. ArrayUtils.printArray(array);10. }
11. public static void countingSort(int[] array, int range) throws Exception {12. if (range <= 0) {13. throw new Exception("range can't be negative or zero.");14. }
15. if (array.length <= 1) {16. return;17. }
18. int[] countArray = new int[range + 1];19. for (int i = 0; i < array.length; i++) {20. int value = array[i];21. if (value < 0 || value > range) {22. throw new Exception("array element overflow range.");23. }24. countArray[value] += 1;25. }26. for (int i = 1; i < countArray.length; i++) {27. countArray[i] += countArray[i - 1];28. }29. int[] temp = new int[array.length];30. for (int i = array.length - 1; i >= 0; i--) {31. int value = array[i];32. int position = countArray[value] - 1;33. temp[position] = value;34. countArray[value] -= 1;35. }36. for (int i = 0; i < array.length; i++) {37. array[i] = temp[i];38. }39. }九、桶排序
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：
1、在额外空间充足的情况下，尽量增大桶的数量 2、使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
1. 什么时候最快
当输入的数据可以均匀的分配到每一个桶中。
2. 什么时候最慢
当输入的数据被分配到了同一个桶中。
3. Java 代码实现
1. /**
2. * 桶排序假设输入元素均匀而独立的分布在区间[0，1）上；
3. * 桶排序的核心思想是，将[0，1）分为n个大小相同的子区间，
4. * 上一个区间里的元素都比下一个区间里的元素小，然后对
5. * 所有区间里的元素排序，最后顺序输出所有区间里的元素，
6. * 达到对所有元素排序的目的。
7. *
8. */
9. public class bucketSort {
10. public void sort(Double[] a) {
11. int n = a.length;
12. /**
13. * 创建链表（桶）集合并初始化，集合中的链表用于存放相应的元素
14. */
15. int bucketNum = 10; // 桶数
16. LinkedList<LinkedList<Double>> buckets = new LinkedList<LinkedList<Double>>();
17. for(int i = 0; i < bucketNum; i++){
18. LinkedList<Double> bucket = new LinkedList<Double>();
19. buckets.add(bucket);
20. }
21. // 把元素放进相应的桶中
22. for(int i = 0; i < n; i++){
23. int index = (int) (a[i] * bucketNum);
24. buckets.get(index).add(a[i]);
25. }
26. // 对每个桶中的元素排序，并放进a中
27. int index = 0;
28. for (LinkedList<Double> linkedList : buckets) {
29. int size = linkedList.size();
30. if (size == 0) {
31. continue;
32. }
33. /**
34. * 把LinkedList<Double>转化为Double[]的原因是，之前已经实现了
35. * 对数组进行排序的算法
36. */
37. Double[] temp = new Double[size];
38. for (int i = 0; i < temp.length; i++) {
39. temp[i] = linkedList.get(i);
40. }
41. // 利用插入排序对temp排序
42. new InsertSort().sort(temp);
43. for (int i = 0; i < temp.length; i++) {
44. a[index] = temp[i];
45. index++;
46. }
47. }
48. }
49. public static void main(String[] args) {
50. Double[] a = new Double[]{0.3, 0.6, 0.5};
51. new BucketSort().sort(a);
52. for (int i = 0; i < a.length; i++) {
53. System.out.println(a[i]);
54. }
55. }十、基数排序
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
1. 基数排序 vs 计数排序 vs 桶排序
基数排序有两种方法：
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
1、基数排序：根据键值的每位数字来分配桶； 2、计数排序：每个桶只存储单一键值； 3、桶排序：每个桶存储一定范围的数值；
2. LSD 基数排序动图演示
3. Java 代码实现
1. /**
2. * 基数排序
3. * 考虑负数的情况还可以参考： https://code.i-harness.com/zh-CN/q/e98fa9
4. */
5. public class RadixSort implements IArraySort {@
6. Override
7. public int[] sort(int[] sourceArray) throws Exception {
8. // 对 arr 进行拷贝，不改变参数内容
9. int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
10. int maxDigit = getMaxDigit(arr);
11. return radixSort(arr, maxDigit);
12. }
13. /**
14. * 获取最高位数
15. */
16. private int getMaxDigit(int[] arr) {
17. int maxValue = getMaxValue(arr);
18. return getNumLenght(maxValue);
19. }
20. private int getMaxValue(int[] arr) {
21. int maxValue = arr[0];
22. for (int value: arr) {
23. if (maxValue < value) {
24. maxValue = value;
25. }
26. }
27. return maxValue;
28. }
29. protected int getNumLenght(long num) {
30. if (num == 0) {
31. return 1;
32. }
33. int lenght = 0;
34. for (long temp = num; temp != 0; temp /= 10) {
35. lenght++;
36. }
37. return lenght;
38. }
39. private int[] radixSort(int[] arr, int maxDigit) {
40. int mod = 10;
41. int dev = 1;
42. for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
43. // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
44. int[][] counter = new int[mod * 2][0];
45. for (int j = 0; j < arr.length; j++) {
46. int bucket = ((arr[j] % mod) / dev) + mod;
47. counter[bucket] = arrayAppend(counter[bucket], arr[j]);
48. }
49. int pos = 0;
50. for (int[] bucket: counter) {
51. for (int value: bucket) {
52. arr[pos++] = value;
53. }
54. }
55. }
56. return arr;
57. }
58. /**
59. * 自动扩容，并保存数据
60. *
61. * @param arr
62. * @param value
63. */
64. private int[] arrayAppend(int[] arr, int value) {
65. arr = Arrays.copyOf(arr, arr.length + 1);
66. arr[arr.length - 1] = value;
67. return arr;
68. }
69. }