排序算法

概念

稳定性: 任意两个相等的元素, 在排序前后的相对位置没有发生改变, 那么就认为这是一个稳定的排序算法(关键是如何处理相等数据)

排序定理:

逆序对 : 若i<j , arr[i] > arr[j] , 则(i,j) 称为一对逆序对

T(N,I) = O(N+I) N: 规模 I:逆序对数

冒泡排序和插入排序主要思想是消除逆序对, 受到逆序对影响大, 适合于规模小, 基本有序的数据

优化算法 : 每次消除多个逆序对

选择排序 : 构建有序数组, 不需要额外空间

排序算法和时间复杂度比较

类型	最坏时间复杂度	平均时间复杂度	适用场景	稳定性
冒泡排序	O(n^2)	O(n^2)	规模小, 基本有序	稳定
插入排序(扑克牌)	O(n^2)	O(n^2)	规模小, 基本有序	稳定
选择排序	O(n^2)	O(n^2)	规模小, 基本有序	稳定
快速排序	Ο(n^2)	O(nlogn)	大数据 + 随机性强	不稳定
希尔排序				不稳定
归并排序	O(nlogn)	O(nlogn) S(n)	基本有序, 数据结构不支持随机访问	稳定
堆排序				不稳定

其他算法:

直接插入排序
折半插入排序
直接选择排序

分析(从小到大)

冒泡排序 :

每次比较当前位置和下一个位置的值, a[i] > a[i+1] 调换位置, 一轮结束后冻结最后一个索引(已正确), 在剩余的位置进行下一轮比较, 直到找不下一个可以调换的元素

冒泡排序.gif

插入排序:

1. 分组: 将第一个元素分到G1,第二个到数组结束的部分分到G2
2. 遍历G2, 读取到一个元素先存储起来, 从后往前扫描G1
3. 若Ele_G1 > Ele_G2, 将Ele_G1往后移动一个元素, G1索引向前移动一位
4. 遇到索引<0 或 Ele_G1 <= Ele_G2, 跳出内循环, 将存储的元素放到G1最后索引位置的下一位

5. 重复以上步骤, 直到G2全部遍历完成

   
   插入排序.gif

选择排序:

1. 遍历未排序数组, 默认当前索引位置为最小值min_origin
2. 从索引开始到数组结束为子序列, 遍历子序列并找到最小值min_real
3. 检查min_origin是否等于min_real, 若不是则对换两个元素
4. min_origin向后移动一位, 得到新的子序列 [min_origin+1, arr_length-1]

5. 重复以上操作直到子序列长度为1, 排序结束

   
   选择排序.gif

快速排序**:

核心思想: 划分子集, 分而治之; 左侧全部小于枢纽值, 右侧全部大于枢纽值

程序设计方法:

方案一: 创建左右数组, 遍历原数组, 小于基准值追加到左数组, 大于基准值追加到右数组

方案二: 将基准调整为最后一个元素,初始化两个指针(0, len-1) ; 左指针从左往右扫描数组直到找到大于基准值, 触发右指针从右往左扫描数组, 直到找到小于基准值; 交换左右指针所指的元素, 重复交换直到左右侧指针重合; 将基准和重合元素交换, 得到一个新数组; 以基准值为中心拆分数组为两个子数组, 递归对每次产生的子序列执行快速排序, 直到子序列的长度为1则递归完成; 合并每次迭代的结果得到完整的有序数组

优化:

1. 设定cutoff阈值, 小于等于cutoff 改为插入排序 / 冒泡排序
2. 中位数设为基准降低捕获最小值概率(移动为数组最后一个元素) 快速排序.gif
   快速排序伪代码.png

1. 以任意元素(一般是第一个元素)为基准数, 创建两个指针A,B分别从左往右和从右往左扫描数组, 从指针B先开始;
2. 指针B一步步向左移动, 每次移动一位, 直到找到元素的值 < 基准值停止

实现步骤:

1. 取数组首,中,尾3个元素, 调换位置至正确, 把中间的元素设置为主元并倒数第二个元素对换
2. 排序第一个元素到倒数第二个元素

指针A扫描到大于基准就和当前指针B指向元素交换位置, 直到A + 1 =B (指针相遇)结束本轮; 此时基准数归位, 左侧子序列均小于基准数, 右侧序列均大于基准数

参考链接 :
https://blog.csdn.net/qq_40941722/article/details/94396010

https://www.codingeek.com/algorithms/quick-sort-algorithm-explanation-implementation-and-complexity/

场景 : 随机性较大, 数据量大

最坏时间复杂度: O(n2) ; 平均时间复杂度: O(nlogn)

问题点 : 只有两个元素时, 用冒泡?

归并排序:

核心: 递归合并两个有序数组, 直到整个原数组被完全合并; 分而治之, 拆分到一个元素一组, 再两两比对, 输出最小值

归并排序.png

希尔排序 :

核心: 优化的插入排序, 使得每次执行增量排序后有可能调转多个逆序对, 弥补插入排序每次只能调转1个逆序对的缺点

性质 : 每次进行更小间隔排序之后仍然保持之前排序的正确性 (先完成5间隔排序再完成3间隔排序, 3间隔排序后仍然在每5个元素组成的数组是有序的)

注意: 无论间隔增量是多少, 间隔大小总是逐渐减小的, 最后下降为1

希尔排序.png

参考链接: https://www.youtube.com/watch?v=yJjjkfnduiI