排序的知识点-创新互联
前言：将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列
思维导图：
目录
一、基本概念
1.定义
2.排序的基本操作
3.排序时间复杂度
4.排序方法的稳定性
二、排序的类别
1.直接插入排序
2.希尔排序（缩小增量排序）
3.冒泡排序
4.快速排序
5.简单选择排序
6.堆排序
7.归并排序
编辑 8.基数排序
a.多关键字排序(最低位优先法LSD)
b.链式基数排序
三、总结
一、基本概念 1.定义
排序：将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。
内部排序：在排序期间数据对象全部存放在内存的排序。
外部排序：在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。
2.排序的基本操作比较：比较两个关键字的大小。
移动：将记录从一个位置移动到另一个位置。
3.排序时间复杂度排序的时间复杂度可用算法执行的记录关键字比较次数与记录移动次数来衡量。
4.排序方法的稳定性如果在记录序列中有两个记录r[i]和r[j], 它们的关键字 key[i] == key[j] , 且在排序之前, 记录r[i]排在r[j]前面。如果在排序之后, 记录r[i]仍在记录r[j]的前面, 则称这个排序方法是稳定的, 否则称这个排序方法是不稳定的。
二、排序的类别 1.直接插入排序稳定性：稳定
时间复杂度：
- 最优情况是正向排序 – O(n)
- 最差是逆向排序，每次插入都需要比较已完成数列元素的个数 – O(n^2)
空间复杂度：O(1)
过程：
注：可理解为打扑克整理牌的时候
- 希尔排序是对直接插入排序的优化。
- 当gap >1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就 会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
- 若待排记录序列为正序时，则时间复杂度可提到值O(n)。
- 稳定性：不稳定
过程：
•首先取一个整数 gap< n(待排序记录数) 作为间隔, 将全部记录分为 gap 个子序列, 所有距离为 gap 的记录放在同一个子序列中 •在每一个子序列中分别施行直接插入排序。 •然后缩小间隔 gap, 例如取 gap = gap/2 •重复上述的子序列划分和排序工作，直到最后取gap = 1, 将所有记录放在同一个序列中排序为止。
3.冒泡排序 - 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：稳定
- 时间复杂度：O(N*logN)
- 空间复杂度：O(logN)
- 稳定性：不稳定
过程：
• 一趟排序(某个子序列)过程1.从high指向的记录开始,向前找到第一个关键字的值小于Pivotkey的记录,将其放到low指向的位置,low+1
2.从low指向的记录开始,向后找到第一个关键字的值大于Pivotkey的记录,将其放到high指向的位置,high-1
3.重复1,2，直到low=high，将枢轴记录放在low(high)指向的位置
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
过程：
•每一趟(例如第i趟,i=0,1,…,n-2)在后面n-i个待排序记录中选出关键字最小的记录,与第i个记录交换
排升序要建大堆，排降序建小堆。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(1)
- 稳定性：不稳定
过程：
• 输出根结点 • 用最后结点代替根结点值 • 比较根结点与两个子结点的值，如果小于其中一个子结点，则选择大的子结点与根结点交换 • 继续将交换的结点与其子结点比较 • 直到叶子结点或者根节点值大于两个子结点
7.归并排序- . 时间复杂度：O(N*logN)
- 空间复杂度：O(N)
- 稳定性：稳定
注：这里主要讲的是2-路归并排序
过程：
• 将 n 个记录看成是 n 个有序序列 • 将前后相邻的两个有序序列归并为一个有序序列(两路归并) • 重复做两路归并操作，直到只有一个有序序列为止
8.基数排序- 时间复杂度：O(MAX(N,范围))
- 空间复杂度：O(范围)
- 稳定性：稳定
过程：
• 基数排序：借助“分配”和“收集”对单逻辑关键字进行排序的一种方法 • 链式基数排序方法：用链表作存储结构的基数排序 • 设置10个队列， f[ i ] 和 e[ i ] 分别为第 i个队列的头指针和尾指针
注：从最低位至最高位，逐位执行上述两步操作（分配和收集），最后得到一个有序序列（个位->十位->百位->....）
三、总结排序方法 | 平均时间 | 最坏情况 | 辅助存储 | 适合情况 |
插入排序 | O(n2) | O(n2) | O(1) | 记录数不很多 |
希尔排序 | O(n(log2n)2) | O(n2) | O(1) | 不太多 |
快速排序 | O(nlog2n) | O(n2) | O(log2n) | 较多 |
堆排序 | O(nlog2n) | O(nlog2n) | O(1) | 较多 |
归并排序 | O(nlog2n) | O(nlog2n) | O(n) | 都可以 |
基数排序 | O(d(n+rd)) | O(d(n+rd)) | O(rd) | 关键字位数少 |
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
分享题目：排序的知识点-创新互联
文章源于：http://cdiso.cn/article/dhoioi.html
