Java十大排序算法知识点总结

一、排序算法概述排序算法是计算机科学中最基础、最重要的算法之一它负责将一组数据按照特定顺序升序或降序重新排列。在Java编程中掌握各种排序算法的原理、实现和适用场景对于提升编程能力和解决实际问题至关重要。本文将系统性地总结Java中八大经典排序算法包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序和基数排序。将从算法思想、Java实现、时间/空间复杂度、稳定性以及适用场景等多个维度进行详细分析。二、算法分类与对比在深入学习具体算法之前我们先从宏观上了解排序算法的分类和整体对比算法名称平均时间复杂度最坏时间复杂度空间复杂度稳定性适用场景冒泡排序O(n²)O(n²)O(1)稳定教学、小规模数据选择排序O(n²)O(n²)O(1)不稳定小规模数据、交换成本高插入排序O(n²)O(n²)O(1)稳定小规模或基本有序数据希尔排序O(n log n) ~ O(n²)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)不稳定大规模数据、通用排序堆排序O(n log n)O(n log n)O(1)不稳定大规模数据、需要原地排序计数排序O(n k)O(n k)O(k)稳定整数排序、数据范围小桶排序O(n k)O(n²)O(n k)稳定数据均匀分布、外部排序、数据范围已知且分布均匀基数排序O(d * (n k))O(d * (n k))O(n k)稳定整数排序、字符串排序按字符、数据位数固定或范围有限三、冒泡排序 (Bubble Sort)3.1 算法思想重复遍历待排序序列依次比较相邻元素如果顺序错误就交换它们。每轮遍历会将最大或最小的元素“冒泡”到正确位置。3.2 Java实现3.3 核心要点时间复杂度平均O(n²)最坏O(n²)最好O(n)优化后空间复杂度O(1)原地排序稳定性稳定相等元素不会交换适用场景教学演示、小规模数据排序四、选择排序 (Selection Sort)4.1 算法思想每次从未排序部分选择最小或最大元素放到已排序部分的末尾。步骤1.默认待排序数组的第一个是min2.寻找真正的min3.默认与真正的min交换。4.2 Java实现4.3 核心要点时间复杂度O(n²)无论数据是否有序空间复杂度O(1)原地排序稳定性不稳定交换可能改变相等元素的相对顺序适用场景数据量小且交换成本高的场景五、插入排序 (InsertSort)5.1 算法思想将待排序元素插入到已排序部分的适当位置类似于整理扑克牌。思想认为数组中第一个数值是已经排好序的数值定义游标从第二个数值开始不断地向后遍历遍历到的数据插入到前边排好序的数组当中。5.2 Java实现5.3 核心要点时间复杂度平均O(n²)最坏O(n²)最好O(n)已排序空间复杂度O(1)原地排序稳定性稳定适用场景小规模数据、基本有序数据、在线排序六、希尔排序 (Shell Sort)/缩小增量排序6.1 算法思想插入排序的改进版通过将原始列表分割成多个子序列进行插入排序逐渐减少增量直至为1。步骤1.将数组按照数组长度的一半为间隔进行分组2.将数组按照数组长度的一半的一半为间隔进行分组组内进行插入排序3.直到间隔为1整个数组为一组组内插入排序。6.2 Java实现6.3 核心要点时间复杂度取决于增量序列平均O(n log n) ~ O(n²)空间复杂度O(1)原地排序稳定性不稳定适用场景中等规模数据比简单插入排序效率更高七、归并排序 (Merge Sort)7.1 算法思想分治法的典型应用将数组递归地分成两半分别排序后再合并合并过程中借助临时空间进行排序。7.2 Java实现7.3 核心要点时间复杂度O(n log n)稳定空间复杂度O(n)需要额外空间稳定性稳定适用场景大规模数据、链表排序、外部排序、需要稳定排序的场景八、快速排序 (Quick Sort)8.1 算法思想分治法选择一个基准元素将数组分成两部分左边都小于基准右边都大于基准然后递归排序两部分。步骤1.定义待排序数组中第一个位置作为基准数2.j游标从后往前移动找第一个比基准数小的值找到后停止3.i游标从前往后移动找第一个比基准数大的值找到后停止4.i和j交换继续查找直至相遇5.相遇位置和基准数进行交换基准数到达正确位置以基准数为起点进行拆分重复所有直到数据全被拆分为止。8.2 Java实现8.3 核心要点时间复杂度平均O(n log n)最坏O(n²)已排序或逆序空间复杂度O(log n) ~ O(n)递归栈稳定性不稳定适用场景大规模数据、通用排序、性能要求高的场景优化策略三数取中、随机化基准、小数组使用插入排序九、堆排序 (Heap Sort)9.1 算法思想利用堆这种数据结构进行排序先将数组构建成最大堆然后反复将堆顶元素最大值与末尾元素交换并调整堆。步骤1.利用完全二叉树构建大顶堆大顶堆父节点的值大于等于左右孩子的值2.堆顶和堆底元素进行交换除了堆底元素之外剩余元素继续构建大顶堆不断重复直到排序完成构建大顶堆从后往前依次检测每个节点是否符合大顶堆不符合则进行调整1.定义parent游标指向要检测的节点2.定义child游标指向parent的左孩子如果child为空则符合大顶堆3.child不为空判断parent有没有右孩子child指向左右孩子的最大值4.父节点进行比较如果父节点值大则符合大顶堆父节点值小父节点进行交换5.parent指向childchild指向左右孩子的最大值继续比较直到parent指向的值大或者child指向空。9.2 Java实现9.3 核心要点时间复杂度O(n log n)稳定空间复杂度O(1)原地排序稳定性不稳定适用场景大规模数据、需要原地排序、优先级队列实现十、计数排序 (Counting Sort)10.1 算法思想非比较排序算法适用于整数排序。统计每个元素出现的次数然后根据统计结果重建有序序列。10.2 Java实现10.3 核心要点时间复杂度O(n k)k为数据范围空间复杂度O(k)需要额外计数数组稳定性稳定从后往前遍历保证适用场景整数排序、数据范围小、非比较排序场景十一、桶排序 (Bucket Sort)11.1 算法思想桶排序是计数排序的扩展将数据分到有限数量的桶里每个桶再分别排序可以使用其他排序算法或递归桶排序最后按顺序合并所有桶的结果。11.2 Java实现11.3 核心要点时间复杂度平均O(n k)最坏O(n²)所有元素分配到同一个桶空间复杂度O(n k)需要额外桶空间稳定性稳定取决于桶内排序算法的稳定性适用场景数据均匀分布、外部排序、数据范围已知且分布均匀十二、基数排序 (RadixSort)12.1 算法思想基数排序是一种非比较整数排序算法按照低位先排序然后收集再按照高位排序然后再收集依次类推直到最高位。通常使用计数排序作为子排序算法。12.2 Java实现12.3 核心要点时间复杂度O(d * (n k))d为最大位数k为基数通常为10空间复杂度O(n k)需要额外计数数组和输出数组稳定性稳定使用稳定的子排序算法适用场景整数排序、字符串排序按字符、数据位数固定或范围有限