十大排序算法汇总

好的，下面为你整理一篇面试全覆盖、极其深入的十大排序算法总结博客，涵盖算法原理、复杂度、稳定性、应用场景、工程实践、C++与Python实现（含详细注释），并对比分析各种排序的优缺点与适用情境。内容力求结构清晰、讲解透彻，适合面试复习与深入学习。

十大排序算法全解析（面试高频+工程实用）

一、排序算法总览

排序算法平均时间复杂度最好最坏空间复杂度稳定性适用场景/特点
冒泡排序O(n²)O(n)O(n²)O(1)稳定小规模/基本有序
选择排序O(n²)O(n²)O(n²)O(1)不稳定小规模/交换少
插入排序O(n²)O(n)O(n²)O(1)稳定小规模/基本有序
希尔排序O(n^1.3~2)O(n)O(n²)O(1)不稳定中等规模/优化插入
归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定大规模/链表/外部排序
快速排序O(nlogn)O(nlogn)O(n²)O(logn)不稳定大规模/工程常用
堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定大规模/原地排序
计数排序O(n+k)O(n+k)O(n+k)O(n+k)稳定整数/范围小
基数排序O(d(n+k))O(d(n+k))O(d(n+k))O(n+k)稳定整数/字符串/大数据
桶排序O(n)~O(n²)O(n)O(n²)O(n+k)稳定均匀分布/浮点数

稳定性：相等元素排序后相对顺序是否保持不变。
空间复杂度：是否原地排序，是否需要辅助数组。
适用场景：数据规模、分布、是否有负数、是否链表等。

二、三种元素交换方法（C++/Python）

1. 临时变量法（推荐，安全）

void swap(int &a, int &b) {int tmp = a;a = b;b = tmp;
}

def swap(arr, i, j):arr[i], arr[j] = arr[j], arr[i]

2. 加减法（需防溢出，i!=j）

void swap(int &a, int &b) {if (&a == &b) return;a = a + b;b = a - b;a = a - b;
}

3. 异或法（仅限整数，i!=j）

void swap(int &a, int &b) {if (&a == &b) return;a ^= b;b ^= a;a ^= b;
}

三、十大排序算法详解

1. 冒泡排序（Bubble Sort）

原理
  • 每轮将最大（或最小）元素“冒泡”到末尾。
  • 优化：若一轮无交换，提前结束。
复杂度
  • 时间：O(n²)，最好O(n)（已排序）
  • 空间：O(1)
  • 稳定性：稳定
C++实现
void bubbleSort(vector<int>& arr) {int n = arr.size();for (int i = 0; i < n - 1; ++i) {bool swapped = false;for (int j = 1; j < n - i; ++j) {if (arr[j-1] > arr[j]) {swap(arr[j-1], arr[j]);swapped = true;}}if (!swapped) break; // 已有序，提前结束}
}
Python实现
def bubble_sort(arr):n = len(arr)for i in range(n-1):swapped = Falsefor j in range(1, n-i):if arr[j-1] > arr[j]:arr[j-1], arr[j] = arr[j], arr[j-1]swapped = Trueif not swapped:break
应用场景
  • 小规模、基本有序数组
  • 代码简单，教学常用

2. 选择排序（Selection Sort）

原理
  • 每轮选择最小（或最大）元素放到前面。
复杂度
  • 时间：O(n²)
  • 空间：O(1)
  • 稳定性：不稳定（跨越交换）
C++实现
void selectionSort(vector<int>& arr) {int n = arr.size();for (int i = 0; i < n-1; ++i) {int minIdx = i;for (int j = i+1; j < n; ++j)if (arr[j] < arr[minIdx]) minIdx = j;if (minIdx != i) swap(arr[i], arr[minIdx]);}
}
Python实现
def selection_sort(arr):n = len(arr)for i in range(n-1):min_idx = ifor j in range(i+1, n):if arr[j] < arr[min_idx]:min_idx = jif min_idx != i:arr[i], arr[min_idx] = arr[min_idx], arr[i]
应用场景
  • 小规模、交换次数少
  • 不要求稳定性

3. 插入排序（Insertion Sort）

原理
  • 每次将一个元素插入到已排序部分的合适位置。
复杂度
  • 时间：O(n²)，最好O(n)
  • 空间：O(1)
  • 稳定性：稳定
C++实现
void insertionSort(vector<int>& arr) {int n = arr.size();for (int i = 1; i < n; ++i) {int key = arr[i], j = i - 1;while (j >= 0 && arr[j] > key) {arr[j+1] = arr[j];--j;}arr[j+1] = key;}
}
Python实现
def insertion_sort(arr):n = len(arr)for i in range(1, n):key = arr[i]j = i - 1while j >= 0 and arr[j] > key:arr[j+1] = arr[j]j -= 1arr[j+1] = key
应用场景
  • 小规模、基本有序
  • 链表排序

4. 希尔排序（Shell Sort）

原理
  • 分组插入排序，逐步缩小gap，最终gap=1变插入排序。
  • 增量序列影响复杂度（Shell/Hibbard/Knuth/Sedgewick等）。
复杂度
  • 时间：O(n^1.3~2)，依赖gap序列
  • 空间：O(1)
  • 稳定性：不稳定
C++实现（Shell增量）
void shellSort(vector<int>& arr) {int n = arr.size();for (int gap = n/2; gap > 0; gap /= 2) {for (int i = gap; i < n; ++i) {int temp = arr[i], j = i;while (j >= gap && arr[j-gap] > temp) {arr[j] = arr[j-gap];j -= gap;}arr[j] = temp;}}
}
Python实现
def shell_sort(arr):n = len(arr)gap = n // 2while gap > 0:for i in range(gap, n):temp = arr[i]j = iwhile j >= gap and arr[j-gap] > temp:arr[j] = arr[j-gap]j -= gaparr[j] = tempgap //= 2
应用场景
  • 中等规模
  • 插入排序的优化

5. 归并排序（Merge Sort）

原理
  • 分治法，递归分成两半，合并时排序。
复杂度
  • 时间：O(nlogn)
  • 空间：O(n)（非原地）
  • 稳定性：稳定
C++实现
void merge(vector<int>& arr, int l, int m, int r) {vector<int> left(arr.begin()+l, arr.begin()+m+1);vector<int> right(arr.begin()+m+1, arr.begin()+r+1);int i = 0, j = 0, k = l;while (i < left.size() && j < right.size())arr[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];while (i < left.size()) arr[k++] = left[i++];while (j < right.size()) arr[k++] = right[j++];
}
void mergeSort(vector<int>& arr, int l, int r) {if (l >= r) return;int m = l + (r-l)/2;mergeSort(arr, l, m);mergeSort(arr, m+1, r);merge(arr, l, m, r);
}
Python实现
def merge_sort(arr):if len(arr) <= 1:return arrmid = len(arr)//2left = merge_sort(arr[:mid])right = merge_sort(arr[mid:])res = []i = j = 0while i < len(left) and j < len(right):if left[i] <= right[j]:res.append(left[i])i += 1else:res.append(right[j])j += 1res.extend(left[i:])res.extend(right[j:])return res
应用场景
  • 大规模、链表排序
  • 外部排序（磁盘/大数据）

6. 快速排序（Quick Sort）

原理
  • 分治法，选主元分区，递归排序两侧。
  • 主元选取方式影响性能（首位/随机/三数取中）。
复杂度
  • 时间：O(nlogn)，最坏O(n²)
  • 空间：O(logn)（递归栈）
  • 稳定性：不稳定
C++实现（随机主元）
int partition(vector<int>& arr, int l, int r) {int pivot = arr[l];int i = l+1, j = r;while (true) {while (i <= j && arr[i] < pivot) ++i;while (i <= j && arr[j] > pivot) --j;if (i >= j) break;swap(arr[i++], arr[j--]);}swap(arr[l], arr[j]);return j;
}
void quickSort(vector<int>& arr, int l, int r) {if (l >= r) return;int mid = l + rand() % (r-l+1);swap(arr[l], arr[mid]);int p = partition(arr, l, r);quickSort(arr, l, p-1);quickSort(arr, p+1, r);
}
Python实现
import random
def quick_sort(arr, l, r):if l >= r:returnpivot_idx = random.randint(l, r)arr[l], arr[pivot_idx] = arr[pivot_idx], arr[l]pivot = arr[l]i, j = l+1, rwhile True:while i <= j and arr[i] < pivot:i += 1while i <= j and arr[j] > pivot:j -= 1if i >= j:breakarr[i], arr[j] = arr[j], arr[i]i += 1j -= 1arr[l], arr[j] = arr[j], arr[l]quick_sort(arr, l, j-1)quick_sort(arr, j+1, r)
应用场景
  • 工程常用，STL/Java/Python底层排序
  • 大规模、内存排序

7. 堆排序（Heap Sort）

原理
  • 构建大顶堆，每次取堆顶与末尾交换，重建堆。
复杂度
  • 时间：O(nlogn)
  • 空间：O(1)
  • 稳定性：不稳定
C++实现
void heapify(vector<int>& arr, int n, int i) {int largest = i, l = 2*i+1, r = 2*i+2;if (l < n && arr[l] > arr[largest]) largest = l;if (r < n && arr[r] > arr[largest]) largest = r;if (largest != i) {swap(arr[i], arr[largest]);heapify(arr, n, largest);}
}
void heapSort(vector<int>& arr) {int n = arr.size();for (int i = n/2-1; i >= 0; --i)heapify(arr, n, i);for (int i = n-1; i > 0; --i) {swap(arr[0], arr[i]);heapify(arr, i, 0);}
}
Python实现
def heapify(arr, n, i):largest = il, r = 2*i+1, 2*i+2if l < n and arr[l] > arr[largest]:largest = lif r < n and arr[r] > arr[largest]:largest = rif largest != i:arr[i], arr[largest] = arr[largest], arr[i]heapify(arr, n, largest)def heap_sort(arr):n = len(arr)for i in range(n//2-1, -1, -1):heapify(arr, n, i)for i in range(n-1, 0, -1):arr[0], arr[i] = arr[i], arr[0]heapify(arr, i, 0)
应用场景
  • 原地排序，内存受限
  • TopK问题（优先队列）

8. 计数排序（Counting Sort）

原理
  • 统计每个数出现次数，累加输出。
  • 适合整数、范围小。
复杂度
  • 时间：O(n+k)
  • 空间：O(n+k)
  • 稳定性：稳定（优化后）
C++实现
vector<int> countingSort(const vector<int>& arr) {if (arr.empty()) return {};int minVal = *min_element(arr.begin(), arr.end());int maxVal = *max_element(arr.begin(), arr.end());vector<int> count(maxVal-minVal+1, 0);for (int num : arr) count[num-minVal]++;vector<int> res;for (int i = 0; i < count.size(); ++i)for (int j = 0; j < count[i]; ++j)res.push_back(i+minVal);return res;
}
Python实现
def counting_sort(arr):if not arr:return []min_val, max_val = min(arr), max(arr)count = [0] * (max_val - min_val + 1)for num in arr:count[num - min_val] += 1res = []for i, c in enumerate(count):res.extend([i + min_val] * c)return res
应用场景
  • 整数、范围小
  • 计分、桶分布

9. 基数排序（Radix Sort）

原理
  • 按位（低到高/高到低）多轮计数排序。
  • 适合整数、字符串。
复杂度
  • 时间：O(d(n+k))，d为位数
  • 空间：O(n+k)
  • 稳定性：稳定
C++实现
void radixSort(vector<int>& arr) {int maxVal = *max_element(arr.begin(), arr.end());for (int exp = 1; maxVal/exp > 0; exp *= 10) {vector<int> output(arr.size()), count(10, 0);for (int num : arr) count[(num/exp)%10]++;for (int i = 1; i < 10; ++i) count[i] += count[i-1];for (int i = arr.size()-1; i >= 0; --i) {int idx = (arr[i]/exp)%10;output[--count[idx]] = arr[i];}arr = output;}
}
Python实现
def radix_sort(arr):if not arr:return []max_val = max(arr)exp = 1while max_val // exp > 0:count = [0] * 10output = [0] * len(arr)for num in arr:count[(num // exp) % 10] += 1for i in range(1, 10):count[i] += count[i-1]for i in range(len(arr)-1, -1, -1):idx = (arr[i] // exp) % 10output[count[idx]-1] = arr[i]count[idx] -= 1arr = output[:]exp *= 10return arr
应用场景
  • 大量整数、字符串排序
  • 电话号码、身份证号等

10. 桶排序（Bucket Sort）

原理
  • 划分区间到多个桶，桶内排序，合并输出。
  • 适合均匀分布、浮点数。
复杂度
  • 时间：O(n)~O(n²)
  • 空间：O(n+k)
  • 稳定性：取决于桶内排序
C++实现
void bucketSort(vector<float>& arr) {int n = arr.size();vector<vector<float>> buckets(n);for (float num : arr) {int idx = n * num; // 假设[0,1)buckets[idx].push_back(num);}for (auto& bucket : buckets)sort(bucket.begin(), bucket.end());int idx = 0;for (auto& bucket : buckets)for (float num : bucket)arr[idx++] = num;
}
Python实现
def bucket_sort(arr):n = len(arr)buckets = [[] for _ in range(n)]for num in arr:idx = int(n * num)  # 假设[0,1)buckets[idx].append(num)for bucket in buckets:bucket.sort()res = []for

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

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

相关文章

零基础 “入坑” Java--- 七、数组（二）

零基础 “入坑” Java--- 七、数组（二）

文章目录 一、数组转字符串二、数组的拷贝三、求数组中元素的平均值四、查找数组中指定元素&#xff08;顺序查找&#xff09;五、数组排序&#xff08;冒泡排序&#xff09;六、查找数组中指定元素&#xff08;二分查找&#xff09;七、判断两个数组中的元素是否相等八、填充数…
阅读更多...
【C++ 真题】P1104 生日

【C++ 真题】P1104 生日

P1104 生日 题目描述 cjf 君想调查学校 OI 组每个同学的生日&#xff0c;并按照年龄从大到小的顺序排序。但 cjf 君最近作业很多&#xff0c;没有时间&#xff0c;所以请你帮她排序。 输入格式 输入共有 n 1 n 1 n1 行&#xff0c; 第 1 1 1 行为 OI 组总人数 n n n&…
阅读更多...
Oracle DB和PostgreSQL,OpenGauss主外键一致性的区别

Oracle DB和PostgreSQL,OpenGauss主外键一致性的区别

针对于unique索引在主外键上的表现&#xff0c;o和PG的行为确实不一致&#xff0c;测试样例&#xff1a;PG:测试1&#xff1a;test# CREATE TABLE gdb_editingtemplates ( objectid INTEGER NOT NULL, globalid VARCHAR(38) DEFAULT {00000000-0000-0000-0000-000000000000} …
阅读更多...
06.自动化测试概念

06.自动化测试概念

自动化测试概念 1. 自动化1.1 回归测试1.2 自动化分类 1.3 自动化测试金字塔2. web自动化测试3.Selenium 1. 自动化 ​ **自动化测试&#xff08;Automated Testing&#xff09;&#xff1a;**是指使用软件工具或脚本来自动执行测试任务&#xff0c;代替人工进行重复性、繁琐的…
阅读更多...
页面登录数据的加密(前端+后端)

页面登录数据的加密(前端+后端)

本加密过程使用的 AESRSA概要1.使用AES对传输数据进行加密AES为对称加密,加密和解决所需要的key是一样的,所以拦截到AES key就可以直接解密,所以需要结果RSA进行加密2.对AES的key进行RSA加密RSA为非对称加密,客户端只能获取到publicKey(公钥),而解密只能使用服务器的privateKey…
阅读更多...
PC端基于SpringBoot架构控制无人机(一):初识无人机控制

PC端基于SpringBoot架构控制无人机(一):初识无人机控制

一、无人机飞控系统的概述飞控&#xff08;Flight Controller&#xff09;是无人机最为核心的组成部分之一&#xff0c;负责实现无人机的自主飞行控制和稳定飞行。飞控系统的功能决定了无人机的飞行性能&#xff0c;包括飞行的稳定性、操控的响应速度、导航的精确度等。通过飞控…
阅读更多...
QT6 源（154）模型视图架构里的列表视图 QListView：先学习属性部分，

QT6 源（154）模型视图架构里的列表视图 QListView：先学习属性部分，

&#xff08;1&#xff09;属性总图&#xff0c;以及测试程序的框架 &#xff1a; 开始属性的学习 &#xff1a; &#xff08;2&#xff09; 继续属性学习 &#xff1a; &#xff08;3&#xff09; 谢谢
阅读更多...
MySQL——9、事务管理

MySQL——9、事务管理

事务管理 1、什么是事务&#xff1f;2、事务常见操作方式3、事务隔离级别4、数据库并发场景4.1、读-写4.2、RR与RC的本质区别 1、什么是事务&#xff1f; mysql是基于CS模式的&#xff0c;是一套网络服务&#xff0c;所以我们是可以在本地连接上远程服务器的mysql服务端的。my…
阅读更多...
Python之面向对象详解（一篇足矣）

Python之面向对象详解（一篇足矣）

目录 一、初阶面向对象 1. 初识面向对象 1.1 对象和self 1.2 常见成员 1.3 应用示例 将数据封装到一个对象&#xff0c;便于以后使用。 将数据封装到对象中&#xff0c;在方法中对原始数据进行加工处理。 根据类创建多个对象&#xff0c;在方法中对对象中的数据进行修改…
阅读更多...
【Qt】qml组件对象怎么传递给c++

【Qt】qml组件对象怎么传递给c++

将QML组件对象传递给C的方法 在QML和C之间传递完整的组件对象需要特殊处理&#xff0c;因为QML组件是动态创建的JavaScript对象。以下是几种有效的方法&#xff1a; 1. 使用QObject指针传递 C端设置 // MyClass.h #include <QObject> #include <QQuickItem>cla…
阅读更多...
Java基础 集合框架 List框架

Java基础 集合框架 List框架

list架构 list接口list 核心特性以及扩展Collection的体现 抽象类 AbstractList抽象类 AbstractSequentialList (简化链表的顺序访问)AbstractSequentialList 核心特点自定义实现示例代码讲解其实现原理AbstractSequentialList 总结与AbstractList的对比 List 实现类 ArrayList…
阅读更多...
2025年6月28和29日复习和预习（C++）

2025年6月28和29日复习和预习（C++）

学习笔记大纲​一、预习部分&#xff1a;数组基础​&#xff08;一&#xff09;核心知识点​数组的创建&#xff1a;掌握一维数组的声明方式&#xff0c;如int arr[5];&#xff08;创建一个包含 5 个整数的数组&#xff09;。重点在于理解数组长度需为常量&#xff0c;且在声明…
阅读更多...
【centos8服务如何给服务器开发3306端口】

【centos8服务如何给服务器开发3306端口】

在 CentOS 8 中开放 MySQL 默认端口 3306&#xff0c;需要配置防火墙和 SELinux。以下是详细步骤&#xff1a; 1. 开放防火墙端口&#xff08;Firewalld&#xff09; CentOS 8 默认使用 firewalld 管理防火墙&#xff0c;执行以下命令开放 3306 端口&#xff1a; # 开放 TCP 33…
阅读更多...
python系列之：使用md5和sha256完成签名认证，调用接口

python系列之：使用md5和sha256完成签名认证，调用接口

python系列之：使用md5和sha256完成签名认证，调用接口 MD5签名和sha256签名认证md5认证代码sha256认证代码拼接签名生成签名拼接url调用接口MD5签名和sha256签名认证 MD5签名认证 算法特性： 生成128位(16字节)的哈希值计算速度快已被证明存在碰撞漏洞(不同输入可能产生相同…
阅读更多...
SpringBatch配置与入门实例

SpringBatch配置与入门实例

通过对SpringBatch基础概念的了解&#xff0c;参考&#xff1a;SpringBatch使用介绍 任何技术用起来之后&#xff0c;再去探究内部细节的原理&#xff0c;才会事半功倍。下面记录一下笔者在SpringBoot项目中集成SpringBatch&#xff0c;并且通过一个小的实例展示如何简单使用它…
阅读更多...
spdlog 项目介绍与二次封装

spdlog 项目介绍与二次封装

目录 介绍 二次封装 介绍 spdlog 是C开源的第三方日志库&#xff0c;整个项目在 spdlog 命名空间中。 在 spdlog 命名空间的 level 命名空间里定义了枚举类型&#xff0c;把日志分为了 5 个等级&#xff1a;trace debug info warn err critical enum level_enum : in…
阅读更多...
shell编程之awk命令详解

shell编程之awk命令详解

1. awk 教程 1.1 调用 awk awk 是一种强大的文本处理工具&#xff0c;在 Linux 系统中广泛应用于日志分析、数据处理等场景。调用 awk 主要有以下三种方式&#xff1a; 1.1.1 命令行方式 基本语法为&#xff1a; awk (-F filed-separator) commands input-files其中&#…
阅读更多...
服务器需要备案吗？在哪些地区需要备案？

服务器需要备案吗？在哪些地区需要备案？

&#x1f3af; 服务器是否需要备案&#xff1f; 是否需要备案&#xff0c;关键看以下两个因素&#xff1a; 服务器所在地&#xff08;机房位置&#xff09; 网站面向的访问群体&#xff08;境内或境外&#xff09; &#x1f3f7; 中国大陆&#xff08;境内&#xff09;服务器…
阅读更多...
HarmonyOS学习3---ArkUI

HarmonyOS学习3---ArkUI

1、组件 1.1、基础组件 1.2、布局容器 1.3、页面导航 1.4、其他组件 2、ArkTs/C混合开发&#xff0c;高性能编码 3、布局能力&交互归一 4、实时开发预览
阅读更多...
Java学习第十五部分——MyBatis

Java学习第十五部分——MyBatis

目录 一.概述 二.特点 三.组件 四.Mapper 五.配置文件 六.使用步骤 七.高级功能 八.优点缺点 九.项目实战 1.打开idea创建一个Java项目&#xff0c;构建系统选“Maven”​ 2.创建完成后若依赖报错&#xff0c;可通过下载或重新加载来解决​ 3.配置pom.xml文件&…
阅读更多...
最新文章

Copyright @ 2022~2023