【sort】既是一种排序过程，也是一种分类过程
【稳定性】排序结果中，相同关键词的相对位置没有发生变化
内部排序
【内部排序算法分类】
| 类别 | 思想 | 种类 |
|---|---|---|
| 插入类 | 将元素插入到有序序列中 | ①直接插入排序②折半插入排序③希尔排序 ④2-路插入排序⑤表插入排序 |
| 交换类 | 在无序序列中进行两两交换，最终会在一端得到一个最值 这也就是该元素的最终位置 |
①起泡排序②快速排序 |
| 选择类 | 从无序序列中选择出最值元素，并加入到有序序列中 | ①简单选择排序②树形选择排序③堆排序 |
| 归并类 | 通过归并两个或两个以上的子序列 | ①二路归并排序 |
| 基数类 | 不需要关键字之间的比较和移动 基于多关键字排序的思想，把一个逻辑关键字拆分成多个关键字 例如：准备10个桶，编号为0-9，按照数字的某一位进行归类，然后按顺序选出 |
①基数排序 |
【性能总结】
| 性能 | 分析 |
|---|---|
| 平均时间复杂度 | 1. 快速、希尔、归并和堆排序的时间复杂度为O(nlog2n)，其他都是O(n2) 2. 特殊：基数排序O(d(n+rd))；d为关键字位数，r为一位的关键字取值范围，n为数量 【助记】 “快些以nlog2n的速度归队”：快（快速排序）、些（希尔排序）、归（归并排序）、队（堆排序） |
| 最坏时间复杂度 | 1. 快速排序的时间复杂度为O(n2) 2. 其他都和平均情况相等 |
| 最好时间复杂度 | 1. 直接插容易插变成O(n)，起泡起的好变成O(n) 2. “容易插”、“起的好”都是指初始序列已经有序 |
| 空间复杂度 | 1. 快速排序O(log2n) 2. 归并排序O(n) 3. 基数排序O(rd) 4. 其他都是O(1) |
| 稳定性 | 【助记】考研复习痛苦啊，心情不稳定（不稳定的算法），快（快速排序）些（希尔排序）选（简单选择排序）一堆（堆排序）好友来聊天吧这4种不是稳定的，其他自然都是稳定的 |
| 排序原理 | 1. 经过一趟排序，就能保证一个元素到达最终位置：起泡、快速（交换类的两种），简单选择、堆（选择类的两种） 2. 排序方法的元素比较次数和原始序列无关：简单选择排序、折半插入排序 3. 排序方法的排序趟数和原始序列有关：交换类的排序 4. 比较类的算法，最坏情况下时间复杂度至少O(log2n) |
【内部排序算法一览表】
| 类别 | 介绍 | 评价 | 平均 | 最好 | 最坏 | 空间 | 稳定性 |
|---|---|---|---|---|---|---|---|
| 直接插入排序 | 每趟选一个插入 | 已经有序的话，只要遍历一次，不需要插入 | 稳定 | ||||
| 折半插入排序 | |||||||
| 希尔排序 | 用步长划分成子序列，分别插入排序 | 不稳定 | |||||
| 冒泡排序 | 两两交换 | 已经有序的话，只要遍历一次，没有交换就结束 | 稳定 | ||||
| 快速排序 | 比小明高的站右边，矮的左边 | 越有序越费劲 | 不稳定 | ||||
| 简单选择排序 | 每趟选出一个最值 | 比较次数与初始序列无关 | 不稳定 | ||||
| 堆排序 | 用堆来选择最值 | 比较次数与初始修了有关 | 不稳定 | ||||
| 二路归并排序 | 分成n个子序列，两两序列归并 | 稳定 | |||||
| 基数排序 | 不比较，分配收集 | 稳定 |
插入类
| 算法 | 思想 | 代码 | 评价 |
|---|---|---|---|
| 直接插入排序 | 每趟将无序序列中的一个元素插入到有序序列中 插入过程中伴随着元素的移动  |
 |
【评价】时间主要浪费在交换上 【适用】适合初始序列较有序的情况 【最坏】 【最好】 【平均 【空间】 |
| 折半插入排序 | 【优化】在有序序列中采用折半查找法来查找插入位置 |  |
【评价】比较次数与初始序列无光，每次都要折半，比较次数是一定的；而关键字移动次数与直接插入排序是一样的 【适用】适合关键字较多的场景 【最坏】 |
| 希尔排序 | 又名缩小增量排序 【优化】用增量来划分子序列，在每个子序列中进行插入排序  |
 |
【增量选取规则】①增量序列的最后一个值一定取1；②增量序列中的值应尽量没有除1之外的公因子 【时间复杂度】与增量选取有关 1. 每次将增量除以2并向下取整 2. 增量 【稳定性】不稳定 |
交换类
| 算法 | 思想 | 代码 | 说明 |
|---|---|---|---|
| 冒泡排序 | 进行两两交换，一趟下来把一个最值移到了最右边  |
 |
【最坏时间复杂度】 【最好时间复杂度】 【平均时间复杂度】 |
| 快速排序 | 第一个同学出列，其他人以他为中心，比他矮的到他的左边，比他高的到他的右边  |
 |
【评价】①快速排序的排序趟数和初始序列有关；②在同级别的算法中（ 【最好】 【最坏】 【平均】 |
选择排序
| 算法 | 思想 | 代码 | 评价 |
|---|---|---|---|
| 简单选择排序 | 每趟选择出一个最值，与无序序列中的第一个交换 |
 |
【最坏时间复杂度】(n-1+1)(n-1)/2=n(n-1)/2【空间复杂度】 |
| 树形选择排序 | 又称锦标赛排序。 ①有n个待排序的元素，把它们两两一组进行比较，取出较小的 ②然后在这n/2个较小者中再两两一组进行比较，取出较小的 ③重复上述步骤，直到取出最小元素 ④这个过程用一棵满二叉树表示，在选出最小关元素后，将这个元素对应的叶子节点的值置为∞，然后把不为∞的兄弟节点移到父节点的位置  |
【时间复杂度】[log2n]+1，所以每选出一个最小元素需要进行[log2n][log2n]次比较，移动元素的次数小于等于比较次数 【评价】这种排序方法辅助存储空间较多、和“最大值”进行多余的比较等缺点。在此基础上改进诞生了堆排序 |
|
| 堆排序 | 用堆来选择最值 |
 |
【空间复杂度】就地建堆，空间复杂度为O(1) 【时间复杂度】 |
简单选择排序稳定性分析
| 情况一：交换版（默认版本） | 情况二：插入版（如果有特殊交代） | |
|---|---|---|
| 说明 | 4(1)、3、4(2)、1、5选择出最小值1，和4(1)交换 1、3、4(2)、4(1)、5 |
选出的最值插入到有序序列中 |
| 稳定性 | 不稳定 | 稳定 |
| 适合情况 | 数组 | 链表 |
归并排序
【思想】归并排序可以看作是分而治之的过程
- 把无序序列分成好几个子序列，先对每个子序列单独处理
- 之后将子序列进行归并
二路归并排序
【步骤】
- 将n个元素的无序序列分成n个序列，所以每个序列中只有一个元素
- 每个序列两两归并，形成几个有序的二元组
- 重复第二步，直到只剩下一个序列时，排序结果
【递归形式的代码】
/* 从小到大排序 */// 合并：[low, mid]、[mid+1, high]两段有序序列归并成一段有序序列void Merge(int A[], int low, int mid, int high) {int *tmpA = (int *)malloc((high-low+1)*sizeof(int)); //创建一个新空间，暂放排序结果int i=low; //第一个有序序列的指针int j=mid+1;//第二个有序序列的指针int k=0; //合并结果的指针while (i<=mid && j<=high) { //开始合并tmpA[k++] = A[i]<=A[j] ? A[i++] : A[j++];}// 处理剩余部分while (i<=mid) tmpA[k++] = A[i++];while (i<=high) tmpA[k++] = A[j++];// 将结果拷贝到A[]for (k=0, i=low; i<=high; ++i) A[i]=tmpA[k++];free(tmpA); //释放临时空间}// 归并排序：对A[]的low、high进行归并排序void MergeSort(int A[], int low, int high) {if (low < high) {int mid = (low+high)/2;MergeSort(A, low, mid); //归并前半段MergeSort(A, mid+1, high); //归并后半段Merge(A, low, mid, high); //[low, mid],[mid+1, high]合并}}
【时间复杂度】整个时间复杂度为O(nlog2n)，归并的趟数为log2n
- 归并排序中可选用merge()函数作为“归并操作”的基本操作，merge()的作用是将两个有序序列归并成一个整体有序的序列
- 归并操作即为将待归并表中的元素复制到一个存储归并结果的表中的过程
- 在顺序表中，merge()函数的归并操作执行次数为要归并的两个子序列中元素个数之和
- 归并操作如下：
- 第1趟归并需要执行2(n/2)=n次基本操作（其中2为两子序列元素个数之和，n/2为要归并的子序列对的个数；每个子序列对执行一次merge()函数，也就是2次基本操作）
- 第2趟归并需要执行4(n/4)=n次基本操作
- 第3趟归并需要执行8(n/8)=n次基本操作
- 第k趟归并需要执行2k *n/2k = n次基本操作
- 当n/2k=1时，即需要归并两个子序列长度均为原序列的一般，只需要执行一次merge()函数归并排序即可结束。此时，k=log2n，即总共需要进行log2n趟排序，每趟排序执行n次基本操作
- 整个归并排序总的基本操作执行次数为nlog2n，时间复杂度O(nlog2n)
【空间复杂度】归并排序需要转存整个待排序序列，因此空间复杂度为O(n)
基数类
基数排序
【基数排序】基数排序属于“分配式排序”，又称“桶子法”
【思想】“多关键字排序”：它是通过键值的部份资讯，将要排序的元素分配至某些“桶”中
【两种实现方法】
| 方法 | 介绍 | 例子：扑克牌 |
|---|---|---|
| 最高位优先 | 1. 先按一种规则（最高位）将数据分成若干个子序列 2. 再对每个子序列按次高位排序 |
①先准备4个桶，按花色（最高位）进行分配； ②再对每种花色13张牌进行排序（可以采用其他排序方法，也可采用最低位基数排序） |
| 最低位优先 | 不必分成子序列，每次排序全体元素都参与。可以不通过比较，而通过“分配”和“收集”来进行排序 | ①准备13个桶，按数字将牌分配到13个桶中； ②然后从第一个桶开始依次收集； ③再将收集好的牌按花色分配到4个桶中 ④然后还是从第一个桶开始依次收集 经过两次“分配”和“收集”操作，最终使牌有序 |
【最低位优先基数排序用于数字排序的步骤】从最低位开始基数排序
- 准备10个桶（先进先出的队列，从桶的上面进，下面出）
- 按关键字的个位，分流到10个桶中，然后再按顺序收集元素
- 按关键字的十位，分流到桶中，然后再按顺序收集元素
- 一直下去，直到数字最大值的最高位
【特殊符号】
- n：为序列中元素的个数
- d：为元素的关键字位数（如930，有三位数，d=3）
- rd：关键字每一位的取值范围（如关键字为930，每一位的取值都0-9，所以rd=10）
【时间复杂度】平均和最坏情况下都是O(d(n+rd))
- 基数排序的每一趟都要进行“分配”，“收集” —> n+rd
- 分配：依次对序列中每个关键字进行，即要扫描整个序列 —> n
- 收集：需要依次对每个桶进行收集，而桶的数量取决于关键字的取值范围 —> rd
- 基数排序需要d趟（关键字的位数） —> d
【空间复杂度】O(rd)：每个桶实际上是一个队列，需要头尾指针，共有rd个桶，所以需要2rd个存放指针的空间
【评价】基数排序适合的元素很多的情况，但组成元素的关键字的取值范围较小，如数字0-9是可以接受的
- 如果关键字取值范围很大，比如26个字母，并且序列中大多数元素的最高位关键字都不相同，那么这时可以考虑使用“最高位优先法”。先根据最高位排成若干子序列，然后分别对这些子序列进行直接插入排序
其他算法
二路插入排序
2-路插入排序是在折半插入排序的基础上改进的
- 目的：减少排序过程中移动记录的次数，但为此需要n个记录的辅助空间
- 缺点：2-路插入排序只能减少移动记录的次数，而不能绝对避免移动记录
- 缺点：当arr[1]是待排序记录中关键字最小或最大的记录时，2-路插入排序就完全失去了它的优越性
- 改进：若希望在排序过程中不移动记录，只有改变存储结构，进行表插入排序
【具体做法】
- 另设一个数组d[]
- 首先将arr[1]赋值给d[1]，并将d[1]看成是排好序的序列中处于中间位置的记录
- 然后从arr第2个记录起依次插入到d[1]之间或之后的有序序列中
【实现】可以将d看成是一个循环向量，并设两个指针first和final分别指示排序过程中得到的有序序列中的第一个记录和最后一个记录在d的位置
表插入排序
【表插入排序】用静态链表的方式作为待排记录序列的存储结构
【优点】避免了插入排序中，元素的移动
#define SIZE 100 //静态链表容量typedef struct{int rc;//记录项int next;//指针项}SLNode; //表结点类型typedef struct{SLNode r[SIZE]; //0号单元为表头结点int length; //链表当前长度}SLinkListType; //静态链表类型void Arrange(SLinikListType &SL){//根据静态链表SL中各结点的指针调整记录位置，使得SL中记录按关键字非递减有序顺序排列int p = SL.r[0].next; // p指示第一个记录的当前位置for(int i=1;i<SL.length;++i){while(p<i) p=SL.r[p].next;q = SL.r[p].next;if(p!=i){SL.r[p]←→SL.r[i];SL.r[i].next = p;}p = q;}}//Arrange
参考文章
若有收获，就点个赞吧
0 人点赞
