当前位置： 首页 > ai >正文

快速、归并、堆、希尔、ArrayList排序

ai 2025/9/6 8:38:55

一、快速排序

描述：快速排序（Quick Sort）是一种高效的分治排序算法，其工作原理如下：

基本思想

  • 通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小
  • 分别对这两部分记录继续进行排序，以达到整个序列有序
  • 采用分治法策略，递归地对子数组进行排序

工作原理

  1. 选择基准元素：从数组中选择一个元素作为基准（pivot），通常选择最后一个元素
  2. 分区操作：重新排列数组，使得比基准小的元素放在基准左边，比基准大的元素放在基准右边
  3. 递归排序：对基准左右两个子数组递归地进行快速排序
  4. 基准定位：每次分区操作后，基准元素会放到其最终的正确位置上
  5. 终止条件：当子数组长度小于等于1时，递归终止
    public static void main(String[] args) {int [] a = {5,3,2,4,1};quickSort(a, 0, a.length - 1);System.out.println(Arrays.toString(a));}// 快速排序public static void quickSort(int[] arr, int low, int high) {if (low < high) {                           // 递归终止条件：子数组长度大于1int pi = partition(arr, low, high);     // 获取分区点quickSort(arr, low, pi - 1);            // 递归排序左半部分quickSort(arr, pi + 1, high);           // 递归排序右半部分}}public static int partition(int[] arr, int low, int high) {int pivot = arr[high];                      // 选择最后一个元素作为基准int i = (low - 1);                          // 小于基准的元素的索引for (int j = low; j < high; j++) {          // 遍历从low到high-1的元素if (arr[j] <= pivot) {                  // 如果当前元素小于等于基准i++;                                // 扩展小于基准的区域int temp = arr[i];                  // 交换元素arr[i] = arr[j];arr[j] = temp;}}int temp = arr[i + 1];                      // 将基准放到正确位置arr[i + 1] = arr[high];arr[high] = temp;return i + 1;                               // 返回基准的索引}

特点

  • 时间复杂度：
    • 最好情况：O(n log n) - 每次分区都能平均分割
    • 平均情况：O(n log n)
    • 最坏情况：O(n²) - 每次选到最大或最小元素作为基准
  • 空间复杂度：O(log n) - 递归调用栈空间
  • 稳定性：不稳定排序算法
  • 适用场景：大规模数据集，对性能要求较高的场景

二、归并排序

描述：归并排序（Merge Sort）是一种基于分治思想的排序算法，其工作原理如下：

基本思想

  • 将数组不断二分，直到每个子数组只有一个元素
  • 然后将这些子数组两两合并，合并过程中保持有序
  • 最终得到一个完全有序的数组

工作原理

  1. 分解：将数组从中间分成两个子数组，递归地对两个子数组进行分解
  2. 解决：当子数组长度为1时，认为其已排序
  3. 合并：将两个已排序的子数组合并成一个有序数组
  4. 递归：重复上述过程，直到整个数组有序
    public static void main(String[] args) {int [] a = {5,3,2,4,1};mergeSort(a, 0, a.length - 1);System.out.println(Arrays.toString(a));}// 归并排序public static void mergeSort(int[] arr, int left, int right) {// 当 left < right 时继续分解数组if (left < right) {// 计算中间位置，将数组分为两部分int mid = (left + right) / 2;// 递归排序左半部分mergeSort(arr, left, mid);// 递归排序右半部分mergeSort(arr, mid + 1, right);// 合并已排序的两部分merge(arr, left, mid, right);}}// 合并两个已排序的子数组public static void merge(int[] arr, int left, int mid, int right) {// 计算左右子数组的长度int n1 = mid - left + 1;  // 左子数组长度int n2 = right - mid;     // 右子数组长度// 创建临时数组存储左右子数组int[] leftArr = new int[n1];int[] rightArr = new int[n2];// 将原数组元素复制到临时数组中for (int i = 0; i < n1; i++)leftArr[i] = arr[left + i];  // 复制左子数组for (int j = 0; j < n2; j++)rightArr[j] = arr[mid + 1 + j];  // 复制右子数组// 初始化左右子数组的索引以及合并后数组的索引int i = 0, j = 0, k = left;// 比较两个子数组的元素，将较小的元素放入原数组while (i < n1 && j < n2) {if (leftArr[i] <= rightArr[j]) {arr[k] = leftArr[i];  // 左子数组元素较小，放入原数组i++;  // 左子数组索引后移} else {arr[k] = rightArr[j]; // 右子数组元素较小，放入原数组j++;  // 右子数组索引后移}k++;  // 原数组索引后移}// 将左子数组剩余元素复制到原数组while (i < n1) {arr[k] = leftArr[i];i++;k++;}// 将右子数组剩余元素复制到原数组while (j < n2) {arr[k] = rightArr[j];j++;k++;}}

特点

  • 时间复杂度：
    • 最好情况：O(n log n)
    • 平均情况：O(n log n)
    • 最坏情况：O(n log n)
  • 空间复杂度：O(n) - 需要额外的数组空间用于合并
  • 稳定性：稳定排序算法
  • 适用场景：大规模数据排序，对时间复杂度有稳定要求的场景

三、堆排序

描述：堆排序（Heap Sort）是一种基于二叉堆数据结构的比较排序算法。它利用堆这种数据结构所设计的一种排序算法，是选择排序的优化版本。

基本思想

  • 将待排序数组构建成一个最大堆（或最小堆）
  • 此时数组的第一个元素就是最大（或最小）值
  • 将堆顶元素与末尾元素交换，然后重新调整剩余元素为堆
  • 重复此过程，直到所有元素排序完成

工作原理

  1. 构建初始堆：将无序数组调整为最大堆结构
  2. 交换堆顶与末尾元素：将堆顶最大值与末尾元素交换，使最大值"沉底"
  3. 重新调整堆：对剩余未排序元素重新构建最大堆
  4. 重复过程：重复步骤2-3，直到所有元素排序完成
    // 堆排序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--) {// 将当前最大元素（堆顶）移到数组末尾int temp = arr[0];arr[0] = arr[i];arr[i] = temp;// 重新调整剩余元素为最大堆heapify(arr, i, 0);}}// 调整堆结构，使其满足最大堆性质public static 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) {int swap = arr[i];arr[i] = arr[largest];arr[largest] = swap;// 递归调整受影响的子树heapify(arr, n, largest);}}

特点

  • 时间复杂度：
    • 最好情况：O(n log n)
    • 平均情况：O(n log n)
    • 最坏情况：O(n log n)
  • 空间复杂度：O(1) - 原地排序算法
  • 稳定性：不稳定排序算法（相同元素的相对位置可能改变）
  • 适用场景：对空间复杂度有要求，且数据量较大的排序场景

四、希尔排序

描述：希尔排序（Shell Sort）是插入排序的一种更高效的改进版本，也称为递减增量排序算法。它通过将原始数组按照一定的间隔（gap）分成若干子序列，对这些子序列分别进行插入排序，然后逐步缩小间隔，最终当间隔为1时，进行一次完整的插入排序。

基本思想

  • 设置一个间隔序列，通常初始间隔为数组长度的一半
  • 按照间隔将数组分组，对每组进行插入排序
  • 逐步缩小间隔，重复上述过程
  • 当间隔为1时，进行最后一次插入排序，完成排序

工作原理

  1. 选择间隔：选择一个间隔序列，通常从数组长度的一半开始
  2. 分组排序：按照当前间隔将数组分组，对每组执行插入排序
  3. 缩小间隔：将间隔减小（通常除以2），重复分组排序过程
  4. 最终排序：当间隔为1时，进行一次完整的插入排序
    public static void main(String[] args) {int [] a = {5,3,2,4,1};shellSort(a);System.out.println(Arrays.toString(a));}// 希尔排序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 key = arr[i];  // 当前要插入的元素int j = i;// 在间隔为gap的子序列中进行插入排序while (j >= gap && arr[j - gap] > key) {arr[j] = arr[j - gap];  // 将大于key的元素向后移动gap个位置j -= gap;}arr[j] = key;  // 插入当前元素到正确位置}}}

特点

  • 时间复杂度：
    • 最好情况：O(n log n) - 数组已经基本有序
    • 平均情况：O(n^1.3) - 根据间隔序列的选择而变化
    • 最坏情况：O(n²) - 使用不当的间隔序列
  • 空间复杂度：O(1) - 原地排序算法
  • 稳定性：不稳定排序算法（相同元素的相对位置可能改变）
  • 适用场景：中等规模数据排序，比插入排序更高效，实现相对简单

五、 ArrayList 排序

ArrayList本身是一种动态数组数据结构，它本身并不直接提供排序功能。在Java中，对ArrayList进行排序通常使用以下方式：

ArrayList排序方式

  1. 使用Collections.sort()方法

    • 对于ArrayList，通常使用Collections.sort()方法进行排序
    • 该方法内部使用的是优化的归并排序（Timsort算法）

  2. 使用Arrays.sort()方法

    • 如果将ArrayList转换为数组，可以使用Arrays.sort()方法
    • 对于基本类型数组，使用双轴快速排序（Dual-Pivot Quicksort）
    • 对于对象数组，使用Timsort算法
ArrayList排序的具体实现
// 示例：ArrayList排序用法
ArrayList<Integer> list = new ArrayList<>();
list.add(5);
list.add(3);
list.add(2);
list.add(8);
list.add(1);list.sort(Comparator.naturalOrder()); //升序
list.sort(Collections.reverseOrder()); //倒叙
// 使用Collections.sort()排序
Collections.sort(list); // 内部使用Timsort算法 //升序
Collections.sort(list, Collections.reverseOrder()); //倒叙
Timsort算法特点
  • 混合排序算法：结合了归并排序和插入排序的优点
  • 稳定排序：相等元素的相对位置不会改变
  • 自适应性：对于部分有序的数据效率很高
  • 时间复杂度：
    • 最好情况：O(n) - 数据已经有序
    • 平均情况：O(n log n)
    • 最坏情况：O(n log n)
  • 空间复杂度：O(n)
Collections.sort()方法的实现逻辑如下：
  1. 将ArrayList转换为数组
  2. 调用Arrays.sort()方法对数组进行排序
  3. 将排序后的数组元素重新放回ArrayList
    default void sort(Comparator<? super E> c) {Object[] a = this.toArray();Arrays.sort(a, (Comparator) c);ListIterator<E> i = this.listIterator();for (Object e : a) {i.next();i.set((E) e);}}

对于对象类型（如Integer、String等），Arrays.sort()使用Timsort算法，这是一种高度优化的归并排序变体。因此，可以说ArrayList在Java中排序时主要使用的是Timsort算法，它是一种稳定、高效的排序算法，实际应用中常见的部分有序数据。

http://www.xdnf.cn/news/20067.html

相关文章：

  • pyinstaller
  • SQL decode() 函数
  • Python爬虫实战：研究Axes Grid模块，构建旅游平台酒店数据采集和分析系统
  • VNC连接服务器实现远程桌面-针对官方给的链接已经失效问题
  • Linux 综合练习
  • LTE CA和NR CA的区别和联系
  • 第七章 Cesium 3D 粒子烟花效果案例解析：从原理到完整代码
  • CSS Position 属性
  • Pspice仿真电路：（三十六）变压器仿真
  • 本科论文抽检档案整理：Python批量文件查找、打包、改名
  • 【uniapp】打包为h5在保留头部标题的同时配置网站标题不跟随页面路由更新
  • CVPR 2025|无类别词汇的视觉-语言模型少样本学习
  • RikkaHub：安卓原生AI聊天新体验
  • 【设计模式】UML 基础教程总结（软件设计师考试重点）
  • 十一、标准化和软件知识产权基础知识
  • 认识 Flutter
  • 告别 OpenAI SDK：如何使用 Python requests 库调用大模型 API（例如百度的ernie-4.5-turbo）
  • 【Qt开发】按钮类控件（三）-＞ QCheckBox
  • 【完整源码+数据集+部署教程】手袋类型检测系统源码和数据集：改进yolo11-AFPN-P345
  • 前端开发，同源策略
  • 【Linux】Linux进程状态和僵尸进程：一篇看懂“进程在忙啥”
  • 基于OpenGL封装摄像机类：视图矩阵与透视矩阵的实现
  • 如何下载B站视频，去水印，翻译字幕
  • .Net程序员就业现状以及学习路线图（四）
  • 创建线程有哪几种方式
  • 【数字孪生核心技术】数字孪生有哪些核心技术？
  • Kubernetes（四）：Service
  • HyperWorks许可服务器设置
  • 企业微信AI怎么用？食品集团靠它砍掉50%低效操作，答案就是选对企业微信服务商
  • ZeroMQ 编译 项目使用流程文档