目錄
1、冒泡排序
2、插入排序
3、選擇排序
4、為什麼很多排序工具使用插入排序而非冒泡排序？【性能】
排序是算法中比較常用的一大塊，很多的場景都需要進行排序操作，而排序選擇不當可能造成千、萬被的性能差距。是以按照時間複雜度将排序算法進行分類，隻是排序時間複雜度隻是衡量資料規模趨勢與耗時的關系，如果隻是基于時間複雜度進行考慮那麼時間複雜度高的基本就不會使用了。大O時間複雜度分析忽略了常數、系數、低階等，然而在資料量比較小的情況下，可能常數等的值比較大，耗時完全超過了遞增的趨勢值，是以一個優秀的排序工具在使用時候，會考慮各種情況下都能得到比較好的性能。後面專門對Java的排序算法進行分析。針對各種排序算法的圖形動态過程可以參見（整個排序過程比較直覺）：https://visualgo.net/zh/sorting
按照時間複雜度将排序進行分類：
O(N²)時間複雜度： 冒泡排序、插入排序、選擇排序
O(N*logN)時間複雜度：歸并排序、快速排序、插入排序的優化 二分插入排序和希爾排序
O(N)時間複雜度：桶排序、計數排排序、基數排序
其他排序：堆排序、猴子排序、面條排序、睡眠排序
排序不僅要考慮時間複雜度，還需要考慮空間使用率，我們将不需要額外的空間（空間複雜度為O (1) ）的排序稱為原地排序。三種O(N²)時間複雜度都不需要申請額外的容器，詳見下面的代碼，是以都是原地排序。排序時兩個元素排序字段的值相等，排序之後是否還能保住原來的順序稱為穩定排序。處理是否原地排序，是否穩定排序也是非常重要的衡量名額，比如我們已經有一部分訂單資料按照時間進行了排序，此時需要按照金額進行排序，如果是否非穩定排序後，則違背了我們已經按照訂單時間排好序的資料。
排序時非常頻繁的動作就是比對和換位，常用的換位方式有兩種：使用臨時變量記錄其中某個值，最後再指派回來；另一種排序方式是進行計算，前提是要計算方式不能丢失資料精度等。
// 基于計算的交換
public static void swap(int []arr, int a, int b) {
arr[a] = arr[a] + arr[b];
arr[b] = arr[a] - arr[b];
arr[a] = arr[a] - arr[b];
}
// 基于臨時變量的交換
public static void swap2(int[] arr, int a, int b) {
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
冒泡、插入、選擇排序的時間複雜度為O(N²)，就是因為其排序思路比較簡單都是直接采用兩層for循環。排序時具體的耗時與本身的有序度相關，三種排序方式的最好時間複雜度都是O(N),需要将所有資料周遊一遍，即資料是滿有序度。最壞情況就是兩層for循環全部執行完，最壞時間複雜度為O(N²)。
1、冒泡排序
冒泡排序思想就是将數組從頭到尾，相鄰兩個元素挨個比對或更換，最壞更換N輪的情況下整個數組就是有序的了。冒泡排序挨個比對替換，我們可以控制相同值的不用替換，是以冒泡排序是穩定排序。
冒泡排序優化：有時候後面的部分資料本身就是有序的，那麼則不需要周遊更新，則需要一個指針記錄每一輪沒有更新過資料的最後一位，下次排序到這裡就不用繼續了。
/**
* 冒泡排序
*
* 就是每次比較相鄰的兩個元素，如果不符合順序則進行交換，直到某次沒有交換過任何資料說明已經有序
* 最好時間複雜的是本身就有序，那麼也需要便利一遍即 O(n)
* 最壞時間複雜的就是兩層循環每次都跑完，那麼時間複雜度就是 O(N²)
*
* @author kevin
* @date 2021/2/21 23:28
* @since 1.0.0
*/
public class BubbleSort {
public static void main(String[] args) {
int[] array = new int[]{12, 34, -34, 454, 657, 33, 89, 67, 68, 99, -23, 34};
System.out.println("排序前：" + Arrays.toString(array));
// bubbleSort(array);
bubbleDownSort(array);
System.out.println("排序後：" + Arrays.toString(array));
}
/**
* 冒泡排序
* @param array 待排序的數組
*/
public static void bubbleSort(int[] array) {
if (array.length < 2) {
return;
}
for (int i = 0; i < array.length; i++) {
boolean isChanged = false;
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
isChanged = true;
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
}
}
// 如果上一輪沒有進行任何的資料交換，則說明已經有序直接退出
if (!isChanged) {
break;
}
}
}
/**
* 冒泡排序的改進方案
*
* 每次記錄最後一次進行位置交換的點，作為下次比較的邊界，節省了該部分的比較操作
*
* @param array 待排序的數組
*/
public static void bubbleSortOptimization(int[] array) {
if (array.length < 2) {
return;
}
// 記錄最後一次交換的點
int lastChangePoint = 0;
// 記錄無序數組的邊界，每次比較到該處即可，後面已經是有序的
int sortBoeder = array.length - 1;
for (int i = 0; i < array.length - 1; i++) {
boolean isChanged = false;
for (int j = 0; j < array.length - sortBoeder; j++) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1);
lastChangePoint = j;
isChanged = true;
}
}
sortBoeder = lastChangePoint;
// 如果上一輪沒有進行任何的資料交換，則說明已經有序直接退出
if (!isChanged) {
break;
}
}
}
/**
* 交換數組中 兩個下标位置的值
* @param array 待排序數組
* @param i 需要交換的下标 1
* @param k 需要交換的下标 2
*/
private static void swap(int[] array, int i, int k) {
int tmp = array[i];
array[i] = array[k];
array[k] = tmp;
}
/**
* 向下冒泡。可能比冒泡更易懂？
*
* 算法概要：
* 從0開始，用這個元素去跟後面的所有元素比較，如果發現這個元素大于後面的某個元素，則交換。
* 3 2 6 4 5 1
* 第一趟是從 index=0 也就是 3， 開始跟index=1及其後面的數字比較
* 3 大于 2，交換，變為 2 3 6 4 5 1，此時index=0的位置變為了2
* 接下來将用2跟index=2比較
* 2 不大于 6 不交換
* 2 不大于 4 不交換
* 2 不大于 5 不交換
* 2 大于 1，交換，變為 1 3 6 4 5 2，第一趟排序完成。
*
* 第二趟是從 index=1 也就是 3，開始跟index=2及其後面的數字比較
* 3 不大于 6 不交換
* 3 不大于 4 不交換
* 3 不大于 5 不交換
* 3 大于 2，交換，變為 1 2 6 4 5 3，第二趟排序完成。
*
* 第三趟是從 index=2 也就是 6，開始跟index=3及其後面的數字比較
* 6 大于 4，交換，變為 1 2 4 6 5 3, 此時 index = 2 的位置變為了4
* 接下來将用4跟index=4比較
* 4 不大于 5 不交換
* 4 大于 3，交換，變為 1 2 3 6 5 4，第三趟排序完成。
*
* 第四趟是從 index=3 也就是 6，開始跟index=4及其後面的數字比較
* 6 大于 5，交換，變為 1 2 3 5 6 4, 此時 index = 3 的位置變為了5
* 接下來将用5跟index=5比較
* 5 大于 4，交換，變為 1 2 3 4 6 5, 第四趟排序完成。
*
* 第五趟是從 index=4 也就是 6，開始跟index=5及其後面的數字比較
* 6 大于 5，交換，變為 1 2 3 4 5 6, 此時 index = 4 的位置變為了5
* 接下來将用5跟index=6比較
* index = 6 已經不滿足 index < length 的條件，整個排序完成。
*/
private static void bubbleDownSort(int[] arr) {
int len = arr.length;
if (len == 1) {
return;
}
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
if (arr[i] > arr[j]) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
}
}
}
2、插入排序
插入排序的思想就是每次輪訓都讓前N個元素有序，讓第N個元素插入合适的位置。插入排序可以控制插入時，在相同元素值的後面，是以插入排序也是穩定排序。
插入排序本身性能比較低，但是有很多基于插入思想的優化方式，二分插入排序、希爾排序。
public static void main(String[] args) {
int[] array = new int[]{12, 34, -34, 454, 657, 33, 89, 67, 68, 99, -23, 34};
System.out.println("排序前：" + Arrays.toString(array));
insertionSort(array);
System.out.println("排序後：" + Arrays.toString(array));
}
/**
* 插入排序
* @param array 待排序的數組
*/
public static void insertionSort(int[] array) {
if (array.length < 2) {
return;
}
for (int i = 0; i < array.length; i ++) {
int value = array[i];
int j = i - 1;
for ( ; j >= 0; j--) {
if (array[j] > value) {
array[j + 1] = array[j];
} else {
break;
}
}
array[j + 1] = value;
}
}
3、選擇排序
選擇排序的思想就是排序好之後每個下标位置上的值是固定的，那麼每次周遊擷取需要處理的下标記錄目前的最小值。其他每輪更小的值，已經排好序，後續不用處理。選擇排序是非穩定排序。
public class SelectionSort {
public static void main(String[] args) {
int[] array = new int[]{12, 34, -34, 454, 657, 33, 89, 67, 68, 99, -23, 34};
System.out.println("排序前：" + Arrays.toString(array));
selectionSort(array);
System.out.println("排序後：" + Arrays.toString(array));
}
/**
* 選擇排序，a表示數組，n表示數組大小
* @param a 待排序數組
*/
public static void selectionSort(int[] a) {
int n = a.length;
if (n <= 1) {
return;
}
for (int i = 0; i < n - 1; ++i) {
// 查找最小值
int minIndex = i;
for (int j = i + 1; j < n; ++j) {
if (a[j] < a[minIndex]) {
minIndex = j;
}
}
// 交換
int tmp = a[i];
a[i] = a[minIndex];
a[minIndex] = tmp;
}
}
}
4、為什麼很多排序工具使用插入排序而非冒泡排序？
由于選擇排序本身是非穩定排序，是以基本上都不會進行選擇。比如上面的訂單排序的例子，使用Java類庫提供的排序工具，結果排序完成後得到了非期待的結果。
排序動作影響性能一個因素就是比對和交換【比對和交換動作都需要CPU進行 讀取-計算-寫入操作】，即其他大環境（排序思想）确定的情況下，想要将排序性能做到極緻，就需要關注具體的細節。冒泡排序和插入排序雖然都是O(N²)的時間複雜度，但是由上面的代碼可知，不論待排序的數組的有序度如何，冒泡排序的交換次數是固定的。插入排序的交換次數與待排序數組的逆序度相關，也是固定值。但是基于上面的代碼，分析兩者的比對和交換操作：
冒泡排序中資料的交換操作：
if (a[j] > a[j+1]) { // 交換
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = true;
}
插入排序中資料的移動操作：
if (a[j] > value) {
a[j+1] = a[j]; // 資料移動
} else {
break;
}
有了上面的理論，自己對兩種排序方式進行測試
資料規模為1萬時，性能差距是9倍；
資料規模為十萬時，性能差距是20倍；
資料規模再增加量級時，由于耗時太長，我等不了，怕等到了天荒地老，是以就沒有對比資料了。。。
/**
* 插入排序 VS 冒泡排序
*
* 做不同量級的數組，相同的機器配置，執行 {@link InsertionSortVsBubbleSort#insertionSortVsBubbleSort()} ，執行結果為：
* arrayByInsertion length = 100000 排序花費時間為：765
* arrayByBubble length = 100000 排序花費時間為：14366
*
* arrayByInsertion length = 10000 排序花費時間為：17
* arrayByBubble length = 10000 排序花費時間為：155
*
* 冒泡排序 插入排序
* 一萬性能差【9】倍 155 17
* 十萬性能差【20】倍 765（或1017） 14366（或19166）
* 百萬耗時太長，我等不到結果
*
* @author kevin
* @date 2021/2/21 23:53
* @since 1.0.0
*/
public class InsertionSortVsBubbleSort {
public static void insertionSortVsBubbleSort() {
int dataLength = 10000;
int[] arrayByInsertion = new int[dataLength];
int[] arrayByBubble = new int[dataLength];
Random random = new Random();
for (int i = 0; i < dataLength; i++) {
int value = random.nextInt();
arrayByInsertion[i] = value;
arrayByBubble[i] = value;
}
long start = System.currentTimeMillis();
insertionSort(arrayByInsertion);
long end = System.currentTimeMillis();
long insertionTime = end - start;
BubbleSort.bubbleSort(arrayByBubble);
long end2 = System.currentTimeMillis();
long bubbleTime = end2 - end;
System.out.println("arrayByInsertion length = " + arrayByInsertion.length + " 排序花費時間為：" + insertionTime);
System.out.println("arrayByBubble length = " + arrayByBubble.length + " 排序花費時間為：" + bubbleTime);
}
}