整合一些算法和动图#
冒泡排序#
冒泡排序（Bubble Sort）是一種簡單的排序算法，它重複地遍歷要排序的列表，依次比較相鄰的元素並交換它們的位置，如果它們的順序錯誤。這個過程會不斷重複，直到整個列表不再需要交換為止，最終得到一個有序的列表。
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
// 標記是否有交換，如果沒有交換則排序完成
boolean swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
// 比較相鄰元素，如果順序錯誤則交換
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// 如果沒有進行交換，說明已經排好序，提前退出循環
if (!swapped) {
break;
}
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
System.out.println("排序後的數組:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
選擇排序#
它的基本思想是每次從待排序的序列中選擇最小（或最大）的元素，將其放在序列的起始位置，依次進行，直到所有元素都被排序完成。javajavajavajavajava
public class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
// 假設當前元素是未排序部分的最小值
int minIndex = i;
// 查找剩余未排序部分的最小值
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 交換找到的最小值與當前元素
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11};
selectionSort(arr);
System.out.println("排序後的數組:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
插入排序#
將第一待排序序列第一個元素看做一個有序序列，把第二個元素到最後一個元素當成是未排序序列。
從頭到尾依次掃描未排序序列，將掃描到的每個元素插入有序序列的適當位置。（如果待插入的元素與有序序列中的某個元素相等，則將待插入元素插入到相等元素的後面。）
public class InsertionSort {
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i]; // 當前要插入的元素
int j = i - 1;
// 向前查找比當前元素大的元素，依次向後移動
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
// 找到合適的位置插入
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6};
insertionSort(arr);
System.out.println("排序後的數組:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
快速排序#
快速排序（QuickSort）是由東尼・霍爾（Tony Hoare）發展的一種高效排序算法。平均情況下，排序 n 個元素需要 Ο(nlogn) 次比較，而在最壞情況下，可能需要 Ο(n²) 次比較，但這種情況很少發生。事實上，快速排序通常比其他 Ο(nlogn) 算法更快，因為其內部循環可以在大多數硬件架構上高效實現。
快速排序通過分治法（Divide and Conquer）將一個序列（list）分為兩個子序列（sub-lists）來進行排序。作為分治思想在排序算法中的經典應用，快速排序本質上是在冒泡排序基礎上的遞歸分治法的擴展。
快速排序的最壞運行情況是 O (n²)，比如說順序數列的快排。但它的平攤期望時間是 O (nlogn)，且 O (nlogn) 記號中隱含的常數因子很小，比複雜度穩定等於 O (nlogn) 的歸併排序要小很多。所以，對絕大多數順序性較弱的隨機數列而言，快速排序總是優於歸併排序。
public class QuickSort {
// 主方法，用於測試
public static void main(String[] args) {
int[] array = {34, 7, 23, 32, 5, 62, 32, 7, 9};
quickSort(array, 0, array.length - 1);
System.out.println("排序後的數組：");
for (int num : array) {
System.out.print(num + " ");
}
}
// 快速排序的主方法
public static void quickSort(int[] array, int low, int high) {
if (low < high) {
int pivotIndex = partition(array, low, high);
quickSort(array, low, pivotIndex - 1); // 排序左半部分
quickSort(array, pivotIndex + 1, high); // 排序右半部分
}
}
// 分區方法，選擇一個基準點並進行分區
private static int partition(int[] array, int low, int high) {
int pivot = array[high]; // 選擇最右邊的元素作為基準點
int i = low - 1; // i 是小於基準點的區域的索引
for (int j = low; j < high; j++) {
if (array[j] < pivot) {
i++;
swap(array, i, j); // 交換小於基準點的元素到左邊
}
}
swap(array, i + 1, high); // 將基準點放到正確的位置
return i + 1; // 返回基準點的位置
}
// 交換數組中的兩個元素
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
希爾排序#
希爾排序（Shell Sort），又稱遞減增量排序算法，是插入排序的一種高效改進版本，但它不是穩定排序算法。
希爾排序的改進主要基於插入排序的兩個關鍵特性：
- 插入排序對基本有序數據效率高：當數據幾乎已經排好序時，插入排序的效率可以接近線性。
- 插入排序的局限性：插入排序每次只能移動一個元素，這使得它在處理大規模無序數據時效率較低。
希爾排序的基本思想是：
- 分組排序：首先將待排序的序列分割成若干個較小的子序列，並對這些子序列進行插入排序。子序列的分組是通過遞減的增量（gap）來完成的。初始時，增量較大，隨著排序的進行，增量逐漸減小。
- 最終排序：當增量減小到 1 時，整個序列的記錄已經 “基本有序”，此時對全體記錄進行一次插入排序即可完成排序。
希爾排序的關鍵在於選擇合理的增量序列。不同的增量序列對排序的效率有很大的影響，常見的增量序列包括初期的增量為 n/2，後續的增量逐漸減少到 1。
public class ShellSort {
// 主方法，用於測試
public static void main(String[] args) {
int[] array = {34, 7, 23, 32, 5, 62, 32, 7, 9};
shellSort(array);
System.out.println("排序後的數組：");
for (int num : array) {
System.out.print(num + " ");
}
}
// 希爾排序方法
public static void shellSort(int[] array) {
int n = array.length;
// 初始增量設置為數組長度的一半
for (int gap = n / 2; gap > 0; gap /= 2) {
// 對每個增量值進行插入排序
for (int i = gap; i < n; i++) {
int temp = array[i];
int j = i;
// 對當前元素進行插入排序
while (j >= gap && array[j - gap] > temp) {
array[j] = array[j - gap];
j -= gap;
}
array[j] = temp;
}
}
}
}
归并排序#
归并排序（Merge Sort）是一種基於分治法的有效排序算法。它的基本思想是將待排序的序列遞歸地分割成兩個子序列，直到每個子序列僅包含一個元素，然後將這些子序列逐步合併成一個有序序列。归并排序可以分為自上而下的遞歸實現和自下而上的迭代實現兩種方法。
public class MergeSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 對 arr 進行拷貝，不改變參數內容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
if (arr.length < 2) {
return arr;
}
int middle = (int) Math.floor(arr.length / 2);
int[] left = Arrays.copyOfRange(arr, 0, middle);
int[] right = Arrays.copyOfRange(arr, middle, arr.length);
return merge(sort(left), sort(right));
}
protected int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int i = 0;
while (left.length > 0 && right.length > 0) {
if (left[0] <= right[0]) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
} else {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
}
while (left.length > 0) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
}
while (right.length > 0) {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
return result;
}
}
堆排序#
堆排序（Heap Sort）是一種基於堆數據結構的有效排序算法。它利用堆的特性來實現排序，通常使用最大堆或最小堆來完成。堆排序的基本思想是將待排序的序列轉換為一個堆，然後逐步從堆中提取最大或最小值，並調整堆的結構，從而實現排序。
堆排序的基本步驟：#
-
構建堆：將待排序的數組構建成一個最大堆（或最小堆）。在最大堆中，每個父節點的值都不小於其子節點的值。在最小堆中，每個父節點的值都不大於其子節點的值。
-
排序：
- 從堆中提取根節點（最大值或最小值），將其與堆的最後一個元素交換。
- 重新調整堆，使其重新滿足堆的性質。
- 重複以上步驟，直到堆為空。
public class HeapSort {
// 主方法，用於測試
public static void main(String[] args) {
int[] array = {34, 7, 23, 32, 5, 62, 32, 7, 9};
heapSort(array);
System.out.println("排序後的數組：");
for (int num : array) {
System.out.print(num + " ");
}
}
// 堆排序方法
public static void heapSort(int[] array) {
int n = array.length;
// 構建最大堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(array, n, i);
}
// 從堆中提取元素
for (int i = n - 1; i > 0; i--) {
// 將根節點（最大值）交換到數組末尾
swap(array, 0, i);
// 重新調整堆
heapify(array, i, 0);
}
}
// 調整堆的方法，使以 i 為根的子樹滿足最大堆性質
private static void heapify(int[] array, int n, int i) {
int largest = i; // 初始化最大值為根節點
int left = 2 * i + 1; // 左子節點
int right = 2 * i + 2; // 右子節點
// 如果左子節點更大
if (left < n && array[left] > array[largest]) {
largest = left;
}
// 如果右子節點更大
if (right < n && array[right] > array[largest]) {
largest = right;
}
// 如果最大值不是根節點
if (largest != i) {
swap(array, i, largest);
// 递归调整子树
heapify(array, n, largest);
}
}
// 交換數組中的兩個元素
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
計數排序#
計數排序是一種線性時間複雜度的排序算法，適用於整數範圍有限的場景。它的基本思想是通過統計每個元素出現的次數來確定元素的位置，從而完成排序。以下是計數排序的基本步驟：
- 確定範圍：首先確定待排序元素的最大值和最小值。這個範圍將決定需要創建的計數數組的大小。
- 創建計數數組：根據元素的範圍創建一個計數數組。數組的索引表示待排序元素的值，數組的值表示該值出現的次數。
- 統計元素出現次數：遍歷原始數據，將每個元素對應的計數數組位置的值加一。
- 計算累積計數：對計數數組進行累積求和，以確定每個元素的最終位置。
- 生成排序結果：根據累積計數數組中的信息，將元素放入正確的位置，生成排序後的數組。
import java.util.Arrays;
public class CountingSort {
public static void countingSort(int[] array) {
if (array == null || array.length == 0) {
return;
}
// 找到數組中的最大值
int max = Arrays.stream(array).max().orElse(Integer.MAX_VALUE);
// 創建計數數組並初始化
int[] count = new int[max + 1];
// 統計每個元素出現的次數
for (int num : array) {
count[num]++;
}
// 將計數數組轉換為累積計數數組
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
// 根據累積計數數組生成排序後的結果
int[] sortedArray = new int[array.length];
for (int i = array.length - 1; i >= 0; i--) {
sortedArray[count[array[i]] - 1] = array[i];
count[array[i]]--;
}
// 將排序結果複製回原數組
System.arraycopy(sortedArray, 0, array, 0, array.length);
}
public static void main(String[] args) {
int[] array = {4, 2, 2, 8, 3, 3, 1};
System.out.println("原數組: " + Arrays.toString(array));
countingSort(array);
System.out.println("排序後: " + Arrays.toString(array));
}
}
桶排序#
桶排序（Bucket Sort）是一種基於分佈的排序算法，特別適用於輸入數據分佈均勻的情況。它將元素分到多個桶中，再對每個桶內的元素進行單獨排序，最後將所有桶內的元素按順序合併，從而完成排序。
桶排序的基本步驟#
- 創建桶：根據輸入數據的範圍和分佈情況，創建一定數量的桶。每個桶代表一個區間。
- 分配元素到桶：遍歷輸入數組，將每個元素根據其值放入相應的桶中。
- 對每個桶內的元素進行排序：選擇合適的排序算法（如插入排序或快速排序）對每個桶內的元素進行排序。
- 合併所有桶的排序結果：將每個桶中的元素按順序拼接起來，形成最終的有序數組。
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSort {
public static void bucketSort(float[] array) {
if (array == null || array.length == 0) {
return;
}
// 創建桶
int numberOfBuckets = array.length;
List<Float>[] buckets = new ArrayList[numberOfBuckets];
for (int i = 0; i < numberOfBuckets; i++) {
buckets[i] = new ArrayList<>();
}
// 將元素分配到桶中
for (float num : array) {
int bucketIndex = (int) (num * numberOfBuckets); // 確定桶的位置
buckets[bucketIndex].add(num);
}
// 對每個桶內的元素進行排序
for (List<Float> bucket : buckets) {
Collections.sort(bucket);
}
// 合併所有桶的排序結果
int index = 0;
for (List<Float> bucket : buckets) {
for (float num : bucket) {
array[index++] = num;
}
}
}
public static void main(String[] args) {
float[] array = {0.42f, 0.32f, 0.73f, 0.25f, 0.67f, 0.48f, 0.12f, 0.89f, 0.94f, 0.36f};
System.out.println("原數組: ");
for (float num : array) {
System.out.print(num + " ");
}
System.out.println();
bucketSort(array);
System.out.println("排序後: ");
for (float num : array) {
System.out.print(num + " ");
}
}
}
基數排序#
基數排序（Radix Sort）是一種非比較的整數排序算法，適用於對整數或特定長度的字符串進行排序。基數排序按位或按數字的位數進行排序，從最低有效位（LSD，Least Significant Digit）到最高有效位（MSD，Most Significant Digit）進行多輪排序，最終實現整個數組的有序排列。
基數排序的基本思想#
基數排序的核心思想是將待排序的數字按位（從低到高或從高到低）進行排序。由於基數排序依賴於對每一位的排序，通常會借助於穩定的排序算法（如計數排序或桶排序）來保證在每一輪排序後，相同位數的元素保持其相對順序。
基數排序的步驟#
- 確定最大值的位數：找到數組中最大元素的位數，這將決定排序的輪數。
- 從最低位開始排序：從最低位開始，對每一位上的數字進行排序。排序時可以使用穩定的排序算法，比如計數排序。
- 重複：依次對更高的每一位進行排序，直到最高位。
- 最終排序結果：完成所有位的排序後，數組就是有序的。
示例#
假設要對整數數組 [170, 45, 75, 90, 802, 24, 2, 66] 進行基數排序：
-
確定最大值的位數：最大值
802有 3 位，所以排序需要進行 3 輪。 -
第一輪（按個位排序）：
- 排序結果：
[170, 90, 802, 2, 24, 45, 75, 66]
- 排序結果：
-
第二輪（按十位排序）：
- 排序結果：
[802, 2, 24, 45, 66, 170, 75, 90]
- 排序結果：
-
第三輪（按百位排序）：
- 排序結果：
[2, 24, 45, 66, 75, 90, 170, 802]
- 排序結果：
import java.util.*;
public class RadixSortWithHashMap {
// 獲取數組中最大值，以確定排序的輪數
private static int getMax(int[] array) {
int max = array[0];
for (int num : array) {
if (num > max) {
max = num;
}
}
return max;
}
// 使用 HashMap 實現計數排序
private static void countingSortWithHashMap(int[] array, int exp) {
// HashMap 用於存儲每位的對應列表
Map<Integer, List<Integer>> countMap = new HashMap<>();
// 初始化 HashMap 的鍵值對（鍵為 0-9 的數字，值為對應的列表）
for (int i = 0; i < 10; i++) {
countMap.put(i, new ArrayList<>());
}
// 根據每一位的數字，將元素放入對應的 HashMap 列表中
for (int num : array) {
int digit = (num / exp) % 10;
countMap.get(digit).add(num);
}
// 將 HashMap 中的元素按鍵的順序（從 0 到 9）重新寫回數組
int index = 0;
for (int i = 0; i < 10; i++) {
for (int num : countMap.get(i)) {
array[index++] = num;
}
}
}
// 主基數排序函數
public static void radixSort(int[] array) {
// 找到最大數以確定輪數
int max = getMax(array);
// 從個位開始對每一位進行計數排序
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSortWithHashMap(array, exp);
}
}
public static void main(String[] args) {
int[] array = {170, 45, 75, 90, 802, 24, 2, 66};
System.out.println("原數組: " + Arrays.toString(array));
radixSort(array);
System.out.println("排序後: " + Arrays.toString(array));
}
}
此文由 Mix Space 同步更新至 xLog
原始鏈接為 https://me.liuyaowen.club/posts/default/20240821and3