排序算法

2020-05-07 本文已影响0人 X1_blog

概念

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

排序定理:

逆序对 : 若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

插入排序:

分组: 将第一个元素分到G1,第二个到数组结束的部分分到G2
遍历G2, 读取到一个元素先存储起来, 从后往前扫描G1
若Ele_G1 > Ele_G2, 将Ele_G1往后移动一个元素, G1索引向前移动一位
遇到索引<0 或 Ele_G1 <= Ele_G2, 跳出内循环, 将存储的元素放到G1最后索引位置的下一位
重复以上步骤, 直到G2全部遍历完成

插入排序.gif

选择排序:

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

选择排序.gif

快速排序**:

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

程序设计方法:

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

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

优化: