跳到主要内容

排序算法

排序是最基本的算法问题之一，理解各种排序算法的原理和特性对于算法学习至关重要。

排序算法分类​

分类说明
比较排序通过比较元素决定相对顺序，时间复杂度下界 O(n log n)
非比较排序不通过比较，利用元素特征排序，可以突破 O(n log n)
稳定排序相等元素的相对位置不变
原地排序空间复杂度 O(1)

冒泡排序​

原理​

通过相邻元素的比较和交换，将最大元素"冒泡"到末尾。

public void bubbleSort(int[] arr) {
    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;
    }
}

分析：

  • 时间复杂度：最好 O(n)，平均 O(n²)，最坏 O(n²)
  • 空间复杂度：O(1)
  • 稳定性：稳定
  • 适用场景：小规模数据、基本有序的数据

选择排序​

原理​

每轮从未排序部分选择最小元素，放到已排序部分的末尾。

public 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;
            }
        }
        
        // 交换
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

分析：

  • 时间复杂度：O(n²)，无论输入如何
  • 空间复杂度：O(1)
  • 稳定性：不稳定（交换可能改变相等元素的相对位置）
  • 适用场景：小规模数据、交换成本高

插入排序​

原理​

将未排序元素插入到已排序部分的正确位置。

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

分析：

  • 时间复杂度：最好 O(n)，平均 O(n²)，最坏 O(n²)
  • 空间复杂度：O(1)
  • 稳定性：稳定
  • 适用场景：小规模数据、基本有序的数据、在线算法

优势：对于近乎有序的数据，插入排序非常高效。

希尔排序​

原理​

改进的插入排序，通过分组进行插入排序，逐渐减小间隔。

public 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 = i;
            
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            
            arr[j] = temp;
        }
    }
}

分析：

  • 时间复杂度：取决于间隔序列，平均 O(n^1.3) ~ O(n²)
  • 空间复杂度：O(1)
  • 稳定性：不稳定
  • 适用场景：中等规模数据

归并排序​

原理​

分治思想：将数组分成两半，分别排序后合并。

public void mergeSort(int[] arr) {
    if (arr.length <= 1) return;
    
    int[] temp = new int[arr.length];
    mergeSort(arr, 0, arr.length - 1, temp);
}

private void mergeSort(int[] arr, int left, int right, int[] temp) {
    if (left >= right) return;
    
    int mid = left + (right - left) / 2;
    
    // 递归排序
    mergeSort(arr, left, mid, temp);
    mergeSort(arr, mid + 1, right, temp);
    
    // 合并
    merge(arr, left, mid, right, temp);
}

private void merge(int[] arr, int left, int mid, int right, int[] temp) {
    int i = left;      // 左半部分起始
    int j = mid + 1;   // 右半部分起始
    int k = 0;         // 临时数组索引
    
    // 合并两个有序数组
    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 (int m = 0; m < k; m++) {
        arr[left + m] = temp[m];
    }
}

分析：

  • 时间复杂度：O(n log n)，稳定
  • 空间复杂度：O(n)
  • 稳定性：稳定
  • 适用场景：大数据量、链表排序、外部排序

优势：时间复杂度稳定，适合链表排序。

快速排序​

原理​

分治思想：选择基准元素，将数组分为小于和大于基准的两部分。

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

private void quickSort(int[] arr, int low, int high) {
    if (low >= high) return;
    
    int pivotIndex = partition(arr, low, high);
    
    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, high);
}

// 分区操作
private 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++;
            swap(arr, i, j);
        }
    }
    
    swap(arr, i + 1, high);
    return i + 1;
}

private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

优化版本​

// 三数取中选择基准
private int medianOfThree(int[] arr, int low, int high) {
    int mid = low + (high - low) / 2;
    
    // 对三个元素排序
    if (arr[low] > arr[mid]) swap(arr, low, mid);
    if (arr[mid] > arr[high]) swap(arr, mid, high);
    if (arr[low] > arr[mid]) swap(arr, low, mid);
    
    return mid;
}

// 三路快排（处理重复元素）
private void quickSort3Way(int[] arr, int low, int high) {
    if (low >= high) return;
    
    int lt = low, gt = high;
    int i = low;
    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++;
        }
    }
    
    quickSort3Way(arr, low, lt - 1);
    quickSort3Way(arr, gt + 1, high);
}

分析：

  • 时间复杂度：平均 O(n log n)，最坏 O(n²)（已排序且基准选择不当）
  • 空间复杂度：O(log n)（递归栈）
  • 稳定性：不稳定
  • 适用场景：大数据量、内存排序

优势：平均性能好，原地排序。

堆排序​

原理​

利用堆的性质进行排序，先建大顶堆，然后逐个取出堆顶。

public 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 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) {
        swap(arr, i, largest);
        heapify(arr, n, largest);
    }
}

分析：

  • 时间复杂度：O(n log n)，稳定
  • 空间复杂度：O(1)
  • 稳定性：不稳定
  • 适用场景：大数据量、原地排序

优势：原地排序，时间复杂度稳定。

计数排序​

原理​

统计每个元素出现的次数，适用于整数且范围不大的情况。

public void countingSort(int[] arr) {
    if (arr.length == 0) return;
    
    // 找出范围
    int max = arr[0], min = arr[0];
    for (int num : arr) {
        max = Math.max(max, num);
        min = Math.min(min, num);
    }
    
    // 统计次数
    int[] count = new int[max - min + 1];
    for (int num : arr) {
        count[num - min]++;
    }
    
    // 累计次数（确定位置）
    for (int i = 1; i < count.length; i++) {
        count[i] += count[i - 1];
    }
    
    // 从后向前遍历，保证稳定性
    int[] output = new int[arr.length];
    for (int i = arr.length - 1; i >= 0; i--) {
        int index = count[arr[i] - min] - 1;
        output[index] = arr[i];
        count[arr[i] - min]--;
    }
    
    // 复制回原数组
    System.arraycopy(output, 0, arr, 0, arr.length);
}

分析：

  • 时间复杂度：O(n + k)，k 为数据范围
  • 空间复杂度：O(n + k)
  • 稳定性：稳定
  • 适用场景：整数、范围不大

桶排序​

原理​

将数据分到多个桶中，每个桶单独排序。

public void bucketSort(int[] arr) {
    if (arr.length == 0) return;
    
    int max = arr[0], min = arr[0];
    for (int num : arr) {
        max = Math.max(max, num);
        min = Math.min(min, num);
    }
    
    // 创建桶
    int bucketCount = (max - min) / arr.length + 1;
    List<List<Integer>> buckets = new ArrayList<>();
    for (int i = 0; i < bucketCount; i++) {
        buckets.add(new ArrayList<>());
    }
    
    // 分配到桶
    for (int num : arr) {
        int bucketIndex = (num - min) / arr.length;
        buckets.get(bucketIndex).add(num);
    }
    
    // 每个桶排序并合并
    int index = 0;
    for (List<Integer> bucket : buckets) {
        Collections.sort(bucket);
        for (int num : bucket) {
            arr[index++] = num;
        }
    }
}

分析：

  • 时间复杂度：平均 O(n + k)，最坏 O(n²)
  • 空间复杂度：O(n + k)
  • 稳定性：取决于桶内排序
  • 适用场景：均匀分布的数据

基数排序​

原理​

按位排序，从低位到高位逐位处理。

public void radixSort(int[] arr) {
    if (arr.length == 0) return;
    
    // 找出最大值，确定位数
    int max = arr[0];
    for (int num : arr) {
        max = Math.max(max, num);
    }
    
    // 按位进行计数排序
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSortByDigit(arr, exp);
    }
}

private void countingSortByDigit(int[] arr, int exp) {
    int[] output = new int[arr.length];
    int[] count = new int[10];  // 0-9
    
    // 统计当前位的出现次数
    for (int num : arr) {
        int digit = (num / exp) % 10;
        count[digit]++;
    }
    
    // 累计次数
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }
    
    // 从后向前遍历
    for (int i = arr.length - 1; i >= 0; i--) {
        int digit = (arr[i] / exp) % 10;
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }
    
    System.arraycopy(output, 0, arr, 0, arr.length);
}

分析：

  • 时间复杂度：O(d * (n + k))，d 为位数，k 为基数
  • 空间复杂度：O(n + k)
  • 稳定性：稳定
  • 适用场景：整数、字符串

排序算法对比​

算法平均时间最坏时间空间稳定性原地
冒泡排序O(n²)O(n²)O(1)稳定是
选择排序O(n²)O(n²)O(1)不稳定是
插入排序O(n²)O(n²)O(1)稳定是
希尔排序O(n^1.3)O(n²)O(1)不稳定是
归并排序O(n log n)O(n log n)O(n)稳定否
快速排序O(n log n)O(n²)O(log n)不稳定是
堆排序O(n log n)O(n log n)O(1)不稳定是
计数排序O(n + k)O(n + k)O(n + k)稳定否
桶排序O(n + k)O(n²)O(n + k)稳定否
基数排序O(d(n + k))O(d(n + k))O(n + k)稳定否

Java 内置排序​

// Arrays.sort() 基本类型使用双轴快速排序 (Dual-Pivot Quicksort)
int[] arr = {5, 2, 8, 1, 9};
Arrays.sort(arr);

// 对象使用 TimSort（归并排序的优化版本）
// TimSort 是 Python 和 Java 默认的对象排序算法，结合了归并排序和插入排序的优点。
Integer[] arr2 = {5, 2, 8, 1, 9};
Arrays.sort(arr2);

现代排序算法趋势​

  • Timsort：自适应，利用数据中的“有序片段”（Runs），对于部分有序的数据时间复杂度接近 O(n)O(n)。
  • Introsort (内省排序)：C++ 默认，快排+堆排+插排的混合，保证最坏情况 O(nlog⁡n)O(n \log n)。
  • PDQSort (Pattern-defeating Quicksort)：Go 默认，是对快排和插排的现代工业级优化。
// 自定义比较器
Arrays.sort(arr2, (a, b) -> b - a);  // 降序

// Collections.sort()
List<Integer> list = Arrays.asList(5, 2, 8, 1, 9);
Collections.sort(list);

小结​

本章我们学习了：

  1. 简单排序：冒泡、选择、插入
  2. 高效排序：希尔、归并、快速、堆排序
  3. 线性排序：计数、桶、基数
  4. 稳定性与原地性：选择合适算法的重要考量

练习​

  1. 实现各种排序算法并测试
  2. LeetCode 912：排序数组
  3. LeetCode 215：数组中的第 K 个最大元素
  4. 比较不同排序算法在不同数据规模下的性能