八大排序对比及实现

一、排序算法总览

稳定性：相等元素排序后相对顺序不变内部排序：全部在内存中完成（本文 8 种都是）

二、八大排序完整代码（直接复制运行）

1. 冒泡排序（Bubble Sort）

思想

重复遍历数组，两两比较，大的往后冒，每轮确定一个最大值。

public static void bubbleSort(int[] arr) { int n = arr.length; // 外层循环：控制轮数 for (int i = 0; i < n - 1; i++) { boolean flag = false; // 优化：没有交换则提前结束 // 内层循环：比较交换 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; flag = true; } } if (!flag) break; } }

2. 选择排序（Selection Sort）

思想

每一轮找到最小值，放到已排序区间末尾。

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[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } }

3. 插入排序（Insertion Sort）

思想

像摸扑克牌，把当前数字插入前面已经排好序的序列

public static void insertionSort(int[] arr) { int n = arr.length; for (int i = 1; i < n; i++) { int current = arr[i]; int j = i - 1; // 移动元素 while (j >= 0 && arr[j] > current) { arr[j + 1] = arr[j]; j--; } // 插入 arr[j + 1] = current; } }

4. 希尔排序（Shell Sort）

思想

分组插入排序，逐步缩小增量，最后变成插入排序。

public static void shellSort(int[] arr) { int n = arr.length; int gap = n / 2; while (gap > 0) { for (int i = gap; i < n; i++) { int temp = arr[i]; int j = i - gap; while (j >= 0 && arr[j] > temp) { arr[j + gap] = arr[j]; j -= gap; } arr[j + gap] = temp; } gap /= 2; } }

5. 归并排序（Merge Sort）

思想

分治法：先拆分，再合并。

public static void mergeSort(int[] arr) { if (arr.length > 1) { int mid = arr.length / 2; int[] left = Arrays.copyOfRange(arr, 0, mid); int[] right = Arrays.copyOfRange(arr, mid, arr.length); mergeSort(left); mergeSort(right); merge(arr, left, right); } } private static void merge(int[] arr, int[] left, int[] right) { int i = 0, j = 0, k = 0; while (i < left.length && j < right.length) { if (left[i] < right[j]) arr[k++] = left[i++]; else arr[k++] = right[j++]; } while (i < left.length) arr[k++] = left[i++]; while (j < right.length) arr[k++] = right[j++]; }

6. 快速排序（Quick Sort）【面试必考】

思想

选基准值，小的放左，大的放右，递归。

public static void quickSort(int[] arr) { quickSort(arr, 0, arr.length - 1); } private static void quickSort(int[] arr, int left, int right) { if (left >= right) return; int pivot = partition(arr, left, right); quickSort(arr, left, pivot - 1); quickSort(arr, pivot + 1, right); } private static int partition(int[] arr, int left, int right) { int pivot = arr[right]; int i = left - 1; 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; }

7. 堆排序（Heap Sort）

思想

构建大顶堆，每次把堆顶放到末尾，再调整堆。

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); } }

8. 基数排序（Radix Sort）

思想

按位排序，从低位到高位，用桶存放。

public static void radixSort(int[] arr) { int max = Arrays.stream(arr).max().getAsInt(); for (int exp = 1; max / exp > 0; exp *= 10) countSort(arr, exp); } private static void countSort(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 idx = (arr[i] / exp) % 10; output[count[idx] - 1] = arr[i]; count[idx]--; } System.arraycopy(output, 0, arr, 0, n); }