互聯網面試，排序是經典問題，總結幾種經典排序代碼，方便後期查閱。
冒泡排序
對縱向排列的關鍵字序列，按照自下而上的掃描方向對兩兩相鄰的關鍵字進行比較，
若為逆序(k_j < k_j-1 )，則將兩個記錄交換位置；
重複上述掃描排序過程，直至沒有記錄需要交換為止。
public static void bubbleSort(int[] arr, int size) { boolean swap = false; for (int i = 0; i < size - 1; i++) { //最多進行 n-1 趟
swap = false; for (int j = size - 1; j > i; j--) { //從下往上掃描
if (arr[j] < arr[j - 1]) {
swap(arr, j, j - 1);
swap = true;
}
} if (!swap) { break; // 未發生交換，終止算法
}
}
}
冒泡排序的優化：
至多需要 n-1 趟掃描，如果在某趟掃描後，待排序記錄已是有序，可以在此趟掃描後終止。
可引入布爾量swap，每次掃描前值為false，若排序過程中發生了交換，置為true。
在一趟掃描後，如果swap仍為false，表示本次未曾交換記錄，可以終止算法。
交換函數
public static void swap(int[] arr, int one, int two) { int temp = arr[one];
arr[one] = arr[two];
arr[two] = temp;
}
快速排序
通過一趟排序將記錄序列分成兩個子序列，
再分別對這兩個子序列進行排序以達到整個序列有序。
// 排序範圍 [start, end], 包含 end public static void quickSort(int[] arr, int start, int end) { if (start < end) { int p = partition(arr, start, end);
quickSort(arr, start, p - 1);
quickSort(arr, p + 1, end);
}
}// 一次劃分代碼，返回被劃分後的基準位置public static int partition(int[] arr, int left, int right) { int pivot = arr[left]; while (left < right) { while (left < right && arr[right] >= pivot)
right--; if (left < right)
arr[left++] = arr[right]; while (left < right && arr[left] <= pivot)
left++; if (left < right)
arr[right--] = arr[left];
}
arr[left] = pivot; return left;
}
快速排序的優化：
基準的選擇影響快速排序的性能，最理想的情況是：選擇的基準恰好能把待排序序列分成兩個等長的子序列。
上文選擇基準是固定使用序列的第1個元素，改進思路是：使用左端、右端和中間位置上的三個元素的中位數作為基準。
非遞歸實現 快速排序
思路就是用棧模擬遞歸
public static void quickSort(int[] arr, int start, int end) { int[] stack = new int[end - start + 1]; // 數組模擬棧
int len = 0; stack[len++] = start; // 入棧
stack[len++] = end; while (len > 0) { // 棧中還有元素
int right = stack[--len]; // 注意是 --len
int left = stack[--len]; int p = partition(arr, left, right); if (p - 1 > left) { stack[len++] = left; stack[len++] = p - 1;
} if (p + 1 < right) { stack[len++] = p + 1; stack[len++] = right;
}
}
}
插入排序
把關鍵字k_i依次與有序區的關鍵字k_i-1、k_i-2、··· 、k_1比較
找到應該插入的位置，將k_i插入，後面的序列要往後移動
public static void insertSort(int[] arr, int size) { int temp = arr[0]; for (int i = 1; i < size; i++) { // 若 arr[i] 不小於有序區的最後一個元素，直接擴大有序區
if (arr[i] < arr[i - 1]) {
temp = arr[i]; int j = i - 1; while (j >= 0 && temp < arr[j]) {
arr[j + 1] = arr[j--];
}
arr[j + 1] = temp;
}
}
}
希爾排序
插入排序當 n 較小時效率較高；當一組記錄有序時，插入排序的算法複雜度可達到最優，即 O(n)。
希爾排序正是基於這兩點對插入排序進行改進的。
希爾排序的基本思想：設置 t 個整數增量：d_1、d_2、···、d_t，其中d_1 < n, d_t=1
以d_1為增量，將所有距離為d_1的記錄放到同一個組，可以得到d_1個組，在各組內進行直接插入排序；
然後取第二個增量d_2，重複上述的分組和排序，直至增量d_t=1
設置增量序列時，要使得增量值沒有除 1 之外的公因子，最後一個增量值必須為 1。
希爾排序的時間複雜度取決於增量序列的選取。
// shellSort(origins, origins.length, new int[] { 5, 3, 1 });public static void shellSort(int[] arr, int size, int[] d) { for (int k = 0; k < d.length; k++) { int gap = d[k]; for (int j = 0; j < gap; j++) { // 對於增量值 gap，一共 gap 組，0~gap-1
for (int i = j + gap; i < size; i++) { if (arr[i] < arr[i - gap]) { // 如果大於，不需要插入排序
int pivot = arr[i]; int t = i - gap; while (t >= 0 && pivot < arr[t]) {
arr[t + gap] = arr[t];
t = t - gap;
}
arr[t + gap] = pivot;
}
}
}
}
}
歸併排序
歸併的含義是：將兩個或兩個以上的有序表合併成一個新的有序表。
歸併排序的思路是：
假設初始表含有 n 個記錄，可看成是 n 個有序的子表，每個子表的長度為1，然後兩兩歸併，
得到 n/2 個長度為 2 的有序子表，再兩兩歸併，如此重複，直至得到長度為 n 的有序子表為止。
合併兩個有序表：
// 將arr[low]~arr[center]與arr[center+1]~arr[right]合併成有序表public static void merge(int[] arr, int left, int center, int right) { int[] result = new int[right - left + 1]; int i = left, j = center + 1, k = 0; while (i <= center && j <= right) { if (arr[i] < arr[j])
result[k++] = arr[i++]; else
result[k++] = arr[j++];
} while (i <= center)
result[k++] = arr[i++]; while (j <= right)
result[k++] = arr[j++];
System.arraycopy(result, 0, arr, left, right - left + 1);
}
一趟歸併：
假設長度為n的待排序序列中，每個有序表的長度為 step，歸併前共有n/step個子序列：
arr[0]~arr[step-1], arr[step]~arr[step*2-1], ··· ，一趟歸併將相鄰的一對有序表進行歸併。
需要考慮三種情況：
- 有序表的個數為偶數，且長度均為step
- 有序表的個數為偶數，但最後一個有序表的長度小於step
- 有序表的個數為奇數（輪空，不需要歸併）
// 子表的長度為 step，對數組進行一趟歸併public static void mergePass(int[] arr, int step) { int length = arr.length; int i = 0; // 循環，歸併長度為 step 的兩個有序表
for (; i + step * 2 - 1 < length; i += step * 2) {
merge(arr, i, i + step - 1, i + step * 2 - 1);
} if (i + step < length)
merge(arr, i, i + step - 1, length - 1); // 注意: 若 i + step >= length, 最後一個子表輪空，無需歸併}
歸併排序時，有序表的初始長度為1，每趟歸併後有序表長度增大一倍；
若干趟歸併後，有序表的長度>=n，排序結束。
public static void mergeSort(int[] arr, int size) { for (int i = 1; i < size; i *= 2) {
mergePass(arr, i);
}
}
直接選擇排序
算法思路：第一趟排序將待排序記錄 arr[0]~arr[n-1]作為無序區，從中找出最小的記錄並與無序區
第1個記錄arr[0]交換，此時得到有序區為arr[0]，無序區為arr[1]~arr[n-1]。
第二趟排序從arr[1]~arr[n-1]選出最小的記錄，與arr[1]交換。
重複上述過程…
public static void selectSort(int[] arr, int size) { for (int i = 0; i < size; i++) { int min = i; for (int j = i + 1; j < size; j++) { if (arr[j] < arr[min]) min = j;
} if (min != i)
swap(arr, min, i);
}
}
閱讀更多 java進階架構師 的文章
