排序算法

排序是最基本的算法问题之一，理解各种排序算法的原理和特性对于算法学习至关重要。本章将详细介绍各类排序算法，从简单的冒泡排序到高效的快速排序，帮助你建立完整的排序算法知识体系。

排序算法分类

排序算法可以从多个维度进行分类，理解这些分类有助于选择合适的算法：

分类维度	类型	说明
比较方式	比较排序	通过比较元素决定相对顺序，时间复杂度下界 $O(n \log n)$
比较方式	非比较排序	不通过比较，利用元素特征排序，可以突破 $O(n \log n)$
稳定性	稳定排序	相等元素的相对位置保持不变
稳定性	不稳定排序	相等元素的相对位置可能改变
空间	原地排序	空间复杂度 $O(1)$ ，不需要额外空间
空间	非原地排序	需要额外的辅助空间

什么是稳定性？ 假设数组中有两个相等的元素 A 和 B，A 在 B 前面。稳定排序后，A 仍在 B 前面；不稳定排序可能会改变它们的相对顺序。稳定性在某些场景很重要，比如按多个字段排序时。

冒泡排序

冒泡排序是最容易理解的排序算法，通过相邻元素的比较和交换，将最大元素"冒泡"到末尾。

算法原理

冒泡排序的核心思想是：重复遍历数组，每次比较相邻的两个元素，如果顺序错误就交换。每一轮遍历后，最大的未排序元素会"冒泡"到正确位置。

想象气泡在水中上浮的过程：大的气泡（较大的元素）会逐渐上浮到水面（数组末尾）。

代码实现

public void bubbleSort(int[] arr) {
    int n = arr.length;
    
    // 外层循环控制遍历轮数
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;  // 优化：检测本轮是否发生交换
        
        // 内层循环进行相邻元素比较
        // 每轮结束后，最大的 i+1 个元素已经排好
        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^2)$	随机数据
最坏时间复杂度	$O(n^2)$	数组逆序
空间复杂度	$O(1)$	原地排序
稳定性	稳定	相等元素不交换

适用场景

冒泡排序虽然效率不高，但在以下场景可以考虑使用：

数据规模很小（如少于 50 个元素）
数据基本有序，只需要少量交换
教学演示，理解排序的基本概念

选择排序

选择排序的思想简单直观：每轮从未排序部分选择最小元素，放到已排序部分的末尾。

算法原理

选择排序将数组分为两部分：已排序部分（左边）和未排序部分（右边）。每轮从未排序部分找出最小元素，与未排序部分的第一个元素交换。

与冒泡排序的区别：冒泡排序通过不断交换相邻元素来移动数据，选择排序每轮只进行一次交换。

代码实现

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^2)$	无论输入如何，都需要 $n(n-1)/2$ 次比较
空间复杂度	$O(1)$	原地排序
稳定性	不稳定	交换可能改变相等元素的相对位置
交换次数	最多 $n-1$ 次	这是选择排序的优势

为什么不稳定？

考虑数组 [5, 5, 3]：

第一轮找到最小元素 3（索引 2），与索引 0 的 5 交换
结果是 [3, 5, 5]，两个 5 的相对位置改变了

适用场景

数据规模小
交换成本高（因为交换次数最少）
对稳定性没有要求

插入排序

插入排序模拟了整理扑克牌的过程：将未排序的元素插入到已排序部分的正确位置。

算法原理

插入排序同样将数组分为已排序和未排序两部分。每次从未排序部分取出第一个元素，从后向前扫描已排序部分，找到合适的位置插入。

插入排序的一个优点是：对于近乎有序的数据，效率非常高。

代码实现

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^2)$	随机数据
最坏时间复杂度	$O(n^2)$	数组逆序
空间复杂度	$O(1)$	原地排序
稳定性	稳定	相等元素不会交换

插入排序的优势

插入排序在某些场景下表现优异：

数据基本有序：时间接近 $O(n)$
数据规模小：常数因子小，实际运行可能比快速排序快
在线算法：可以边接收数据边排序

这也是为什么很多高级排序算法（如 Timsort）在小规模数据时使用插入排序。

希尔排序

希尔排序是插入排序的改进版本，通过分组进行插入排序，逐渐减小间隔，最终实现整体有序。

算法原理

希尔排序的核心思想是：先将整个数组分成若干子序列，分别进行插入排序；然后逐渐缩小间隔，继续分组排序；最后间隔为 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^2)$	取决于间隔序列的选择
空间复杂度	$O(1)$	原地排序
稳定性	不稳定	分组排序可能打乱相对位置

间隔序列的选择

间隔序列影响希尔排序的效率。常见的间隔序列：

序列名称	序列值	最坏时间复杂度
Shell 原始序列	$n/2, n/4, \ldots, 1$	$O(n^2)$
Hibbard 序列	$1, 3, 7, 15, \ldots, 2^k-1$	$O(n^{1.5})$
Sedgewick 序列	$1, 5, 19, 41, 109, \ldots$	$O(n^{1.3})$

归并排序

归并排序是分治思想的典型应用：将数组分成两半，分别排序后合并。

算法原理

归并排序采用分治策略：

分解：将数组分成两个子数组
解决：递归地对两个子数组进行归并排序
合并：将两个有序子数组合并成一个有序数组

归并排序的稳定性来自合并过程：当两个元素相等时，优先选择左边数组的元素。

代码实现

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)$	需要辅助数组
稳定性	稳定	合并时保持相等元素的顺序

归并排序的优势

时间复杂度稳定：无论输入如何，都是 $O(n \log n)$
适合链表排序：链表合并不需要额外空间
适合外部排序：可以处理无法全部装入内存的大数据

快速排序

快速排序是实践中最常用的高效排序算法，同样基于分治思想，但通过选择基准元素进行分区。

算法原理

快速排序的核心步骤：

选择基准：从数组中选择一个元素作为基准（pivot）
分区：将数组分为两部分，小于基准的在左边，大于基准的在右边
递归：对左右两部分递归进行快速排序

快速排序的平均性能很好，但最坏情况下会退化到 $O(n^2)$ 。

基本实现

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;  // lt: 小于pivot的边界, gt: 大于pivot的边界
    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--);  // 不增加i，因为交换过来的元素未检查
        } else {
            i++;
        }
    }
    
    // lt 到 gt 之间的元素都等于 pivot
    quickSort3Way(arr, low, lt - 1);
    quickSort3Way(arr, gt + 1, high);
}

算法分析

指标	值	说明
最好时间复杂度	$O(n \log n)$	每次分区都很平衡
平均时间复杂度	$O(n \log n)$	实践中效率很高
最坏时间复杂度	$O(n^2)$	数组已排序且基准选择不当
空间复杂度	$O(\log n)$	递归调用栈
稳定性	不稳定	分区过程可能改变相对位置

避免最坏情况

随机选择基准：随机选择 pivot 可以避免针对特定输入的退化
三数取中：选择首、中、尾三个元素的中位数作为基准
小数组切换插入排序：当数组较小时，插入排序更高效

堆排序

堆排序利用堆这种数据结构进行排序。堆是一个完全二叉树，满足堆序性质：每个节点的值都大于等于（大顶堆）或小于等于（小顶堆）其子节点的值。

算法原理

堆排序分为两个阶段：

建堆：将数组构建成一个大顶堆
排序：反复取出堆顶（最大值），放到数组末尾，然后调整堆

代码实现

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

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

算法分析

指标	值	说明
时间复杂度	$O(n \log n)$	稳定，建堆 $O(n)$ ，排序 $O(n \log n)$
空间复杂度	$O(1)$	原地排序
稳定性	不稳定	堆调整可能改变相等元素的相对位置

堆排序的特点

堆排序是一种很有特色的排序算法：

时间复杂度稳定，最坏情况也是 $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)$	$n$ 是元素个数， $k$ 是数据范围
空间复杂度	$O(n + k)$	需要计数数组和输出数组
稳定性	稳定	从后向前遍历保证稳定性

适用场景

计数排序的适用条件：

数据是整数或可以映射到整数
数据范围 $k$ 不是很大（如 $k = O(n)$ ）
对稳定性有要求

桶排序

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

算法原理

根据数据范围创建若干个桶
将元素分配到对应的桶中
对每个桶内的元素单独排序
将所有桶的元素合并

代码实现

import java.util.*;

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^2)$	所有元素都在一个桶中
空间复杂度	$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$ 是基数（通常为 10）
空间复杂度	$O(n + k)$	需要计数数组和输出数组
稳定性	稳定	使用稳定的计数排序作为子过程

适用场景

整数排序
字符串排序（按字典序）
数据位数不多

排序算法对比

时间复杂度对比

算法	最好	平均	最坏	空间	稳定性
冒泡排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
插入排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
希尔排序	$O(n \log n)$	$O(n^{1.3})$	$O(n^2)$	$O(1)$	不稳定
归并排序	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$	稳定
快速排序	$O(n \log n)$	$O(n \log n)$	$O(n^2)$	$O(\log n)$	不稳定
堆排序	$O(n \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 + k)$	$O(n + k)$	$O(n^2)$	$O(n + k)$	稳定
基数排序	$O(d(n + k))$	$O(d(n + k))$	$O(d(n + k))$	$O(n + k)$	稳定

选择建议

场景	推荐算法	原因
数据量小，基本有序	插入排序	时间接近 $O(n)$
数据量小，交换成本高	选择排序	交换次数最少
数据量大，内存排序	快速排序	平均性能最好
数据量大，需要稳定性	归并排序	稳定的 $O(n \log n)$
数据量大，空间受限	堆排序	原地排序，时间稳定
整数，范围不大	计数排序	线性时间复杂度
整数，位数不多	基数排序	线性时间复杂度

语言内置排序

现代编程语言都提供了高效的内置排序函数，它们通常采用混合算法。

Java 排序

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

// 对象：Timsort（归并排序和插入排序的混合）
Integer[] arr2 = {5, 2, 8, 1, 9};
Arrays.sort(arr2);

// 自定义比较器（降序）
Arrays.sort(arr2, (a, b) -> b - a);

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

Python 排序

# list.sort() 原地排序
arr = [5, 2, 8, 1, 9]
arr.sort()  # 原地排序
arr.sort(reverse=True)  # 降序

# sorted() 返回新列表
arr = [5, 2, 8, 1, 9]
new_arr = sorted(arr)  # 返回新列表

# 自定义排序
arr = ['apple', 'pie', 'a']
arr.sort(key=len)  # 按长度排序
arr.sort(key=lambda x: (len(x), x))  # 多条件排序

Timsort 算法

Timsort 是 Python 和 Java（对象排序）的默认排序算法，由 Tim Peters 在 2002 年为 Python 设计。

核心思想：Timsort 是归并排序和插入排序的混合算法：

将数组划分为若干"有序片段"（Run）
对每个 Run 使用插入排序（小规模效率高）
将多个 Run 合并（归并排序）

时间复杂度：

最好： $O(n)$ （数据已有序）
平均： $O(n \log n)$
最坏： $O(n \log n)$

优势：

对部分有序的数据非常高效
稳定排序
实际应用中性能优异

小结

本章我们系统学习了各类排序算法：

简单排序：冒泡、选择、插入——实现简单，适合小规模数据
高效排序：希尔、归并、快速、堆排序——时间复杂度 $O(n \log n)$
线性排序：计数、桶、基数——适用于特定场景
稳定性：选择排序算法的重要考量因素
内置排序：现代语言通常使用 Timsort 等混合算法

选择排序算法时，需要综合考虑数据规模、数据特征、空间限制和稳定性要求。

练习

实现各种排序算法并测试其正确性
LeetCode 912：排序数组
LeetCode 215：数组中的第 K 个最大元素
比较不同排序算法在不同数据规模下的性能
实现一个稳定的快速排序

排序算法分类​

冒泡排序​

算法原理​

代码实现​

算法分析​

适用场景​

选择排序​

算法原理​

代码实现​

算法分析​

为什么不稳定？​

适用场景​

插入排序​

算法原理​

代码实现​

算法分析​

插入排序的优势​

希尔排序​

算法原理​

代码实现​

算法分析​

间隔序列的选择​

归并排序​

算法原理​

代码实现​

算法分析​

归并排序的优势​

快速排序​

算法原理​

基本实现​

优化版本​

算法分析​

避免最坏情况​

堆排序​

算法原理​

代码实现​

算法分析​

堆排序的特点​

计数排序​

算法原理​

代码实现​

算法分析​

适用场景​

桶排序​

算法原理​

代码实现​

算法分析​

适用场景​

基数排序​

算法原理​

代码实现​

算法分析​

适用场景​

排序算法对比​

时间复杂度对比​

选择建议​

语言内置排序​

Java 排序​

Python 排序​

Timsort 算法​

小结​

练习​

排序算法分类

冒泡排序

算法原理

代码实现

算法分析

适用场景

选择排序

算法原理

代码实现

算法分析

为什么不稳定？

适用场景

插入排序

算法原理

代码实现

算法分析

插入排序的优势

希尔排序

算法原理

代码实现

算法分析

间隔序列的选择

归并排序

算法原理

代码实现

算法分析

归并排序的优势

快速排序

算法原理

基本实现

优化版本

算法分析

避免最坏情况

堆排序

算法原理

代码实现

算法分析

堆排序的特点

计数排序

算法原理

代码实现

算法分析

适用场景

桶排序

算法原理

代码实现

算法分析

适用场景

基数排序

算法原理

代码实现

算法分析

适用场景

排序算法对比

时间复杂度对比

选择建议

语言内置排序

Java 排序

Python 排序

Timsort 算法

小结

练习