從數組中選擇最小元素，將它與數組的第一個元素交換位置。再從數組剩下的元素中選擇出最小的元素，將它與數組的第二個元素交換位置。不斷進行這樣的操作，直到將整個數組排序。

動態過程

算法原理參考：圖解選擇排序。

代碼實現

// 選擇排序public static void selectSort(int[] arr) { for (int i = 0; i < arr.length-1; i++) { int k = i; for (int j = i+1; j < arr.length; j++) { if (arr[j] < arr[k]) { k = j; } } if (k != i) { int temp = arr[i]; arr[i] = arr[k]; arr[k] = temp; } }}

---

1|2冒泡排序

算法思想

從左到右不斷交換相鄰逆序的元素，在一輪的循環之后，可以讓未排序的最大元素上浮到右側。在一輪循環中，如果沒有發生交換，那么說明數組已經是有序的，此時可以直接退出。

算法原理參考：圖解冒泡排序。

代碼實現

// 冒泡排序public static void bubbleSort(int[] arr) { // 設置每次冒泡的終止點 for (int i = arr.length-1; i > 0; i--) { boolean change = false; // 從起點開始冒泡 for (int j = 0; j < i; j++) { if (arr[j] > arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; if (change == false) { change = true; } } } // 如果本次無交換，則表示已有序，排序完成 if (!change) { return; } }}

---

1|3插入排序

算法思想

通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。每步將一個待排序的元素，按其排序碼大小插入到前面已經排好序的一組元素的適當位置上去，直到元素全部插入為止。

算法原理參考：圖解插入排序。

代碼實現

// 插入排序public static void insertionSort(int[] arr) { // 從第二個元素開始為它們找位置 for (int i = 1; i < arr.length; i++) { // 記住當前元素 int temp = arr[i]; int j; // 從當前元素左邊第一個元素開始，向左找位置 for (j = i-1; j >= 0 && arr[j] > temp; j--) { arr[j+1] = arr[j]; } // 找到合適位置后，將當前元素插入 arr[j+1] = temp; }}

---

1|4希爾排序

算法思想

又稱“分組插入排序”，先將整個待排元素序列分割成若干個子序列(由相隔某個“增量”的元素組成的)分別進行直接插入排序，然后依次縮減增量再進行排序，待整個序列中的元素基本有序(增量足夠小)時，再對全體元素進行一次直接插入排序。

算法原理參考：圖解希爾排序。

這個排序算法較難理解，建議讀者在本子上依照代碼的執行過程，把排序過程動手畫一遍，這應該是理解其本質最快的方法了。

代碼實現

// 希爾排序public static void shellSort(int[] arr) { // 增量控制，每次減半 for (int gap = arr.length/2; gap > 0; gap /= 2) { // 步長控制，從gap開始向后移動 for (int i = gap; i < arr.length; i++) { int temp = arr[i]; int j; // 起始指針控制，向左插入排序(找位置) for (j = i-gap; j >= 0 && arr[j] > temp; j -= gap) { arr[j+gap] = arr[j]; } arr[j+gap] = temp; } }}

---

1|5歸并排序

算法思想

該算法采用經典的分治(divide-and-conquer)策略，分：問題分成一些小的問題然后遞歸求解，治：將分的階段得到的各答案"修補"在一起，即分而治之。將序列遞歸拆半分成多個子序列，再將各個子序列排序后歸并疊加，最后歸并所有子序列，排序完成。

算法原理參考：圖解歸并排序。

代碼實現

// 歸并排序public static void mergeSort(int[] arr, int left, int right) { if (left < right) { int mid = (left + right) / 2; // 分 mergeSort(arr, left, mid); mergeSort(arr, mid+1, right); // 治 merge(arr, left, mid, right); }}public static void merge(int[] arr, int left, int mid, int right) { // 臨時數組 int[] temp = new int[right-left+1]; // 左、右指針 int i = left; int j = mid+1; int k = 0; // 將兩段數據按序寫入臨時數組 while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; }else { temp[k++] = arr[j++]; } } // 剩余數據寫入 while (i <= mid) { temp[k++] = arr[i++]; } while (j <= right) { temp[k++] = arr[j++]; } // 更新arr數組 k = 0; while (left <= right) { arr[left++] = temp[k++]; }}

---

1|6快速排序

算法思想

以第一個元素為基準，左右指針向中間移動掃描，小于基準元素的放到左邊，大于基準元素的放到右邊，最后將基準元素放到中間，這個位置也就是基準元素的合適位置。此時數據以基準元素為間隔，分為左右兩部分(不包括基準元素)，然后分別對左右兩部分數據分別執行此過程，直到數據不能再分，此時排序完成。

算法原理參考：圖解快速排序。

代碼實現

// 快速排序public static void quickSort(int[] arr, int left, int right) { if (left < right) { int index = getIndex(arr, left, right); quickSort(arr, left, index-1); quickSort(arr, index+1, right); }}public static int getIndex(int[] arr, int left, int right) { // 得到基準元素 int item = arr[left]; // 向中間移動，調整位置，找到基準元素的位置 while (left < right) { while (left < right && arr[right] >= item) { right--; } arr[left] = arr[right]; while (left < right && arr[left] <= item) { left++; } arr[right] = arr[left]; } // 放置基準元素 arr[left] = item; return left;}

---

1|7堆排序

算法思想

將待排序序列構造成一個大頂堆，此時，整個序列的最大值就是堆頂的根節點。將其與末尾元素進行交換，此時末尾就為最大值。然后將剩余n-1個元素重新構造成一個堆，這樣會得到n個元素的次小值。如此反復執行，便能得到一個有序序列了。

算法原理參考：圖解堆排序。

代碼實現

// 堆排序public static void heapSort(int[] arr) { // 1.構建大頂堆 for (int i = arr.length/2-1; i >= 0; i--) { adjust(arr, i, arr.length); } // 2.調整堆結構，交換頂元素與末尾元素 for (int j = arr.length-1 ; j > 0; j--) { int temp = arr[j]; arr[j] = arr[0]; arr[0] = temp; adjust(arr, 0, j); }}public static void adjust(int[] arr, int i, int length) { int temp = arr[i]; for (int k = 2*i+1; k < length; k = 2*k+1) { if (k+1 < length && arr[k+1] > arr[k]) { k++; } if (arr[k] > temp) { arr[i] = arr[k]; i = k; }else { break; } } arr[i] = temp;}

---

1|8計數排序

算法思想

計數排序要求輸入的數據必須是有確定范圍的整數。

找出待排序的數組中最大和最小的元素；統計數組中每個值為i的元素出現的次數，存入數組C的第i項；對所有的計數累加(從C中的第一個元素開始，每一項和前一項相加)；反向填充目標數組：將每個元素i放在新數組的第C(i)項，每放一個元素就將C(i)減去1。

算法原理參考：圖解計數排序。

代碼實現

// 計數排序public static int[] countSort(int[] src) { // 計算最大值與最小值 int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for(int i = 0; i < src.length; i++){ max = Math.max(max, src[i]); min = Math.min(min, src[i]); } // 數組中的數據范圍 int range = max - min + 1; // count[i]表示數組src中數據min + i的個數 int[] count = new int[range]; for (int value : src) { count[value - min]++; } // 累計變形，使得count[i]保存src中小于等于min + i的數據的個數 for (int i = 1; i < range; i++) { count[i] += count[i - 1]; } // 結果數組 int[] res = new int[src.length]; // 倒序遍歷原數組，保持排序的穩定性 for (int i = src.length - 1; i >= 0; i--) { // 獲取數據在count數組中的索引 int index = src[i] - min; // 個數減1 count[index]--; // 數據src[i]排序后的索引是count[index] res[count[index]] = src[i]; } return res;}

---

1|9桶排序

算法思想

桶排序是計數排序的擴展版本，計數排序可以看成每個桶只存儲相同元素，而桶排序每個桶存儲一定范圍的元素，通過映射函數，將待排序數組中的元素映射到各個對應的桶中，對每個桶中的元素進行排序，最后將非空桶中的元素逐個放入原序列中。

桶排序需要盡量保證元素分散均勻，否則當所有數據集中在同一個桶中時，桶排序失效。

算法原理參考：圖解桶排序。

代碼實現

// 桶排序public static void bucketSort(int[] arr){ // 計算最大值與最小值 int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for(int i = 0; i < arr.length; i++){ max = Math.max(max, arr[i]); min = Math.min(min, arr[i]); } // 計算桶的數量,并創建桶 int bucketNum = (max - min) / arr.length + 1; ArrayList> bucketArr = new ArrayList<>(bucketNum); for(int i = 0; i < bucketNum; i++){ bucketArr.add(new ArrayList()); } // 將每個元素放入桶 for(int i = 0; i < arr.length; i++){ int num = (arr[i] - min) / (arr.length); bucketArr.get(num).add(arr[i]); } // 對每個桶進行排序 for(int i = 0; i < bucketArr.size(); i++){ Collections.sort(bucketArr.get(i)); } // 將桶中的元素賦值到原序列 int index = 0; for(int i = 0; i < bucketArr.size(); i++){ for(int j = 0; j < bucketArr.get(i).size(); j++){ arr[index++] = bucketArr.get(i).get(j); } } }

---

1|10基數排序

算法思想

基數排序可以看成是桶排序的擴展，以整數排序為例，主要思想是將整數按位數劃分，準備 10 個桶，代表 0 - 9，根據整數個位數字的數值將元素放入對應的桶中，之后按照輸入賦值到原序列中，依次對十位、百位等進行同樣的操作，最終就完成了排序的操作。

　　算法原理參考：圖解基數排序。

代碼實現

public static void radixSort(int[] arr) { if (arr == null || arr.length < 2) { return; } radixSort(arr, 0, arr.length - 1, maxbits(arr));} // 計算最大位數public static int maxbits(int[] arr) { int max = Integer.MIN_VALUE; for (int i = 0; i < arr.length; i++) { max = Math.max(max, arr[i]); } int res = 0; while (max != 0) { res++; max /= 10; } return res;}// 基數排序public static void radixSort(int[] arr, int begin, int end, int digit) { final int radix = 10; int i = 0, j = 0; int[] count = new int[radix]; int[] bucket = new int[end - begin + 1]; // 依次遍歷每個位數 for (int d = 1; d <= digit; d++) { for (i = 0; i < radix; i++) { count[i] = 0; } // 統計數量 for (i = begin; i <= end; i++) { j = getDigit(arr[i], d); count[j]++; } // 計算位置 for (i = 1; i < radix; i++) { count[i] = count[i] + count[i - 1]; } // 記錄到對應位置 for (i = end; i >= begin; i--) { j = getDigit(arr[i], d); count[j]--; bucket[count[j]] = arr[i]; } for (i = begin, j = 0; i <= end; i++, j++) { arr[i] = bucket[j]; } }}// 獲取位數數值public static int getDigit(int x, int d) { return ((x / ((int) Math.pow(10, d - 1))) % 10);}

---

2|0排序算法梳理

2|1復雜度分析

2|2算法分類及適用場景

　　★ 選擇、冒泡、插入、希爾、歸并、快速、堆排序都是基于比較的排序。

　　　　? 平均時間復雜度最低O(nlogn)。

　　　　? 適用于所有可比較的對象。

　　★ 計數排序、桶排序、基數排序不是基于比較的排序。

　　　　? 使用空間換時間，某些時候，平均時間復雜度可以低于O(nlogn)。

　　　　? 適用于正整數的比較。

2|3穩定性分析

　　? 不穩定的排序算法有：快速排序、希爾排序、選擇排序、堆排序。

　　　　? 巧記：快『快速排序』、些『希爾排序』、選『選擇排序』、堆『堆排序』。

　　? 穩定的排序算法有：冒泡排序、插入排序、歸并排序、計數排序、桶排序、基數排序。

總結

以上是生活随笔為你收集整理的9个元素换6次达到排序序列_程序员必须掌握的：10大排序算法梳理已整理好的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。