0.通用测试代码

  1. package com.sgg.algorithm.sort.util;
  3. import com.sgg.algorithm.sort.BubbleSort;
  4. import com.sgg.algorithm.sort.InsertSort;
  5. import com.sgg.algorithm.sort.SelectSort;
  7. import java.util.function.Consumer;
  9. public class CommonUtil {
  10.     public static void test(Consumer<int[]> consumer) {
  11.         long l = System.currentTimeMillis();
  12.         int[] arr = genArray();
  13.         consumer.accept(arr);
  14.         System.out.println("耗时" + (System.currentTimeMillis() - l) + "豪秒");
  15.         System.out.println(isSort(arr));
  16.         System.out.println("======================================================");
  17.     }
  19.     public static int[] genArray() {
  20.         int size = 80000;
  21.         int[] arr = new int[size];
  22.         for (int i = 0; i < size; i++) {
  23.             arr[i] = (int) (Math.random() * 10000000);
  24.         }
  25.         return arr;
  26.     }
  28.     private static boolean isSort(int[] arr) {
  29.         for (int i = 0; i < arr.length - 1; i++) {
  30.             if (arr[i] > arr[i + 1]) {
  31.                 return false;
  32.             }
  33.         }
  34.         return true;
  35.     }
  37.     public static void main(String[] args) {
  38.         CommonUtil.test(BubbleSort::sortImprove);
  39.         CommonUtil.test(SelectSort::sort);
  40.         CommonUtil.test(InsertSort::sort);
  41.         CommonUtil.test(InsertSort::insertSort);
  43.     }
  44. }

1.冒泡排序

介绍和思路

冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）,依次比较
相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。

代码

  1. package com.sgg.algorithm.sort;
  3. import java.util.Arrays;
  5. //O(n2)
  6. public class BubbleSort {
  8.     public static void sort(int[] arr) {
  9.         int size = arr.length;
  10.         for (int i = 0; i < size - 1; i++) {
  11.             for (int j = 0; j < size - 1 - i; j++) {
  12.                 if (arr[j] > arr[j + 1]) {
  13.                     int temp = arr[j];
  14.                     arr[j] = arr[j + 1];
  15.                     arr[j + 1] = temp;
  16.                 }
  17.             }
  18. //            System.out.println("第" + (i + 1) + "次排序后的数组:" + Arrays.toString(arr));
  19.         }
  20.     }
  22.     //优化:一次排序,没有变化,就说明已经有序了
  23.     public static void sort2(int[] arr) {
  24.         int size = arr.length;
  25.         boolean flag = false;
  27.         for (int i = 0; i < size - 1; i++) {
  28.             for (int j = 0; j < size - 1 - i; j++) {
  29.                 if (arr[j] > arr[j + 1]) {
  30.                     int temp = arr[j];
  31.                     arr[j] = arr[j + 1];
  32.                     arr[j + 1] = temp;
  33.                     flag = true;
  34.                 }
  35.             }
  36. //            System.out.println("第" + (i + 1) + "次排序后的数组:" + Arrays.toString(arr));
  37.             if (!flag) {
  38.                 break;
  39.             } else {
  40.                 flag = false;
  41.             }
  42.         }
  43.     }
  44. }

优化

一次排序,没有交换,就说明已经有序了

2.选择排序

介绍和思路

选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的
选择排序（select sorting）
它的基本思想是：第一次从arr[0]~arr[n-1]中选取最小值，与arr[0]交换，
第二次从arr[1]~arr[n-1]中选取最小值，与arr[1]交换，
第三次从arr[2]~arr[n-1]中选取最小值，与arr[2]交换，
第i次从arr[i-1]~arr[n-1]中选取最小值，与arr[i-1]交换
第n-1次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换，
总共通过n-1次，得到一个按排序码从小到大排列的有序序列。

代码

  1. package com.sgg.algorithm.sort;
  3. import java.util.Arrays;
  5. public class SelectSort {
  7.     /**
  8.      * 第一轮:找到最小的,跟第1个交换
  9.      * 第二轮:找到后面的最小的,跟第2个换
  10.      * 第二轮:找到后面的最小的,跟第3个换
  11.      */
  12.     public static void sort(int[] arr) {
  13.         for (int i = 0; i < arr.length; i++) {
  14.             int index = i;
  15.             for (int j = i; j < arr.length; j++) {
  16.                 if (arr[j] < arr[index]) {
  17.                     index = j;
  18.                 }
  19.             }
  20.             int temp = arr[index];
  21.             arr[index] = arr[i];
  22.             arr[i] = temp;
  23.         }
  24.     }
  25. }

3.插入排序

介绍和思路

插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的
插入排序（Insertion Sorting）的基本思想是：
把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，
排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

思路图

image.png

代码

  1. package com.sgg.algorithm.sort;
  3. public class InsertSort {
  4.     /**
  5.      * 老师的思路
  6.      */
  7.     public static void insertSort(int[] arr) {
  8.         for (int i = 1; i < arr.length; i++) {
  9.             int insertVal = arr[i];//先记录插入的值,后面被覆盖
  10.             int insertIndex = i - 1;//需要插入的位置
  11.             while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
  12.                 arr[insertIndex + 1] = arr[insertIndex];
  13.                 insertIndex--;
  14.             }
  15.             arr[insertIndex + 1] = insertVal;
  16.         }
  17.     }
  18. }

4.希尔排序

介绍和思路

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序

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

示意图

image.png

代码

有交换法和移动法两种

  1. package com.sgg.algorithm.sort;
  4. import java.util.Arrays;
  6. /**
  7.  * 插入排序的升级法
  8.  */
  9. public class ShellSort {
  10.     public static void main(String[] args) {
  12.     }
  15.     //交换法 效率很低
  16.     public static void sortExchange(int[] arr) {
  17.         int count = 0;
  18.         for (int gap = arr.length / 2; gap > 0; gap /= 2) {
  19.             for (int i = gap; i < arr.length; i++) {
  20.                 for (int j = i - gap; j >= 0; j -= gap) {
  21.                     if (arr[j] > arr[j + gap]) {
  22.                         int temp = arr[j];
  23.                         arr[j] = arr[j + gap];
  24.                         arr[j + gap] = temp;
  25.                     }
  26.                 }
  27.             }
  28. //            System.out.println(count+"次:"+Arrays.toString(arr));
  29.         }
  30.     }
  32.     //移动法 效率比较高,类似插入排序
  33.     public static void sortMove(int[] arr) {
  34.         //步长
  35.         int move = 3;
  36.         for (int gap = arr.length / move; gap > 0; gap /= move) {
  37.             for (int i = gap; i < arr.length; i++) {
  38.                 int insertIndex = i;
  39.                 int insertValue = arr[i];
  40.                 if (arr[insertIndex] < arr[insertIndex - gap]) {
  41.                     while (insertIndex - gap >= 0 && insertValue < arr[insertIndex - gap]) {
  42.                         arr[insertIndex] = arr[insertIndex - gap];
  43.                         insertIndex -= gap;
  44.                     }
  45.                     arr[insertIndex] = insertValue;
  46.                 }
  47.             }
  48.         }
  49.     }
  51.     public static void demo() {
  52.         int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
  53.         /**
  54.          * 第一次 5组 每组2个
  55.          * i=5 j=0
  56.          * i=6 j=1
  57.          * i=7 j=2
  58.          * i=8 j=3
  59.          * i=9 j=4
  60.          */
  61.         for (int i = 5; i < arr.length; i++) {
  62.             for (int j = i - 5; j >= 0; j -= 5) {
  63.                 if (arr[j] > arr[j + 5]) {
  64.                     int temp = arr[j];
  65.                     arr[j] = arr[j + 5];
  66.                     arr[j + 5] = temp;
  67.                 }
  68.             }
  69.         }
  70.         System.out.println(Arrays.toString(arr));
  71.         /**
  72.          * 第二次 2组,每组5个
  73.          * i=2 j=0
  74.          * i=3 j=1
  75.          * i=4 j=2,0
  76.          * i=5 j=3,1
  77.          * i=6 j=4,2,0
  78.          * i=7 j=5,3,1
  79.          * i=8 j=6,4,2,0
  80.          * i=9 j=7,5,3,1
  81.          */
  82.         for (int i = 2; i < arr.length; i++) {
  83.             for (int j = i - 2; j >= 0; j -= 2) {
  84.                 if (arr[j] > arr[j + 2]) {
  85.                     int temp = arr[j];
  86.                     arr[j] = arr[j + 2];
  87.                     arr[j + 2] = temp;
  88.                 }
  89.             }
  90.         }
  91.         System.out.println(Arrays.toString(arr));
  92.         /**
  93.          * 第三次1组,每组10个
  94.          * 1 0
  95.          * 2 1,0
  96.          * 3 2,1,0
  97.          * 4 3,2,1,0
  98.          * 5 4-0
  99.          * 6 5-0
  100.          * 7 6-0
  101.          * 8 7-0
  102.          * 9 8-0
  103.          */
  104.         for (int i = 1; i < arr.length; i++) {
  105.             for (int j = i - 1; j >= 0; j -= 1) {
  106.                 if (arr[j] > arr[j + 1]) {
  107.                     int temp = arr[j];
  108.                     arr[j] = arr[j + 1];
  109.                     arr[j + 1] = temp;
  110.                 }
  111.             }
  112.         }
  113.         System.out.println(Arrays.toString(arr));
  114.     }
  115. }

5.快速排序

思路和介绍

快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

算法第四版的描述

本节的主题是快速排序． 它可能是应用最广泛的排序算法了。
快速排序流行的原因是它实现简单、适合于各种不同的输人数据且在一般应用中比其他排序算法都要快得多。
快速排序引人注目的特点包括它是原地排序（只需要一个很小的辅助栈），且将长度为N的数组排序所需的时间和NlgN成正比。
我们巳经学习过的排序算法都无法将这两个优点结合起来。 另外． 快速排序的内循环比大多数排序算法都要短小． 这意味着它无论是在理论上还是在实际中都要更快。
它的主耍缺点是非常脆弱． 在实现时要非常小心才能避免低劣的性能。巳经有无数例子显示许多种错误都能致使它在实际中的性能只有平方级别。 幸好我们将会看到，由这些错误中学到的教训也大大改进了快速排序疗法． 使它的应用更加广泛。
韩老师讲的听不懂,去看小码哥的视频

示意图

代码

  1. package com.sgg.algorithm.sort;
  3. import com.sgg.algorithm.sort.util.CommonUtil;
  5. import java.util.Arrays;
  7. public class QuickSort {
  8.     public static void main(String[] args) {
  9.         int size = 10;
  10.         int[] arr = new int[size];
  11.         for (int i = 0; i < size; i++) {
  12.             arr[i] = (int) (Math.random() * size*10);
  13.         }
  14.         System.out.println("before" + Arrays.toString(arr));
  15.         sort(arr);
  16.         System.out.println("after" + Arrays.toString(arr));
  17.         System.out.println(CommonUtil.isSort(arr));
  18.     }
  20.     public static void sort(int[] arr) {
  21.         doSort(arr, 0, arr.length);
  22.     }
  24.     public static void doSort(int[] arr, int left, int right) {
  25.         if (right - left < 2) {
  26.             return;
  27.         }
  28.         int mid = pivotIndex(arr, left, right);
  29.         doSort(arr, left, mid);
  30.         doSort(arr, mid + 1, right);
  31.     }
  33.     private static int pivotIndex(int[] arr, int left, int right) {
  34.         int temp = arr[left];
  35.         right--;
  36.         while (left < right) {
  37.             while (left < right) {
  38.                 if (temp < arr[right]) {
  39.                     right--;
  40.                 } else {
  41.                     arr[left++] = arr[right];
  42.                     break;
  43.                 }
  44.             }
  45.             while (left < right) {
  46.                 if (temp > arr[left]) {
  47.                     left++;
  48.                 } else {
  49.                     arr[right--] = arr[left];
  50.                     break;
  51.                 }
  52.             }
  53.         }
  54.         arr[left] = temp;
  55.         return left;
  56.     }
  58. }

6.归并排序

介绍和思路

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略
分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之。
image.png

代码

  1. package com.sgg.algorithm.sort;
  3. import java.util.Arrays;
  5. public class MergeSort {
  6.     public static void main(String[] args) {
  7.         int[] arr = { 8, 4, 5, 7, 1, 3, 6, 2 };
  8.         sort(arr);
  9.         System.out.println(Arrays.toString(arr));
  10.     }
  12.     public static void sort(int[] arr){
  13.         int[] temp =new int[arr.length];
  14.         mergeSort(arr,0,arr.length-1,temp);
  15.     }
  18.     /**
  19.      * 分合
  20.      */
  21.     public static void mergeSort(int[] arr, int left, int right, int[] temp) {
  22.         if (left < right) {
  23.             int mid = (left + right) / 2;
  24.             mergeSort(arr,left,mid,temp);
  25.             mergeSort(arr,mid+1,right,temp);
  26.             merge(arr,left,mid,right,temp);
  27.         }
  29.     }
  31.     /**
  32.      * 治理
  33.      */
  34.     public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
  35.         System.out.printf("left:%d,right:%d \n",left,right);
  36.         int leftIndex = left;
  37.         int rightIndex = mid + 1;
  38.         int tempIndex=left;
  39.         while (leftIndex <= mid && rightIndex <= right) {
  40.             if (arr[leftIndex] <= arr[rightIndex]) {
  41.                 temp[tempIndex] = arr[leftIndex];
  42.                 tempIndex++;
  43.                 leftIndex++;
  44.             }else {
  45.                 temp[tempIndex] = arr[rightIndex];
  46.                 tempIndex++;
  47.                 rightIndex++;
  48.             }
  49.         }
  50.         while (leftIndex <= mid) {
  51.             temp[tempIndex] = arr[leftIndex];
  52.             tempIndex++;
  53.             leftIndex++;
  54.         }
  55.         while (rightIndex <= right) {
  56.             temp[tempIndex] = arr[rightIndex];
  57.             tempIndex++;
  58.             rightIndex++;
  59.         }
  60.         for (int i = left; i <= right; i++) {
  61.             arr[i] = temp[i];
  62.         }
  63.     }
  64. }

7.基数排序

思路和介绍

1)基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用
2)基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法
3)基数排序(Radix Sort)是桶排序的扩展
4)基数排序是1887年赫尔曼·何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。

将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
这样说明，比较难理解，下面我们看一个图文解释，理解基数排序的步骤

代码

  1. package com.sgg.algorithm.sort;
  3. import java.util.Arrays;
  5. public class RadixSort {
  6.     public static void main(String[] args) {
  7.         int[] arr = {53, 3, 542, 748, 14, 214};
  8.         sort(arr);
  9.         System.out.println(Arrays.toString(arr));
  11.     }
  13.     public static void sort(int[] arr) {
  14.         int max = arr[0];
  15.         for (int i = 1; i < arr.length - 1; i++) {
  16.             if (arr[i] > max) {
  17.                 max = arr[i];
  18.             }
  19.         }
  20.         int loopSize = (max + "").length();
  21.         int[][] bucket = new int[10][arr.length];
  22.         int[] counts = new int[10];
  24.         for (int loop = 0, y = 1; loop < loopSize; loop++, y *= 10) {
  25.             for (int j = 0; j < arr.length; j++) {
  26.                 int mo = arr[j] / y % 10;
  27.                 bucket[mo][counts[mo]] = arr[j];
  28.                 counts[mo]++;
  29.             }
  30.             int index = 0;
  31.             for (int i = 0; i < 10; i++) {
  32.                 if (bucket[i].length > 0) {
  33.                     for (int j = 0; j < counts[i]; j++) {
  34.                         arr[index] = bucket[i][j];
  35.                         index++;
  36.                     }
  37.                 }
  38.                 counts[i] = 0;
  39.             }
  40. //            System.out.println(Arrays.toString(arr));
  41.         }
  42.     }
  44.     public static void demo(int[] arr) {
  45.         int[][] bucket = new int[10][arr.length];
  46.         int[] counts = new int[10];
  47.         //1
  48.         for (int j = 0; j < arr.length; j++) {
  49.             int mo = arr[j] % 10;
  50.             bucket[mo][counts[mo]] = arr[j];
  51.             counts[mo]++;
  52.         }
  53.         int index = 0;
  54.         for (int j = 0; j < 10; j++) {
  55.             if (bucket[j].length > 0) {
  56.                 for (int k = 0; k < counts[k]; k++) {
  57.                     arr[index] = bucket[k][k];
  58.                     index++;
  59.                 }
  60.             }
  61.             counts[j] = 0;
  62.         }
  63.         //2
  64.         for (int j = 0; j < arr.length; j++) {
  65.             int mo = arr[j] / 10 % 10;
  66.             bucket[mo][counts[mo]] = arr[j];
  67.             counts[mo]++;
  68.         }
  69.         index = 0;
  70.         for (int i = 0; i < 10; i++) {
  71.             if (bucket[i].length > 0) {
  72.                 for (int j = 0; j < counts[i]; j++) {
  73.                     arr[index] = bucket[i][j];
  74.                     index++;
  75.                 }
  76.             }
  77.             counts[i] = 0;
  78.         }
  79.         //3
  80.         for (int j = 0; j < arr.length; j++) {
  81.             int mo = arr[j] / 100 % 10;
  82.             bucket[mo][counts[mo]] = arr[j];
  83.             counts[mo]++;
  84.         }
  85.         index = 0;
  86.         for (int i = 0; i < 10; i++) {
  87.             if (bucket[i].length > 0) {
  88.                 for (int j = 0; j < counts[i]; j++) {
  89.                     arr[index] = bucket[i][j];
  90.                     index++;
  91.                 }
  92.             }
  93.             counts[i] = 0;
  94.         }
  95.     }
  96. }

1)基数排序是对传统桶排序的扩展，速度很快.
2)基数排序是经典的空间换时间的方式，占用内存很大,当对海量数据排序时，容易造成OutOfMemoryError。
3)基数排序时稳定的。[注:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的]
4)有负数的数组，我们不用基数排序来进行排序,如果要支持负数，参考: https://code.i-harness.com/zh-CN/q/e98fa9

10.总结

image.png

1)稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
2)不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
3)内排序：所有排序操作都在内存中完成；
4)外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
5)时间复杂度： 一个算法执行所耗费的时间。
6)空间复杂度：运行完一个程序所需内存的大小。
7)n:数据规模
8)k:“桶”的个数
9)In-place:不占用额外内存
10) Out-place:占用额外内存