一、排序基础概念
排序是将一串记录按照某个或某些关键字的大小，进行递增或递减排列的操作。理解排序前，有几个核心概念需要明确：
稳定性：若待排序序列中存在多个相同关键字的记录，排序后它们的相对位置保持不变，则称该算法稳定；否则不稳定。
内部排序：所有数据都在内存中完成。
外部排序：数据量过大无法全部装入内存，需借助外存（如磁盘）辅助完成的排序。
二、常见排序算法实现
2.1 插入排序
2.1.1 直接插入排序
基本思想很简单：将待排序元素逐个插入到已排好序的序列中。就像打扑克牌时整理手牌一样，每次拿起一张牌，插到合适的位置。
import java.util.Arrays;
public class InsertionSort {
/**
* 直接插入排序算法
* @param arr 待排序的数组
*/
public static void insertionSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
// 从第二个元素开始遍历（第一个元素默认已排序）
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
// 将大于 key 的元素向后移动一位
while (j >= 0 && key < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
// 将 key 插入到正确位置
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] testArr = {32, 26, 87, 72, 26, 17};
System.out.print("原始序列：" + Arrays.toString(testArr));
insertionSort(testArr);
System.out.println("\n排序后序列：" + Arrays.toString(testArr));
}
}
特性总结：
- 元素集合越接近有序，效率越高。
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)，稳定排序。
2.1.2 希尔排序
希尔排序是对直接插入排序的优化，又称缩小增量法。它先将整个待排记录序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录'基本有序'时，再对全体记录进行一次直接插入排序。
public class ShellSort {
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 temp = arr[i];
int j;
// 对间隔为 gap 的子序列进行直接插入排序
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
public static void main(String[] args) {
int[] arr = {12, 34, 54, 2, 26, 9, 17, 5};
System.out.print("原始数组：" + java.util.Arrays.toString(arr));
shellSort(arr);
System.out.println("\n排序后的数组：" + java.util.Arrays.toString(arr));
}
}
特性总结：
- 是插入排序的改进版，通过分组预排序让数组更接近有序。
- 时间复杂度取决于增量序列，通常优于 O(N^2)。
- 不稳定排序。
2.2 选择排序
2.2.1 直接选择排序
基本思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
public class SelectionSort {
public static void selectionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
// 在剩余元素中寻找最小值
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 交换找到的最小值与当前位置元素
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
public static void main(String[] args) {
int[] array = {35, 26, 18, 47, 52, 9, 13};
System.out.print("排序前：" + java.util.Arrays.toString(array));
selectionSort(array);
System.out.println("\n排序后：" + java.util.Arrays.toString(array));
}
}
特性总结：
- 逻辑简单，但效率一般，实际使用较少。
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 不稳定排序。
2.2.2 堆排序
堆排序利用堆这种数据结构设计，属于选择排序的一种。排升序建大堆，排降序建小堆。这里展示一种基于树结构的实现方式，便于理解堆的性质。
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
class TreeNode {
int value;
TreeNode left, right, parent;
public TreeNode(int value) {
this.value = value;
this.left = null;
this.right = null;
this.parent = null;
}
}
public class HeapSortWithTree {
private TreeNode root;
private int size;
private TreeNode lastNode;
public int[] sort(int[] array) {
if (array == null || array.length <= 1) {
return array;
}
buildMaxHeap(array);
int[] result = new int[array.length];
for (int i = array.length - 1; i >= 0; i--) {
result[i] = extractMax();
}
return result;
}
private void buildMaxHeap(int[] array) {
root = null; size = 0; lastNode = null;
for (int num : array) {
insert(num);
}
}
private void insert(int value) {
TreeNode newNode = new TreeNode(value);
size++;
if (root == null) {
root = newNode; lastNode = root;
return;
}
TreeNode parent = findInsertParent();
if (parent.left == null) parent.left = newNode;
else parent.right = newNode;
newNode.parent = parent;
lastNode = newNode;
bubbleUp(newNode);
}
private TreeNode findInsertParent() {
List<TreeNode> queue = new ArrayList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode current = queue.remove(0);
if (current.left == null || current.right == null) {
return current;
}
queue.add(current.left);
queue.add(current.right);
}
return null;
}
private void bubbleUp(TreeNode node) {
while (node.parent != null && node.value > node.parent.value) {
int temp = node.value;
node.value = node.parent.value;
node.parent.value = temp;
node = node.parent;
}
}
private void bubbleDown(TreeNode node) {
while (true) {
TreeNode largest = node;
if (node.left != null && node.left.value > largest.value) {
largest = node.left;
}
if (node.right != null && node.right.value > largest.value) {
largest = node.right;
}
if (largest == node) break;
int temp = node.value;
node.value = largest.value;
largest.value = temp;
node = largest;
}
}
private int extractMax() {
if (root == null) throw new IllegalStateException("堆为空");
int maxValue = root.value;
size--;
if (size == 0) {
root = null; lastNode = null;
return maxValue;
}
root.value = lastNode.value;
TreeNode newLastNode = findNewLastNode();
if (lastNode.parent != null) {
if (lastNode.parent.right == lastNode) lastNode.parent.right = null;
else lastNode.parent.left = null;
}
lastNode = newLastNode;
bubbleDown(root);
return maxValue;
}
private TreeNode findNewLastNode() {
if (size == 1) return root;
List<TreeNode> queue = new ArrayList<>();
queue.add(root);
TreeNode result = root;
for (int i = 0; i < size - 1; i++) {
TreeNode current = queue.remove(0);
result = current;
if (current.left != null) queue.add(current.left);
if (current.right != null) queue.add(current.right);
}
return result;
}
public static void main(String[] args) {
HeapSortWithTree heapSort = new HeapSortWithTree();
int[] array = {14, 10, 8, 7, 9, 3, 2, 4, 1};
System.out.print("排序前：" + java.util.Arrays.toString(array));
int[] sortedArray = heapSort.sort(array);
System.out.println("\n排序后：" + java.util.Arrays.toString(sortedArray));
}
}
特性总结：
- 利用堆结构选数，效率高。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(1)
- 不稳定排序。
2.3 交换排序
2.3.1 冒泡排序
通过重复走访要排序的数列，一次比较两个元素，如果顺序错误就交换过来。较大的元素会像气泡一样逐渐浮到末尾。
public class BubbleSort {
/**
* 优化版冒泡排序
* 添加标志位，当某轮未发生交换时说明数组已有序，可提前结束
*/
public static void bubbleSortOptimized(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
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[] testArr = {64, 34, 25, 12, 22, 11, 90};
System.out.print("排序前：" + java.util.Arrays.toString(testArr));
bubbleSortOptimized(testArr);
System.out.println("\n排序后：" + java.util.Arrays.toString(testArr));
}
}
特性总结：
- 易于理解，适合教学。
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定排序。
2.3.2 快速排序
快速排序是分治法的典型应用。任取基准值，将小于基准值的放左边，大于的放右边，然后递归处理左右子序列。
public class QuickSort {
public static void quickSort(int[] array, int left, int right) {
if (right - left <= 1) {
return;
}
int div = partition(array, left, right);
quickSort(array, left, div);
quickSort(array, div + 1, right);
}
// Hoare 分区法
private static int partition(int[] array, int left, int right) {
int i = left;
int j = right;
int pivot = array[left];
while (i < j) {
while (i < j && array[j] >= pivot) j--;
while (i < j && array[i] <= pivot) i++;
swap(array, i, j);
}
swap(array, i, left);
return i;
}
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String[] args) {
int[] array = {3, 2, 1, 5, 4};
System.out.print("排序前：" + java.util.Arrays.toString(array));
quickSort(array, 0, array.length);
System.out.println("\n排序后：" + java.util.Arrays.toString(array));
}
}
优化策略：
- 三数取中：避免基准值极端化导致性能下降。
- 小区间插入排序：当区间较小时，切换为插入排序效率更高。
- 非递归实现：使用栈模拟递归过程，防止栈溢出。
特性总结：
- 综合性能最好，实际应用广泛。
- 平均时间复杂度：O(N*logN)
- 最坏情况：O(N^2)
- 不稳定排序。
2.4 归并排序
归并排序采用分治法，将已有序的子序列合并，得到完全有序的序列。核心在于'分'与'治'。
public class MergeSort {
public static void mergeSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int[] temp = new int[arr.length];
sort(arr, 0, arr.length - 1, temp);
}
private static void sort(int[] arr, int left, int right, int[] temp) {
if (left < right) {
int mid = left + (right - left) / 2;
sort(arr, left, mid, temp);
sort(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 t = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[t++] = arr[i++];
} else {
temp[t++] = arr[j++];
}
}
while (i <= mid) temp[t++] = arr[i++];
while (j <= right) temp[t++] = arr[j++];
t = 0;
while (left <= right) arr[left++] = temp[t++];
}
public static void main(String[] args) {
int[] testArr = {12, 11, 13, 5, 6, 7};
System.out.print("排序前：" + java.util.Arrays.toString(testArr));
mergeSort(testArr);
System.out.println("\n排序后：" + java.util.Arrays.toString(testArr));
}
}
海量数据处理： 当数据量超过内存限制（如 100G 数据只有 1G 内存），外部排序成为必要。归并排序是最常用的外部排序方案：先将文件切分，内存排序后写回磁盘，最后进行多路归并。
特性总结：
- 缺点是需要 O(N) 的空间复杂度。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(N)
- 稳定排序。
三、排序算法复杂度及稳定性对比
| 排序方法 | 最好情况 | 平均情况 | 最坏情况 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | 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) | O(n^1.3) | O(n²) | O(1) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) ~ O(n) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
四、总结
排序是计算机科学中最基础也最重要的操作之一。不同的场景需要选择不同的算法：
- 小规模数据：插入排序往往表现不错，且稳定。
- 大规模随机数据：快速排序通常是首选，速度最快。
- 对稳定性有要求：归并排序或插入排序是更好的选择。
- 内存受限：堆排序和原地快速排序更合适。
掌握这些算法的核心思想与实现细节，能帮助你更好地应对实际开发中的性能挑战。