以下是Java中幾種常見排序算法的實現，包括冒泡排序、選擇排序、插入排序、快速排序和歸并排序。

各排序算法特點說明：

1. 冒泡排序：

   • 原理：重復比較相鄰元素，將大的元素逐步"冒泡"到數組末尾
   • 特點：穩定排序，適合小規模數據，可優化（加入交換標記提前退出）
   • 空間復雜度：O(1)（原地排序）

2. 選擇排序：

   • 原理：每次從剩余元素中找到最小元素，放到已排序區間末尾
   • 特點：不穩定（可能改變相等元素的相對順序），交換次數少
   • 空間復雜度：O(1)（原地排序）

3. 插入排序：

   • 原理：將元素逐個插入到前面已排序的區間中合適的位置
   • 特點：穩定排序，對近乎有序的數據效率很高（接近O(n)）
   • 空間復雜度：O(1)（原地排序）

4. 快速排序：

   • 原理：通過分區操作將數組分為兩部分，遞歸排序子數組
   • 特點：實際應用中最快的排序算法之一，不穩定，最壞情況性能差
   • 空間復雜度：O(log n)（遞歸棧空間）

5. 歸并排序：

   • 原理：將數組分成兩半分別排序，再合并兩個有序子數組
   • 特點：穩定排序，性能穩定（始終O(n log n)），需要額外空間
   • 空間復雜度：O(n)（需要臨時數組）

import java.util.Arrays;public class SortingAlgorithms {// 1. 冒泡排序（穩定，O(n2)）public static void bubbleSort(int[] arr) {if (arr == null || arr.length <= 1) return;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;}}// 2. 選擇排序（不穩定，O(n2)）public static void selectionSort(int[] arr) {if (arr == null || arr.length <= 1) return;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[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}// 3. 插入排序（穩定，O(n2)，適合近乎有序的數據）public static void insertionSort(int[] arr) {if (arr == null || arr.length <= 1) return;int n = arr.length;// 從第二個元素開始，將其插入到前面的有序區間for (int i = 1; i < n; i++) {int key = arr[i]; // 當前要插入的元素int j = i - 1;// 移動有序區間中大于key的元素while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}// 將key插入到正確位置arr[j + 1] = key;}}// 4. 快速排序（不穩定，平均O(n log n)，最壞O(n2)）public static void quickSort(int[] arr) {if (arr == null || arr.length <= 1) return;quickSort(arr, 0, arr.length - 1);}private static void quickSort(int[] arr, int left, int right) {if (left < right) {// 分區操作，返回基準元素的正確位置int pivotIndex = partition(arr, left, right);// 遞歸排序基準元素左右兩側的子數組quickSort(arr, left, pivotIndex - 1);quickSort(arr, pivotIndex + 1, right);}}private static int partition(int[] arr, int left, int right) {int pivot = arr[right]; // 以最右側元素作為基準int i = left - 1; // i指向小于基準的元素的最后位置// 遍歷數組，將小于基準的元素放到左側for (int j = left; j < right; j++) {if (arr[j] <= pivot) {i++;// 交換元素int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 將基準元素放到正確位置int temp = arr[i + 1];arr[i + 1] = arr[right];arr[right] = temp;return i + 1; // 返回基準元素的索引}// 5. 歸并排序（穩定，O(n log n)，需要額外空間）public static void mergeSort(int[] arr) {if (arr == null || arr.length <= 1) return;mergeSort(arr, 0, arr.length - 1, new int[arr.length]);}private static void mergeSort(int[] arr, int left, int right, int[] temp) {if (left < right) {int mid = left + (right - left) / 2; // 避免溢出// 遞歸排序左右兩半mergeSort(arr, left, mid, temp);mergeSort(arr, mid + 1, right, temp);// 合并兩個有序子數組merge(arr, left, mid, right, temp);}}private static void merge(int[] arr, int left, int mid, int right, int[] temp) {int i = left; // 左子數組的起始索引int j = mid + 1; // 右子數組的起始索引int k = left; // 臨時數組的起始索引// 合并兩個子數組到臨時數組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++];}// 將臨時數組中的元素復制回原數組for (k = left; k <= right; k++) {arr[k] = temp[k];}}// 測試public static void main(String[] args) {int[] arr = {64, 34, 25, 12, 22, 11, 90};int[] copy;copy = Arrays.copyOf(arr, arr.length);bubbleSort(copy);System.out.println("冒泡排序: " + Arrays.toString(copy));copy = Arrays.copyOf(arr, arr.length);selectionSort(copy);System.out.println("選擇排序: " + Arrays.toString(copy));copy = Arrays.copyOf(arr, arr.length);insertionSort(copy);System.out.println("插入排序: " + Arrays.toString(copy));copy = Arrays.copyOf(arr, arr.length);quickSort(copy);System.out.println("快速排序: " + Arrays.toString(copy));copy = Arrays.copyOf(arr, arr.length);mergeSort(copy);System.out.println("歸并排序: " + Arrays.toString(copy));}
}