排序算法 Java

排序算法 Java 实现案例我给你整理了8 种经典排序算法的完整 Java 代码示例都基于同一个数组测试用例方便你对比学习。测试用例java运行public class SortDemo { public static void main(String[] args) { int[] arr {64, 34, 25, 12, 22, 11, 90}; System.out.println(排序前:); printArray(arr); // 选择下面任意一种排序算法调用 bubbleSort(arr); // selectionSort(arr); // insertionSort(arr); // shellSort(arr); // quickSort(arr, 0, arr.length - 1); // mergeSort(arr, 0, arr.length - 1); // radixSort(arr); // heapSort(arr); System.out.println(排序后:); printArray(arr); } // 打印数组 public static void printArray(int[] arr) { for (int num : arr) { System.out.print(num ); } System.out.println(); } }1. 冒泡排序 (Bubble Sort)java运行public static void bubbleSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { for (int j 0; j n - i - 1; j) { if (arr[j] arr[j 1]) { // 交换 int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; } } } }核心思想重复遍历数组比较相邻元素并交换把最大的元素 “冒泡” 到末尾。2. 简单选择排序 (Selection Sort)java运行public static void selectionSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (arr[j] arr[minIdx]) { minIdx j; } } // 交换最小值到当前位置 int temp arr[minIdx]; arr[minIdx] arr[i]; arr[i] temp; } }核心思想每次从未排序部分找到最小值放到已排序部分的末尾。3. 插入排序 (Insertion Sort)java运行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; // 将比key大的元素后移 while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } }核心思想将未排序元素逐个插入到已排序序列的合适位置。4. 希尔排序 (Shell Sort)java运行public static void shellSort(int[] arr) { int n arr.length; for (int gap n / 2; gap 0; gap / 2) { for (int i gap; i n; i) { int key arr[i]; int j i; while (j gap arr[j - gap] key) { arr[j] arr[j - gap]; j - gap; } arr[j] key; } } }核心思想分组插入排序逐步缩小分组间隔最后变成完整的插入排序。5. 快速排序 (Quick Sort)java运行public static void quickSort(int[] arr, int low, int high) { if (low high) { int pi partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi 1, high); } } private static int partition(int[] arr, int low, int high) { int pivot arr[high]; int i low - 1; for (int j low; j high; 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[high]; arr[high] temp; return i 1; }核心思想选一个基准把数组分成小于和大于基准的两部分递归排序。6. 归并排序 (Merge Sort)java运行public static void mergeSort(int[] arr, int left, int right) { if (left right) { int mid left (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); } } private static void merge(int[] arr, int left, int mid, int right) { int n1 mid - left 1; int n2 right - mid; int[] L new int[n1]; int[] R new int[n2]; System.arraycopy(arr, left, L, 0, n1); System.arraycopy(arr, mid 1, R, 0, n2); int i 0, j 0, k left; while (i n1 j n2) { if (L[i] R[j]) { arr[k] L[i]; } else { arr[k] R[j]; } k; } // 复制剩余元素 while (i n1) arr[k] L[i]; while (j n2) arr[k] R[j]; }核心思想分治法把数组拆成两半分别排序再合并两个有序数组。7. 基数排序 (Radix Sort)java运行public static void radixSort(int[] arr) { int max arr[0]; for (int num : arr) if (num max) max num; for (int exp 1; max / exp 0; exp * 10) { countingSortByExp(arr, exp); } } private static void countingSortByExp(int[] arr, int exp) { int n arr.length; int[] output new int[n]; int[] count new int[10]; for (int num : arr) count[(num / exp) % 10]; for (int i 1; i 10; i) count[i] count[i - 1]; for (int i n - 1; i 0; i--) { int digit (arr[i] / exp) % 10; output[count[digit] - 1] arr[i]; count[digit]--; } System.arraycopy(output, 0, arr, 0, n); }核心思想按位分组排序从低位到高位依次处理最终得到有序序列。8. 堆排序 (Heap Sort)java运行public static void heapSort(int[] arr) { int n arr.length; // 构建最大堆 for (int i n / 2 - 1; i 0; i--) heapify(arr, n, i); // 逐个提取堆顶元素 for (int i n - 1; i 0; i--) { int temp arr[0]; arr[0] arr[i]; arr[i] temp; heapify(arr, i, 0); } } private static void heapify(int[] arr, int n, int i) { int largest i; int left 2 * i 1; int right 2 * i 2; if (left n arr[left] arr[largest]) largest left; if (right n arr[right] arr[largest]) largest right; if (largest ! i) { int temp arr[i]; arr[i] arr[largest]; arr[largest] temp; heapify(arr, n, largest); } }核心思想构建最大堆将堆顶元素与末尾交换再调整堆结构重复直到有序。算法复杂度对比表格排序算法时间复杂度 (平均)时间复杂度 (最坏)时间复杂度 (最好)空间复杂度稳定性冒泡排序O(n²)O(n²)O(n)O(1)稳定简单选择排序O(n²)O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n²)O(n)O(1)稳定希尔排序O(n log n)O(n²)O(n)O(1)不稳定快速排序O(n log n)O(n²)O(n log n)O(log n)不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定基数排序O(n*k)O(n*k)O(n*k)O(n k)稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定