Java排序算法百科全书：原理、实现与实战指南

发布于：2025-04-18 ⋅ 阅读:(23) ⋅ 点赞:(0)

一、排序算法全景视图

1. 算法分类体系

graph TD
    A[排序算法] --> B[比较排序]
    A --> C[非比较排序]
    B --> B1[基本排序]
    B1 --> B11[冒泡排序]
    B1 --> B12[选择排序]
    B1 --> B13[插入排序]
    B --> B2[高效排序]
    B2 --> B21[快速排序]
    B2 --> B22[归并排序]
    B2 --> B23[堆排序]
    B2 --> B24[希尔排序]
    B --> B3[混合排序]
    B3 --> B31[TimSort]
    B3 --> B32[内省排序]
    C --> C1[计数排序]
    C --> C2[桶排序]
    C --> C3[基数排序]

2. 核心指标对比表

算法 平均时间复杂度 最差时间复杂度 空间复杂度 稳定性 最佳适用场景
冒泡排序 O(n²) O(n²) O(1) 稳定 教学演示/小数据集
快速排序 O(n log n) O(n²) O(log n) 不稳定 通用场景
归并排序 O(n log n) O(n log n) O(n) 稳定 大数据量/外部排序
堆排序 O(n log n) O(n log n) O(1) 不稳定 实时系统/内存敏感
希尔排序 O(n log²n) O(n²) O(1) 不稳定 中等规模数据
计数排序 O(n + k) O(n + k) O(k) 稳定 小范围整数
桶排序 O(n + k) O(n²) O(n + k) 稳定 均匀分布数据
基数排序 O(nk) O(nk) O(n + k) 稳定 多关键字排序
TimSort O(n log n) O(n log n) O(n) 稳定 Java对象排序

二、基础比较排序实现

1. 冒泡排序（Bubble Sort）

算法特点：简单直观，适合教学演示
优化技巧：提前终止标志位+记录最后交换位置

public static void optimizedBubbleSort(int[] arr) {
    int n = arr.length;
    int lastSwap = n - 1;
    
    for (int i = 0; i < n-1; i++) {
        boolean isSorted = true;
        int currentSwap = 0;
        
        for (int j = 0; j < lastSwap; j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr, j, j+1);
                isSorted = false;
                currentSwap = j;
            }
        }
        
        lastSwap = currentSwap;
        if (isSorted) break;
    }
}

2. 插入排序（Insertion Sort）

最佳场景：小数据集或基本有序数据
优化方案：二分查找插入位置

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int pos = binarySearch(arr, 0, i-1, key);
        
        System.arraycopy(arr, pos, arr, pos+1, i-pos);
        arr[pos] = key;
    }
}

private static int binarySearch(int[] arr, int low, int high, int key) {
    while (low <= high) {
        int mid = (low + high) >>> 1;
        if (arr[mid] < key) low = mid + 1;
        else high = mid - 1;
    }
    return low;
}

三、高效分治排序实现

1. 快速排序（Quick Sort）

核心优化：三数取中+三路划分+小数组切换

public static void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length-1);
}

private static void quickSort(int[] arr, int low, int high) {
    if (high - low < 47) { // 小数组优化
        insertionSort(arr, low, high);
        return;
    }
    
    // 三数取中法选择基准
    int m = medianOfThree(arr, low, (low+high)>>>1, high);
    swap(arr, low, m);
    
    // 三路划分
    int lt = low, gt = high, i = low+1;
    int pivot = arr[low];
    
    while (i <= gt) {
        if      (arr[i] < pivot) swap(arr, lt++, i++);
        else if (arr[i] > pivot) swap(arr, i, gt--);
        else              i++;
    }
    
    quickSort(arr, low, lt-1);
    quickSort(arr, gt+1, high);
}

2. 归并排序（Merge Sort）

迭代优化版：避免递归开销+内存复用

public static void mergeSort(int[] arr) {
    int n = arr.length;
    int[] temp = new int[n];
    
    for (int size = 1; size < n; size *= 2) {
        for (int left = 0; left < n; left += 2*size) {
            int mid = Math.min(left+size-1, n-1);
            int right = Math.min(left+2*size-1, n-1);
            merge(arr, temp, left, mid, right);
        }
    }
}

private static void merge(int[] arr, int[] temp, int left, int mid, int right) {
    System.arraycopy(arr, left, temp, left, right-left+1);
    
    int i = left, j = mid+1, k = left;
    while (i <= mid && j <= right) {
        arr[k++] = (temp[i] <= temp[j]) ? temp[i++] : temp[j++];
    }
    
    while (i <= mid) arr[k++] = temp[i++];
}

四、非比较排序实现

1. 计数排序（Counting Sort）

适用场景：数据范围小的整数排序
负数处理：偏移量调整

public static void countingSort(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();
    int min = Arrays.stream(arr).min().getAsInt();
    int range = max - min + 1;
    
    int[] count = new int[range];
    int[] output = new int[arr.length];
    
    for (int num : arr) count[num - min]++;
    for (int i = 1; i < range; i++) count[i] += count[i-1];
    
    for (int i = arr.length-1; i >= 0; i--) {
        output[count[arr[i]-min]-1] = arr[i];
        count[arr[i]-min]--;
    }
    
    System.arraycopy(output, 0, arr, 0, arr.length);
}

2. 基数排序（Radix Sort）

LSD实现：支持负数处理

public static void radixSort(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();
    int min = Arrays.stream(arr).min().getAsInt();
    max = Math.max(max, -min);
    
    for (int exp = 1; max/exp > 0; exp *= 10) {
        countingSortByDigit(arr, exp);
    }
}

private static void countingSortByDigit(int[] arr, int exp) {
    int n = arr.length;
    int[] output = new int[n];
    int[] count = new int[19]; // -9到9
    
    for (int num : arr) {
        int digit = (num / exp) % 10 + 9;
        count[digit]++;
    }
    
    for (int i = 1; i < 19; i++) count[i] += count[i-1];
    
    for (int i = n-1; i >= 0; i--) {
        int digit = (arr[i]/exp) % 10 + 9;
        output[--count[digit]] = arr[i];
    }
    
    System.arraycopy(output, 0, arr, 0, n);
}

五、高级混合排序

1. TimSort

核心特性：Java对象排序默认算法

// Java内置实现原理
static <T> void timSort(T[] a, Comparator<? super T> c) {
    int n = a.length;
    int minRun = minRunLength(n);
    
    // 1. 分割Run并扩展
    for (int i=0; i<n; i+=minRun) {
        int end = Math.min(i+minRun, n);
        binaryInsertionSort(a, i, end, c);
    }
    
    // 2. 合并相邻Run
    for (int size=minRun; size<n; size*=2) {
        for (int left=0; left<n; left+=2*size) {
            int mid = left + size;
            int right = Math.min(left+2*size, n);
            merge(a, left, mid, right, c);
        }
    }
}

2. 堆排序（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--) {
        swap(arr, 0, i);
        heapify(arr, i, 0);
    }
}

private static void heapify(int[] arr, int n, int i) {
    int largest = i;
    while (true) {
        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) break;
        
        swap(arr, i, largest);
        i = largest;
    }
}

六、排序算法选择指南

决策树

需要稳定排序？
├── 是 → 数据范围小？
│       ├── 是 → 计数排序（整数） / 桶排序（浮点）
│       └── 否 → 归并排序 / TimSort
└── 否 → 内存敏感？
           ├── 是 → 堆排序 / 原地快排
           └── 否 → 快速排序 / 内省排序

性能优化要点

  1. 数据特征分析：规模、分布、有序度

  2. 硬件特性利用：缓存优化、并行计算

  3. 混合策略：结合不同算法优势

  4. 预处理：检测有序子序列

七、实战应用场景

  1. 数据库索引：B+树的有序存储

  2. 实时计算：滑动窗口中位数计算

  3. 大数据处理：MapReduce排序阶段

  4. 图形渲染：深度缓冲排序优化

// 实时中位数计算示例
class MedianFinder {
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

    public void addNum(int num) {
        if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
            maxHeap.offer(num);
        } else {
            minHeap.offer(num);
        }
        
        // 平衡堆
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.offer(maxHeap.poll());
        } else if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }
    
    public double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        } else {
            return maxHeap.peek();
        }
    }
}

总结与扩展方向

核心原则

  1. 没有绝对最优：根据场景选择合适算法

  2. 理解数据特征：是优化排序性能的关键

  3. 混合策略：往往能获得最佳实践效果

进阶方向

  • 分布式排序：研究MapReduce的排序机制

  • GPU加速排序：利用并行计算特性

  • 机器学习排序：神经网络预测最优顺序

通过系统掌握各类排序算法的原理与Java实现，开发者能够根据具体场景选择最优解决方案，并具备定制化优化排序性能的能力。排序算法作为计算机科学的基石，其思想方法将持续影响未来技术的发展方向。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布