常见的排序方法

目录

1. 插入排序

2. 希尔排序

3. 选择排序

4. 堆排序

5. 冒泡排序

6. 快速排序

1. 快速排序的实现

1. 思路（以从小到大排序为例）

2. 选取基准元素的方法（Hoare）

3. 选取基准元素的方法（挖坑法）

2. 快速排序的优化

3. 快速排序的非递归实现

7. 归并排序

1. 归并排序的实现

2. 归并排序的非递归实现

3. 海量数据的排序问题

8. 计数排序

1. 插入排序

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定性：稳定

特点：数据越有序，排序越快

思路（以从小到大排序为例）：

指针 i 标记新拿到的数据，指针 j 标记已有的排好序的数据，初始情况为 i = 1， j = i - 1；

i 向后遍历，如果拿到的数据比 j 指向的数据大，直接将 i 指向的数据放在 j + 1 的位置；

注意：第一次挪 j 位置的数据会覆盖掉原来 i 位置的数据，因此需要定义一个变量，提前保存好 i 位置的数据；

如果 i 指向的数据小于等于 j 指向的数据，将 j 指向的数据放在 j + 1 位置即可；

如果 i 指向的数据比所有的 j 维护的数据都小，那么 j 会减小至负数，将 i 位置数据放到 0 位置即可；

    public static void insertSort(int[] array){int n = array.length;for(int i = 1; i < n; i++){int j = i - 1;int tmp = array[i];for( ; j >= 0; j--){if(tmp < array[j]){array[j + 1] = array[j];}else{break;}}array[j + 1] = tmp;}}

2. 希尔排序

时间复杂度：O(n^1.3 ~ n^1.5)

空间复杂度：O(1)

稳定性：不稳定

思路（以从小到大排序为例）：

先将数据分成若干组，每组元素间隔距离为 gap，每组元素以插入排序的方式进行排序；

排序完成后，每组元素间隔距离为 gap / 2，再以插入排序的方式进行排序，直至 gap = 1，整体完成排序；

    public static void shellSort(int[] array){int gap = array.length;while(gap > 0){gap /= 2;shell(array, gap);}}private static void shell(int[] array, int gap){int n = array.length;for(int i = gap; i < n; i++){int tmp = array[i];int j = i - gap;for(; j >= 0; j -= gap){if(array[j] > tmp){array[j + gap] = array[j];}else{break;}}array[j + gap] = tmp;}}

3. 选择排序

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定性：不稳定

思路（以从小到大排序为例）：

定义 i 指针遍历数组，定义 j = i + 1，找最小值，找到最小值后，将下标 j 存在 minIndex 里面；

交换 i 位置和 minIndex 位置元素，直到 i 遍历数组完成；

    public static void selectSort(int[] array){int n = array.length;for(int i = 0; i < n; i++){int minIndex = i;for(int j = i + 1; j < n; j++){if(array[j] < array[minIndex]){minIndex = j;}}swap(array, i, minIndex);}}private static void swap(int[] array, int i, int j){int tmp = array[i];array[i] = array[j];array[j] = tmp;}

4. 堆排序

时间复杂度：O(n* logn)

空间复杂度：O(1)

稳定性：不稳定

思路（以从小到大排序为例）：

建立一个大根堆，从后往前遍历每一棵子树，如果根节点值小于左右孩子节点的最大值，根节点值和最大值交换，重新指向交换过的孩子节点并向下调整；

交换堆顶元素和最后一个元素，并将堆顶元素向下调整；

    private static void swap(int[] array, int i, int j){int tmp = array[i];array[i] = array[j];array[j] = tmp;}public static void heapSort(int[] array){// 建一个大根堆int n = array.length;int parent = (n - 1 - 1) / 2;for( ; parent >= 0; parent--){shiftDown(array, parent, n);}// 排序int end = n - 1;while(end > 0){swap(array, 0, end);shiftDown(array, 0, end--);}}private static void shiftDown(int[] array, int parent, int size){int child = parent * 2 + 1;while(child < size){if(child + 1 < size && array[child] < array[child + 1]){child++;}if(array[child] > array[parent]){swap(array, child, parent);parent = child;child = parent * 2 + 1;}else{break;}}}

5. 冒泡排序

时间复杂度：O(n*2)

空间复杂度：O(1)

稳定性：稳定

思路（以从小到大排序为例）：

定义指针 i 标记排序的趟数，如果数组长度为 n，排 n - 1 趟即可；

定义指针 j 标记要比较的元素，和 j + 1 位置的元素做比较，如果 array[j] > array[j + 1]，交换 j 位置和 j + 1 位置的元素；

优化：如果一趟排序下来没有发生交换，表示已经有序了，跳出循环即可；

    public static void bubbleSort(int[] array){int n = array.length;for(int i = 0; i < n - 1; i++){boolean flag = false;for(int j = 0; j < n - 1 - i; j++){if(array[j] > array[j + 1]){swap(array, j, j + 1);flag = true;}}if(!flag) break;}}private static void swap(int[] array, int i, int j){int tmp = array[i];array[i] = array[j];array[j] = tmp;}

6. 快速排序

时间复杂度：

快排算法的时间复杂度取决于分割数组的方式（基准元素的选取），因此分割方式不同，时间复杂度不同；

如果基准元素每次都正好选取了要排序部分的中位数，那么时间复杂度应为 O(n*logn)；

如果基准元素每次都正好选取了要排序部分的最小值或者最大值，那么时间复杂度应为 O(n^2)；

空间复杂度：O(logn)

稳定性：不稳定

1. 快速排序的实现

1. 思路（以从小到大排序为例）

采用数组分块的思想，选取一个基准元素，将数组分成两块，此时基准元素已经有序了，分别处理基准元素左右两遍的区间；

左边部分再选取基准元素，在 [left, pivot - 1] 中递归；

右边部分再选取基准元素，在 [pivot + 1, right] 中递归；

2. 选取基准元素的方法（Hoare）

left 指向待排序的区间的左端点，right 指向待排序的区间的右端点；

选取左端点指向的元素为基准元素；

如果 right 指针指向的元素大于等于基准元素，就向左移动；

如果 left 指针指向的元素小于等于基准元素，就向右移动；

此时 right 指向的是比基准元素小的值，left 指向的是比基准元素大的值，交换 left 和 right 指向的元素；

直到 left 指针和 right 指针相遇，此时指向的位置，左边的元素都小于等于基准元素，右边的元素都大于等于基准元素；

    public static void quickSort(int[] array){int n = array.length;quick(array, 0, n - 1);}public static void quick(int[] array, int left, int right){if(left >= right) return;int pivot = partition(array, left, right);quick(array, left, pivot - 1);quick(array, pivot + 1, right);}private static int partition(int[] array, int left, int right){int tmp = array[left];int pos = left;while(left < right){while(left < right && array[right] >= tmp) right--;while(left < right && array[left] <= tmp) left++;swap(array, left, right);}swap(array, pos, left);return left;}private static void swap(int[] array, int i, int j){int tmp = array[i];array[i] = array[j];array[j] = tmp;}

要点 1：为什么选取基准元素，移动 left 和 right 指针的时候要取等号？

防止 left 和 right 指针指向的元素都恰好等于基准元素的值，都等于会陷入死循环；

要点 2：为什么要先移动 right 指针，而不是先移动 left 指针？

如果先移动 left，当 left 和 right 指针相遇的时候，指向的元素的值会大于基准元素，如果交换基准元素和该元素，就会把比基准元素大的值交换到左边去，不符合排序的思想；

3. 选取基准元素的方法（挖坑法）

left 指向待排序的区间的左端点，right 指向待排序的区间的右端点；

选取左端点指向的元素为基准元素；

如果 right 指针指向的元素大于等于基准元素，就向左移动；

此时 right 指向的是比基准元素小的值，把 right 指向的元素放到 left 指向的位置；

如果 left 指针指向的元素小于等于基准元素，就向右移动；

此时 left 指向的是比基准元素大的值，把 left 指向的元素放到 right 指向的位置；

直到 left 指针和 right 指针相遇，把基准元素放到此时指向的位置，左边的元素都小于等于基准元素，右边的元素都大于等于基准元素，此时基准元素已经有序了；

    private static int partition2(int[] array, int left, int right){int tmp = array[left];while(left < right) {while(left < right && array[right] >= tmp) right--;array[left] = array[right];while(left < right && array[left] <= tmp) left++;array[right] = array[left];}array[left] = tmp;return left;}

2. 快速排序的优化

使用快排为了避免出现选取基准元素选取到区间中的最大值或者最小值的情况，因此可以结合三数取中法进行优化；

思路：

定义 left 指向区间的左端点，right 指向区间的右端点，mid 指向区间的中点；

找出 left，right，mid 指向的元素中第二大的元素，返回下标；

    private static int midOfThree(int[] array, int left, int right){int mid = (left + right) / 2;if(array[left] < array[right]){if(array[mid] < array[left]) return left;else if(array[mid] > array[right]) return right;else return mid;}else {if(array[mid] < array[right]) return right;else if(array[mid] > array[left]) return left;else return mid;}}

结合三数取中法优化：

记录三数取中法返回的下标 index，index 指向的元素和 left 指向的元素进行交换，保证数组分块时，每次选取 left 指向的元素都不是区间内的最大值和最小值，使分块形成的二叉树尽可能接近完全二叉树；

    public static void quick(int[] array, int left, int right){if(left >= right) return;int index = midOfThree(array, left, right);swap(array, index, left);int pivot = partition(array, left, right);quick(array, left, pivot - 1);quick(array, pivot + 1, right);}

3. 快速排序的非递归实现

快速排序可以借助递归实现，递的过程就是调用方法在栈上开辟栈帧的过程，归的过程就是方法返回销毁栈帧的过程，因此递归通常可以借助栈来转化为非递归。

思路：

递归是找基准元素将数组分块，再分别处理左边区间和右边区间；

因此可以将区间的左右端点加入到栈中，每次弹出一组端点，分别为区间的右端点和左端点；

调用数组分块的方法，将这段区间分为两块，再重新将两块区间的端点加入到栈中；

直至弹出栈中所有的数对，排序就完成了；

    // 快排的非递归版本public static void quickSortNor(int[] array){int n = array.length;Stack<Integer> stack = new Stack<>();stack.push(0);stack.push(n - 1);while(!stack.isEmpty()){int right = stack.pop();int left = stack.pop();int pivot = partition2(array, left, right);if(left + 1 < pivot){stack.push(left);stack.push(pivot - 1);}if(pivot + 1 < right){stack.push(pivot + 1);stack.push(right);}}}

7. 归并排序

时间复杂度：O(n*logn)

空间复杂度：O(n)

稳定性：稳定

1. 归并排序的实现

思路：

给定一段待排序的区间，left 指向区间左端点，right 指向区间右端点，mid 指向区间左中点；

先对左边区间进行排序 [left, mid]，再对右边区间进行排序 [mid + 1, right]；

合并两个有序区间；

    public static void mergeSort(int[] array){mergeSortFunc(array, 0, array.length - 1);}private static void mergeSortFunc(int[] array, int left, int right) {if(left >= right) return;int mid = (right + left) / 2;mergeSortFunc(array, left, mid);mergeSortFunc(array, mid + 1, right);merge(array, left, mid, right);}private static void merge(int[] array, int left, int mid, int right){int i = left;int j = mid + 1;int k = 0;int[] tmp = new int[right - left + 1];while(i <= mid && j <= right){if(array[i] <= array[j]){tmp[k++] = array[i++];}else{tmp[k++] = array[j++];}}while(i <= mid) tmp[k++] = array[i++];while(j <= right) tmp[k++] = array[j++];for(int l = left; l <= right; l++){array[l] = tmp[l - left];}}

2. 归并排序的非递归实现

思路：

定义变量 gap 表示每次排序的子区间的长度，从左向右对子区间进行排序；

left 用于表示子区间的左端点，mid 表示子区间的右端点，mid + 1 表示下一个子区间的左端点，right 表示下一个子区间的右端点，分别计算 left，mid，right 的值；

调用 merge() 方法合并两个有序区间；

gap 增大为原来的 2 倍，继续重复上述步骤，直到 gap 增大到大于等于整个数组的长度；

    public static void mergeSortNor(int[] array){int n = array.length;int gap = 1;while(gap < n){for(int i = 0; i < n; i += 2 * gap){int left = i;int mid = i + gap - 1;int right = mid + gap;if(mid >= n) mid = n - 1;if(right >= n) right = n - 1;merge(array, left, mid, right);}gap *= 2;}}

3. 海量数据的排序问题

外部排序：排序过程需要在磁盘外部进行的排序；

前提：内存只有 1G，需要排序 100G 的数据；

因为内存只有 1G，无法将所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序；

实现步骤：

1. 先把数据分割成 200 份，每份 512M；

2. 对每一份 512M 的数据进行排序，因为内存可以放得下，因此选用哪种排序方式均可；

3. 进行 2 路归并，同时读取两个文件中的数据，每次读 1 个数据，进行比较排序，并写入到一个新文件中；

4. 得到新文件再按照上述方式进行 2 路归并，最终形成一个新的数据有序的文件；

8. 计数排序

时间复杂度：O(N+数据范围)

空间复杂度：O(数据范围)

稳定性：稳定

思路（下面代码是不稳定的排序）：

遍历一遍数组，找出最小值 minVal 和最大值 maxVal；

建立一个计数数组 count，大小为 maxVal - minVal + 1；

遍历一遍数组，统计每个数字出现的次数，minVal 放到下标为 0 的位置，依次类推；

遍历一遍 count 数组，如果 count[i] 不等于 0，依次将数字放到原数组中；

    public static void countSort(int[] array){int n = array.length;int minVal = array[0];int maxVal = array[0];for(int x : array){if(minVal > x) minVal = x;if(maxVal < x) maxVal = x;}int[] count = new int[maxVal - minVal + 1];for(int x : array){count[x - minVal]++;}int pos = 0;for(int i = 0; i < count.length; i++){while(count[i]-- > 0){array[pos++] = i + minVal;}}}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.pswp.cn/bicheng/86493.shtml
繁体地址，请注明出处：http://hk.pswp.cn/bicheng/86493.shtml

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

【matlab定位例程】基于AOA和TDOA混合的定位方法，背景为三维空间，自适应锚点数量，附下载链接

【matlab定位例程】基于AOA和TDOA混合的定位方法，背景为三维空间，自适应锚点数量，附下载链接

文章目录 代码概述代码功能概述核心算法原理AOA定位模型TDOA定位迭代算法混合定位策略关键技术创新 运行结果4个锚点的情况40个锚点的情况 MATLAB源代码 代码概述 代码功能概述 本代码实现了一种三维空间中的混合定位算法&#xff0c;结合到达角&#xff08; A O A AOA AOA&a…
阅读更多...
专题：2025医疗AI应用研究报告|附200+份报告PDF汇总下载

专题：2025医疗AI应用研究报告|附200+份报告PDF汇总下载

原文链接&#xff1a;https://tecdat.cn/?p42748 本报告汇总解读聚焦医疗行业人工智能应用的前沿动态与市场机遇&#xff0c;以数据驱动视角剖析技术演进与商业落地的关键路径。从GenAI在医疗领域的爆发式增长&#xff0c;到细分场景的成熟度矩阵&#xff0c;再到运营成本压力…
阅读更多...
推荐一个前端基于vue3.x，vite7.x，后端基于springboot3.4.x的完全开源的前后端分离的中后台管理系统基础项目（纯净版）

推荐一个前端基于vue3.x，vite7.x，后端基于springboot3.4.x的完全开源的前后端分离的中后台管理系统基础项目（纯净版）

XHan Admin 简介 &#x1f389;&#x1f389; XHan Admin 是一个开箱即用的开源中后台管理系统基础解决方案&#xff0c; 项目为前后端分离架构。采用最新的技术栈全新构建&#xff0c;纯净的项目代码&#xff0c;没有历史包袱。 前端使用最新发布的 vite7.0 版本构建&#xf…
阅读更多...
MySQL误删数据急救指南：基于Binlog日志的实战恢复详解

MySQL误删数据急救指南：基于Binlog日志的实战恢复详解

背景 数据误删是一个比较严重的场景 1.典型误操作场景 场景1&#xff1a;DELETE FROM orders WHERE status0 → 漏写AND create_time>‘2025-06-20’ 场景2&#xff1a;DROP TABLE customer → 误执行于生产环境 认识 binlog 1.binlog 的核心作用 记录所有 DDL/DML 操…
阅读更多...
高效数据采集方案：快速部署与应用 AnyCrawl 网页爬虫工具实操指南

高效数据采集方案：快速部署与应用 AnyCrawl 网页爬虫工具实操指南

以下是对 AnyCrawl 的简单介绍&#xff1a; AnyCrawl 提供高性能网页数据爬取&#xff0c;其功能专为 LLM 集成和数据处理而设计支持利用搜索引擎直接查询获取结果内容&#xff0c;类似 searxng提供开发者友好的API&#xff0c;支持动态内容抓取&#xff0c;并输出结构化数据&…
阅读更多...
vue3可以分页、搜索的select

vue3可以分页、搜索的select

下载 npm i v-selectpage基本使用 import { SelectPageList } from v-selectpage;<SelectPageListlanguage"zh-chs"key-prop"id"label-prop"name"fetch-data"fetchData" />const fetchData (data,callback) > {const { sea…
阅读更多...
C# 入门学习教程 (一)

C# 入门学习教程 (一)

文章目录 一、解决方案与项目1. Solution 与 project 二、类与名称空间1.类与名称空间2.类库的引用1. DLL引用&#xff08;黑盒引用&#xff0c;无源代码&#xff09;2. Nuget 引用3. 项目引用&#xff08;白盒引用&#xff0c;有源代码&#xff09; 3.依赖关系 三、类&#xf…
阅读更多...
76、单元测试-参数化测试

76、单元测试-参数化测试

76、单元测试-参数化测试 参数化测试是一种单元测试技术&#xff0c;通过将测试数据与测试逻辑分离&#xff0c;使用不同的输入参数多次运行相同的测试用例&#xff0c;从而提高测试效率和代码复用性。 #### 基本原理 - **数据驱动测试**&#xff1a;将测试数据参数化&#xf…
阅读更多...
SQL学习笔记3

SQL学习笔记3

SQL常用函数 1、字符串函数 函数调用的语法&#xff1a;select 函数&#xff08;参数); 常用的字符串函数有&#xff1a; 拼接字符串&#xff0c;将几个字符串拼到一起&#xff1a;concat (s1,s2,……); select concat(你好,hello); update mytable set wherefo concat(中…
阅读更多...
Golang 面向对象编程，如何实现 封装、继承、多态

Golang 面向对象编程，如何实现 封装、继承、多态

Go语言虽然不是纯粹的面向对象语言&#xff0c;但它通过结构体(struct)、接口(interface)和方法(method)提供了面向对象编程的能力。下面我将通过具体示例展示Go中如何实现类、封装、继承、多态以及构造函数等概念。 1. 类与封装 在Go中&#xff0c;使用结构体(struct)来定义…
阅读更多...
为什么android要使用Binder机制

为什么android要使用Binder机制

1.linux中大多数标准 IPC 场景&#xff08;如管道、消息队列、ioctl 等&#xff09;的进程间通信机制 ------------------ ------------------ ------------------ | 用户进程 A | | 内核空间 | | 用户进程 B | | (User Spa…
阅读更多...
OpenCV CUDA模块设备层-----双曲余弦函数cosh()

OpenCV CUDA模块设备层-----双曲余弦函数cosh()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 该函数用于计算四维浮点向量&#xff08;float4类型&#xff09;的双曲余弦值&#xff0c;作用于CUDA设备端。双曲余弦函数定义为cosh(x) (eˣ …
阅读更多...
48页PPT | 企业数字化转型关键方法论：实践路径、案例和落地评估框架

48页PPT | 企业数字化转型关键方法论：实践路径、案例和落地评估框架

目录 一、什么是企业数据化转型&#xff1f; 二、为什么要进行数据化转型&#xff1f; 1. 市场复杂性与不确定性上升 2. 内部流程效率与协同难题突出 3. 数字资产沉淀不足&#xff0c;智能化基础薄弱 三、数据化流程管理&#xff1a;从“业务流程”到“数据流程”的对齐 …
阅读更多...
VTK中的形态学处理

VTK中的形态学处理

VTK图像处理代码解析：阈值化与形态学开闭运算 这段代码展示了使用VTK进行医学图像处理的两个关键步骤：阈值分割和形态学开闭运算。下面我将详细解析每个部分的功能和实现原理。 处理前 处理后 1. 阈值分割部分 (vtkImageThreshold) vtkSmartPointer<vtkImageThresho…
阅读更多...
xlsx.utils.sheet_to_json() 方法详解

xlsx.utils.sheet_to_json() 方法详解

sheet_to_json() 是 SheetJS/xlsx 库中最常用的方法之一&#xff0c;用于将 Excel 工作表&#xff08;Worksheet&#xff09;转换为 JSON 格式数据。下面我将全面讲解它的用法、参数配置和实际应用场景。 基本语法 javascript 复制 下载 const jsonData XLSX.utils.sheet…
阅读更多...
〔从零搭建〕BI可视化平台部署指南

〔从零搭建〕BI可视化平台部署指南

&#x1f525;&#x1f525; AllData大数据产品是可定义数据中台&#xff0c;以数据平台为底座&#xff0c;以数据中台为桥梁&#xff0c;以机器学习平台为中层框架&#xff0c;以大模型应用为上游产品&#xff0c;提供全链路数字化解决方案。 ✨杭州奥零数据科技官网&#xf…
阅读更多...
合规型区块链RWA系统解决方案报告——机构资产数字化的终极武器

合规型区块链RWA系统解决方案报告——机构资产数字化的终极武器

&#xff08;跨境金融科技解决方案白皮书&#xff09; 一、直击机构客户四大痛点 痛点传统方案缺陷我们的破局点✖️ 跨境资产流动性差结算周期30天&#xff0c;摩擦成本超8%▶️ 724h全球实时交易&#xff08;速度提升90%&#xff09;✖️ 合规成本飙升KYC/AML人工审核占成本…
阅读更多...
探索阿里云容器：解锁云原生应用的无限可能

探索阿里云容器：解锁云原生应用的无限可能

引言&#xff1a;容器时代的开启 在数字化浪潮汹涌澎湃的当下&#xff0c;云计算已成为企业创新与发展的关键驱动力。从早期的基础设施即服务&#xff08;IaaS&#xff09;&#xff0c;到如今蓬勃发展的平台即服务&#xff08;PaaS&#xff09;和软件即服务&#xff08;SaaS&a…
阅读更多...
spring-ai 1.0.0 （1）模型调用能力

spring-ai 1.0.0 （1）模型调用能力

听说1.0是一个非常好用的版本&#xff0c;最后还是扛不住听说的压力&#xff0c;为了落实自己悬浮心理&#xff0c;自己还是着手实践一下了。 第一步pom集成&#xff1a; 参考spring-projects/spring-ai | DeepWiki维基以及官方文档入门 &#xff1a;&#xff1a; Spring AI …
阅读更多...
数据分享：汽车行业-汽车属性数据集

数据分享：汽车行业-汽车属性数据集

说明&#xff1a;如需数据可以直接到文章最后关注获取。 1.数据背景 Automobile数据集源自于对汽车市场深入研究的需求&#xff0c;旨在为汽车行业提供一个全面且详细的资源&#xff0c;以便更好地理解影响汽车价格及性能的各种因素。该数据集最初由卡内基梅隆大学&#x…
阅读更多...
最新文章

Copyright @ 2022~2023