数据结构学习笔记 - 排序

雨点打透心脏的1/2处 2022-12-25 04:57 95阅读 0赞

## 排序 ##

### 简介 ###

排序算法有很多, 最经典最常用的有  
冒泡排序, 插入排序, 选择排序, 时间复杂度 O(n平方)  
快速排序, 归并排序, 时间复杂度O(nlogn)  
桶排序, 计数排序, 基数排序, 时间复杂度O(n)

### 分析排序算法 ###

*  执行效率

1.  最好情况, 最坏情况, 平时情况时间复杂度
2.  时间复杂度的系数, 常数, 低阶
3.  元素比较次数和移动次数

*  内存消耗  
    可以通过空间复杂度来衡量
 *  稳定性  
    稳定排序算法可以保持数值相同的两个对象, 在排序之后的前后顺序不变  
    真实开发中排序场景往往比较复杂, 有些问题借助稳定排序算法可以非常简洁的解决

### [冒泡排序][Link 1] ###

冒泡过程只涉及相邻数据的交换操作, 所以空间复杂度为O(1), 是一个原地排序算法  
且当相邻的两个元素大小相等时不交换, 相同大小的数据在排序前后不会改变顺序, 所以冒泡排序是稳定的排序算法  
最好的情况数据有序, 时间复杂度O(n), 最坏的情况数据倒序, 时间复杂度O(n平方), 平均时间复杂度为O(n平方)

### [插入排序][Link 2] ###

将数组中的元素分为已排序区和未排序区, 取未排序区元素在已排序区找到合适的位置插入, 并保证已排序区数据一直有序, 直至未排序区为空  
插入排序运行也不需要额外的存储空间, 所以空间复杂度是O(1), 是一个原地排序算法  
排序时, 对于值相同的元素可以选择将后面出现的元素插入到前面出现的元素的后面, 所以是稳定的排序算法  
最好的情况数据有序, 时间复杂度O(n), 最坏的情况数据倒序, 时间复杂度O(n平方), 平均时间复杂度为O(n平方)

### 选择排序 (todo) ###

选择排序类似插入排序, 分已排序区和未排序区, 但每次会从未排序区找到最小元素, 交换位置放到已排序区末尾  
选择排序一样空间复杂度为O(1), 是一种原地排序算法  
最好最坏和平均时间复杂度都是O(n平方)  
因为存在交换位置, 所以选择排序不是一种稳定的排序算法,

> 以上三种时间复杂度较高, 适合小规模数据排序  
> 选择排序不是稳定排序算法, 所以稍逊色于冒泡排序和插入排序, 而冒泡排序的数据交换要比插入排序的数据移动复杂, 所以这三种排序, 插入排序更为常用

### 归并排序 (todo) ###

核心思想, 先把数组从中间分成两部分, 然后对前后两部分排序, 再将排好序的两部分合并, 就得到有序的完整数组  
归并排序使用的分治思想, 分治是一种解决问题的处理思想, 递归是一种编程技巧  
用递归代码来实现归并排序  
归并排序合并过程中, 值相同的元素可以自己掌握顺序, 所以是一个稳定的排序算法  
时间复杂度为O(nlogn), 且执行效率与原始数组有序度无关, 最好最坏平均情况都是O(nlogn)  
但不是原地排序算法, 空间复杂度为O(n)

### 快速排序 (todo) ###

也采用分治思想  
假如要排序的数组, 最左下标为’左’, 最右下标为’右’, 选中间任意一个点为分区点, 下标’中’  
遍历从左到右, 将小于’中’的放到左边, 大于’中’的放到右边, 数组就被分成了三部分, '左’到’中-1’的都是小于’中’下标的元素的, ‘中+1’到’右’都是大于’中’下标元素的  
根据分治思想, 用递归继续排序’左’到’中-1’和’中+1’到’右’, 直到区间缩小为1, 则所有数据有序, 具体实现方法看源码  
原地, 不稳定排序算法, 分区过程中有交换操作, 所以相同元素顺序会变  
时间复杂度O(nlogn), 但分区极其不均匀的情况会退化为O(n平方), 平均O(nlogn)  
常用选取分区点的算法

1.  三数取中法, 从头尾中取三个数, 对比大小取中间值作为分区点
2.  随机法, 随机选择一个元素做为分区点

> 以上, 快排和归并很相似, 区别是归并排序是从下向上处理, 先处理子问题再合并, 快排是由上到下, 先分区, 再处理子问题  
> 归并时间复杂度稳定但空间复杂度高, 快排空间复杂度低, 且通过合理选择分区点可以避免时间复杂度退化为O(n平方), 所以快排应用更广泛

### 桶排序 (todo) ###

核心思想把要排序的数据分到几个有序的桶里, 每个桶里的数据再单独排序, 之后按顺序依次取出  
桶排序对排序数据要求苛刻, 要能很容易划分成m个桶, 且桶之间有大小顺序, 其次各个桶之间的数据分布均匀  
桶排序比较适合用在外部排序中, 即数据存储在外部磁盘, 数据量大, 内存有限  
比如10G订单数据, 内存100MB排序问题, 可用桶排序划分订单数据, 每个桶生成一个文件, 如果桶间数据不均匀, 找到较大的文件, 继续分桶, 直到所有文件都能读入内存

### 计数排序 (todo) ###

计数排序是桶排序的一种特殊情况  
当数据范围不大时, 最大值为k, 就分k个桶, 省去桶内排序时间, 如果k要比排序的元素个数大得多, 则不适合用计数排序  
和桶排序非常相似, 只是桶的大小粒度不一样  
实现细节稍微复杂, 见代码  
计数排序只能给非负整数排序, 如有其它类型, 则想办法在不改变相对大小前提下转化为非负整数

### 基数排序 (todo) ###

基数排序对数据有要求, 需要可以分割出独立的位来比较, 且位之间有递进的关系, 从后向前一位一位进行线性排序  
另外, 每一位的数据范围不能太大, 要可以用线性排序算法来排序, 否则时间复杂度就大于O(n)了  
针对长度不一样的, 可以在前面或后面补0  
比较两个数只需要比较高位, 高位相同再比较低位

> 以上三种都是线性时间复杂度的排序算法, 它们对要排序的数据有要求, 所以应用不是很广泛, 但如果数据特征匹配, 会非常高效, 时间复杂度可达O(n), 都是稳定非原地排序

### 总结 ###

以上都是理论知识, 生产环境中使用的排序函数通常都不是基于一种排序算法, 比如数据量小用归并排序, 数据量大用快排, 快排到区间内元素较少时改用插入排序  
为了尽可能提高性能, 通常会做很多优化

[Link 1]: https://github.com/WangDanpeng/Vamos/blob/main/src/main/scala/wdp/sort/bubble.scala
[Link 2]: https://github.com/WangDanpeng/Vamos/blob/main/src/main/scala/wdp/sort/insertion.scala