java演演算法之排序演演算法大全
2023-10-12 18:01:47
①排序
所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。排序演演算法，就是如何使得記錄按照要求排列的方法。排序演演算法在很多領域得到相當地重視，尤其是在大量資料的處理方面。一個優秀的演演算法可以節省大量的資源。在各個領域中考慮到資料的各種限制和規範，要得到一個符合實際的優秀演演算法，得經過大量的推理和分析。
⓿ 複雜度
| 排序演演算法 | 平均時間 | 最差時間 | 穩定性 | 空間 | 備註 |
|---|---|---|---|---|---|
| 氣泡排序 | O(n2) | O(n2) | 穩定 | O(1) | n較小時好 |
| 選擇排序 | O(n2) | O(n2) | 不穩定 | O(1) | n較小時好 |
| 插入排序 | O(n2) | O(n2) | 穩定 | O(1) | 大部分已有序時好 |
| 希爾排序 | O(nlogn) | O(ns)(1<s<2) | 不穩定 | O(1) | s是所選分組 |
| 快速排序 | O(nlogn) | O(n2) | 不穩定 | O(logn) | n較大時好 |
| 歸併排序 | O(nlogn) | O(nlogn) | 穩定 | O(n)/O(1) | n較大時好 |
| 基數排序 | O(n*k) | O(n*k) | 穩定 | O(n) | n為資料個數，k為資料位數 |
| 堆排序 | O(nlogn) | O(nlogn) | 不穩定 | O(1) | n較大時好 |
| 桶排序 | O(n+k) | O(n2) | 穩定 | O(n+k) | |
| 計數排序 | O(n+k) | O(n+k) | 穩定 | O(k) |
❶氣泡排序
演演算法步驟
- 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
- 對每一對相鄰元素作同樣的工作。這步做完後，最後的元素會是最大的數。
- 針對所有的元素重複以上的步驟，除了最後一個。
- 持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數位需要比較。
- 一共進行了
陣列元素個數-1次大回圈，小回圈要比較的元素越來越少。 - 優化：如果在某次大回圈，發現沒有發生交換，則證明已經有序。
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {4, 5, 1, 6, 2};
int[] res = bubbleSort(arr);
System.out.println(Arrays.toString(res));
}
public static int[] bubbleSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
boolean flag = true; //定義一個標識，來記錄這趟大回圈是否發生了交換
for (int j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = false;
}
}
//如果這次迴圈沒發生交換，直接停止迴圈
if (flag){
break;
}
}
return arr;
}
}
❷選擇排序
演演算法步驟
- 遍歷整個陣列，找到最小（大）的元素，放到陣列的起始位置。
- 再遍歷剩下的陣列，找到剩下元素中的最小（大）元素，放到陣列的第二個位置。
- 重複以上步驟，直到排序完成。
- 一共需要遍歷
陣列元素個數-1次，當找到第二大（小）的元素時，可以停止。這時最後一個元素必是最大（小）元素。
public class SelectSort {
public static void main(String[] args) {
int[] arr = {3, 1, 6, 10, 2};
int[] res = selectSort(arr);
System.out.println(Arrays.toString(res));
}
public static int[] selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
for (int j = i + 1; j < arr.length; j++) {
if(arr[min] > arr[j]){
min = j;
}
}
// 將找到的最小值和i位置所在的值進行交換
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
return arr;
}
}
❸插入排序
演演算法步驟
- 將待排序序列第一個元素看做一個有序序列，把第二個元素到最後一個元素當成是未排序序列。
- 從頭到尾依次掃描未排序序列，將掃描到的每個元素插入有序序列的適當位置。（如果待插入的元素與有序序列中的某個元素相等，則將待插入元素插入到相等元素的後面）
黑色代表有序序列，紅色代表待插入元素
public class InsertSort {
public static void main(String[] args) {
int[] arr = {3, 1, 6, 10, 2};
int[] res = insertSort(arr);
System.out.println(Arrays.toString(res));
}
public static int[] insertSort(int[] arr) {
//從陣列的第二個元素開始選擇合適的位置插入
for (int i = 1; i < arr.length; i++) {
//記錄要插入的資料,後面移動元素可能會覆蓋該位置上元素的值
int temp = arr[i];
//從已經排序的序列最右邊開始比較，找到比其小的數
//變數j用於遍歷前面的有序陣列
int j = i;
while (j > 0 && temp < arr[j - 1]) {
//如果有序陣列中的元素大於temp，則後移一個位置
arr[j] = arr[j - 1];
j--;
}
//j所指位置就是待插入的位置
if (j != i) {
arr[j] = temp;
}
}
return arr;
}
}
❹希爾排序
插入排序存在的問題
當最後一個元素為整個陣列的最小元素時，需要將前面的有序陣列中的每個元素都向後移一位，這樣是非常花時間的。所以有了希爾排序來幫我們將陣列從無序變為整體有序再變為有序。
演演算法步驟
- 選擇一個增量序列 t1（一般是陣列長度/2），t2（一般是一個分組長度/2），……，tk，其中 ti > tj, tk = 1；
- 按增量序列個數 k，對序列進行 k 趟排序；
- 每趟排序，根據對應的增量 ti，將待排序列分割成若干長度為 m 的子序列，分別對各子表進行直接插入排序。當增量因子為 1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。
public class ShellSort {
public static void main(String[] args) {
int[] arr = {3, 6, 1, 4, 5, 8, 2, 0};
int[] res = shellSort(arr);
System.out.println(Arrays.toString(res));
}
public static int[] shellSort(int[] arr) {
//將陣列分為gap組,每個組內部進行插入排序
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
//i用來指向未排序陣列的首個元素
for (int i = gap; i < arr.length; i++) {
int temp = arr[i];
int j = i;
while (j - gap >= 0 && temp < arr[j - gap]) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
return arr;
}
}
❺快速排序
演演算法步驟
- 先把陣列中的一個數當做基準數（pivot），一般會把陣列中最左邊的數當做基準數。
- 然後從兩邊進行檢索。
- 先從右邊檢索比基準數小的
- 再從左邊檢索比基準數大的
- 如果檢索到了，就停下，然後交換這兩個元素。然後再繼續檢索
- 直到兩邊指標重合時，把基準值和重合位置值交換
- 排序好後，該基準就處於數列的中間位置。這個稱為分割區（partition）操作；
- 然後遞迴地（recursive）把小於基準值的子陣列和大於基準值元素的子陣列再排序。
你注意最後形成的這棵二元樹是什麼？是一棵二元搜尋樹
你甚至可以這樣理解：快速排序的過程是一個構造二元搜尋樹的過程。
但談到二元搜尋樹的構造，那就不得不說二元搜尋樹不平衡的極端情況，極端情況下二元搜尋樹會退化成一個連結串列，導致操作效率大幅降低。為了避免出現這種極端情況，需要引入隨機性。
public class QuickSort {
public static void main(String[] args) {
int[] arr = {8, 12, 19, -1, 45, 0, 14, 4, 11};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr, int left, int right) {
//遞迴終止條件
if (left >= right) return;
//定義陣列第一個數為基準值
int pivot = arr[left];
//定義兩個哨兵
int i = left;
int j = right;
while (i != j) {
//從右往左找比基準值小的數，找到就停止，沒找到就繼續左移
while (pivot <= arr[j] && i < j) j--;
//從左往右找比基準值大的數，找到就停止，沒找到就繼續右移
while (pivot >= arr[i] && i < j) i++;
//兩邊都找到就交換它們
if (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
//此時，i和j相遇，把基準值和重合位置值交換
arr[left] = arr[i];
arr[i] = pivot;
quickSort(arr, left, i - 1);//對左邊的子陣列進行快速排序
quickSort(arr, i + 1, right);//對右邊的子陣列進行快速排序
}
}
private static void sort(int[] nums, int left, int right) {
if (left >= right) {
return;
}
int p = partition(nums, left, right);
sort(nums, left, p - 1);
sort(nums, p + 1, right);
}
public static int partition(int[] arr, int left, int right) {
int pivot = arr[left];//定義基準值為陣列第一個數
int i = left;
int j = right;
while (i != j) {
//case1:從右往左找比基準值小的數，找到就停止，沒找到就繼續左移
while (pivot <= arr[j] && i < j) j--;
//case2:從左往右找比基準值大的數，找到就停止，沒找到就繼續右移
while (pivot >= arr[i] && i < j) i++;
//將找到的兩數交換位置
if (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
arr[left] = arr[i];
arr[i] = pivot;//把基準值放到合適的位置
return i;
}
參考：快速排序法（詳解）
❻歸併排序
歸併排序（Merge sort）是建立在歸併操作上的一種有效的排序演演算法。該演演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。
演演算法步驟
- 申請空間，該空間用來存放合併後的序列；
- 設定兩個指標，最初位置分別為兩個已經排序序列的起始位置；
- 比較兩個指標所指向的元素，選擇相對小的元素放入到合併空間，並移動指標到下一位置；
- 重複步驟 3 直到某一指標達到序列尾；
- 將序列剩下的所有元素直接複製到合併序列尾。
分治法
治理階段
 |
 |
|---|---|
public class MergeSort {
public static void main(String[] args) {
int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
int[] tmp = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, tmp);
System.out.println(Arrays.toString(arr));
}
//分+治
public static void mergeSort(int[] arr, int left, int right, int[] tmp) {
if(left >= right){
return ;
}
int mid = (left + right) / 2;//中間索引
//向左遞迴進行分解
mergeSort(arr, left, mid, tmp);
//向右遞迴進行分解
mergeSort(arr, mid + 1, right, tmp);
//合併（治理）
merge(arr, left, right, tmp);
}
//治理階段（合併）
public static void merge(int[] arr, int left, int right, int[] tmp) {
int mid = (left + right) / 2;
int i = left; // 初始化i, 左邊有序序列的初始索引
int j = mid + 1; //初始化j, 右邊有序序列的初始索引
int t = 0; // 指向temp陣列的當前索引
//(一)
//先把左右兩邊(有序)的資料按照規則填充到temp陣列
//直到左右兩邊的有序序列，有一邊處理完畢為止
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
tmp[t++] = arr[i++];
} else {
tmp[t++] = arr[j++];
}
}
//(二)
//把有剩餘資料的一邊的資料依次全部填充到temp
while (i <= mid) {//左邊的有序序列還有剩餘的元素，就全部填充到temp
tmp[t++] = arr[i++];
}
while (j <= right) {
tmp[t++] = arr[j++];
}
//(三)
//將temp陣列的元素拷貝到arr
t = 0;
while (left <= right) {
arr[left++] = tmp[t++];
}
}
}
❼基數排序
基數排序是使用空間換時間的經典演演算法
演演算法步驟
- 將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零
- 事先準備10個陣列(10個桶)，對應位數的 0-9
- 根據每個數最低位值(個位)，將數放入到對應位置桶中，即進行一次排序
- 然後從 0-9 個陣列/桶，依次，按照加入元素的先後順序取出
- 以此類推，從最低位排序一直到最高位（個位->十位->百位->…->最高位），迴圈輪數為最大數位長度
- 排序完成以後, 數列就變成一個有序序列
- 需要我們獲得最大數的位數：可以通過將最大數變為String型別，再求得它的長度即可
| 排序過程 | 排序後結果 |
|---|---|
 |
|
 |
|
 |
public class RadixSort {
public static void main(String[] args) {
int[] arr = {53, 3, 542, 748, 14, 214};
radixSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void radixSort(int[] arr) {
//定義一個二維陣列，表示10個桶, 每個桶就是一個一維陣列
int[][] bucket = new int[10][arr.length];
//為了記錄每個桶中存放了多少個資料,我們定義一個陣列來記錄各個桶的每次放入的資料個數
//比如：bucketElementCounts[0] , 記錄的就是 bucket[0] 桶的放入資料個數
int[] bucketElementCounts = new int[10];
//最大位數
int maxLen = getMaxLen(arr);
for (int i = 0, n = 1; i < maxLen; i++, n *= 10) {
//maxLen輪排序
for (int j = 0; j < arr.length; j++) {
//取出每個元素的對應位的值
int digitOfElement = arr[j] / n % 10;
//放入到對應的桶中
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
bucketElementCounts[digitOfElement]++;
}
//按照桶的順序和加入元素的先後順序取出，放入原來陣列
int index = 0;
for (int k = 0; k < 10; k++) {
//如果桶中，有資料，我們才放入到原陣列
int position = 0;
while (bucketElementCounts[k] > 0) {
//取出元素放入到arr
arr[index++] = bucket[k][position++];
bucketElementCounts[k]--;
}
}
}
}
//得到該陣列中最大元素的位數
public static int getMaxLen(int[] arr) {
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
//將最大值轉為字串，它的長度就是它的位數
int maxLen = (max + "").length();
return maxLen;
}
}
❽堆排序
給定一個陣列：String[] arr = {「S」,」O」,」R」,」T」,」E」,」X」,」A」,」M」,」P」,」L」,」E」}請對陣列中的字元按從小到大排序。
實現步驟：
- 1.構造堆；
- 2.得到堆頂元素，這個值就是最大值；
- 3.交換堆頂元素和陣列中的最後一個元素，此時所有元素中的最大元素已經放到合適的位置；
- 4.對堆進行調整，重新讓除了最後一個元素的剩餘元素中的最大值放到堆頂；
- 5.重複2~4這個步驟，直到堆中剩一個元素為止。
public class HeapSort {
public static void main(String[] args) throws Exception {
String[] arr = {"S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"};
HeapSort.sort(arr);
System.out.println(Arrays.toString(arr));
}
//判斷heap堆中索引i處的元素是否小於索引j處的元素
private static boolean less(Comparable[] heap, int i, int j) {
return heap[i].compareTo(heap[j]) < 0;
}
//交換heap堆中i索引和j索引處的值
private static void exch(Comparable[] heap, int i, int j) {
Comparable tmp = heap[i];
heap[i] = heap[j];
heap[j] = tmp;
}
//根據原陣列source，構造出堆heap
private static void createHeap(Comparable[] source, Comparable[] heap) {
//把source中的元素拷貝到heap中，heap中的元素就形成一個無序的堆
System.arraycopy(source, 0, heap, 1, source.length);
//對堆中的元素做下沉調整(從長度的一半處開始，往索引1處掃描)
for (int i = (heap.length) / 2; i > 0; i--) {
sink(heap, i, heap.length - 1);
}
}
//對source陣列中的資料從小到大排序
public static void sort(Comparable[] source) {
//構建堆
Comparable[] heap = new Comparable[source.length + 1];
createHeap(source, heap);
//定義一個變數，記錄未排序的元素中最大的索引
int N = heap.length - 1;
//通過迴圈，交換1索引處的元素和排序的元素中最大的索引處的元素
while (N != 1) {
//交換元素
exch(heap, 1, N);
//排序交換後最大元素所在的索引，讓它不要參與堆的下沉調整
N--;
//需要對索引1處的元素進行對的下沉調整
sink(heap, 1, N);
}
//把heap中的資料複製到原陣列source中
System.arraycopy(heap, 1, source, 0, source.length);
}
//在heap堆中，對target處的元素做下沉，範圍是0~range
private static void sink(Comparable[] heap, int target, int range) {
while (2 * target <= range) {
//1.找出當前結點的較大的子結點
int max;
if (2 * target + 1 <= range) {
if (less(heap, 2 * target, 2 * target + 1)) {
max = 2 * target + 1;
} else {
max = 2 * target;
}
} else {
max = 2 * target;
}
//2.比較當前結點的值和較大子結點的值
if (!less(heap, target, max)) {
break;
}
exch(heap, target, max);
target = max;
}
}
}