十大排序算法
– JAVA之10大排序算法
-
知识范围
- 冒泡排序
- 快速排序
- 归并排序
- 插入排序
- 希尔排序
选择排序(后续补充)堆排序(后续补充)计数排序(后续补充)桶排序(后续补充)基数排序(后续补充)
-
核心原理
-
冒泡排序
从头遍历数组, 相邻元素比较
前面元素比后面元素大(或小), 则交换这两个元素, 得到本次遍历的最后位置为最大(或最小)元素
-
快速排序
分治法将一个数组分为两个子数组
从数组中选择一个元素, 作为本数组(子数组)的基准
遍历本数组(子数组), 将小于基准元素的值交换到基准前面, 大于基准元素的值交换到后面
递归上面得到的2个子数组, 得到排序结果
-
归并排序
分治法
将长度为n的数组分为两个长度为n/2的子序列
对这两个子序列分别采用归并排序
将两个排序好的子序列合并成最终排序序列
-
插入排序
对于未排序序列,将其与已排序元素从后往前(从前往后)扫描的元素作比较, 满足大于(小于)条件时插入
从第一个元素开始, 该元素认为已经排序
取下一个元素, 与已经排序好的排序元素从后往前扫描做比较
若该元素大于排序元素, 将该元素移到下一位置
重复比较直到找到已排序的元素大于(或小于)等于该元素, 将该元素插入该位置
-
希尔排序
优先比较较远位置的元素.
选择一个增量序列: t_1, t_2, …, t_k, 其中t_i > t_j, t_k=1;
按照增量序列的个数, k个, 对序列进行k趟排序;
每趟排序中, 根据对应的增量t_i, 将待排序序列分割成若干长度为m的子序列
分别对各字表进行直接插入排序
当且仅当增量为1时, 整个序列作为一个整表排序处理
-
-
经验探秘
排序方法 平均时间复杂度 最优时间复杂度 最差时间复杂度 空间复杂度 稳定性 冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定 快速排序 O(nLog_2_^n) O(nLog_2_^n) O(n^2) O(nLog_2_^n) 不稳定 归并排序 O(nLog_2_^n) O(nLog_2_^n) O(nLog_2_^n) O(n) 稳定 插入排序 O(n^2) O(n) O(n^2) O(1) 稳定 希尔排序 O(n^m), m∈[1, 2) O(n) O(n^2) O(1) 不稳定 -
总结输出
-
冒泡排序: 可以优化, 设置交换操作的标志, 当未发生交换时, 说明后续元素已经有序, 那么退出当前循环
比较相邻元素,将大的元素放后边,小的放前边,每一轮比较,总有一个最大元素被冒到数组最后边。N轮比较下来,就完成了排序
应用场景: 数据基本有序, 且数据量较小
-
快速排序: 通常是实际应用中的最好选择排序算法
快速排序算法每次选择一个基准元素,将小于基准元素的数放到左边,大于基准元素的数放到右边,递归的重复这个划分过程,直到需要划分的数组中只有一个元素,结束递归。
应用场景: 处理大量数据排序
-
归并排序: 由于使用递归,递归深度太深容易造成内存溢出,所以可使用非递归版本归并排序
归并排序在结构上是递归的,归并排序每一次递归将原数组均分为规模较小的两个部分,直到无法再分为止,此时每一个部分只有一个元素,那么自然是有序的,于是递归开始自下往上进行合并; 合并时,新建一个数组,长度等于两个子数组长度之和,依次比较两个子数组中的元素,每次将较小的元素放进新数组即可; 对于归并排序,每一层递归将原数组均分成了两部分,于是递归树一共log_2_^n+1层,每一层最多进行n次比较,所以时间复杂度为nlog_2_^n。
应用场景: 数据量较大且要求排序稳定
-
插入排序: 基本思想类似于我们抓扑克牌
开始时,我们的左手为空,然后我们每次从牌堆中拿走一张牌并插入到正确的位置;为了找到每一张牌的正确位置,需要将它从右到左与每一张牌比较,直到找到小于它的那张牌,保证左手的牌随时都是有序的,同样N轮插入操作下来,数组有序。
**应用场景: **数据基本有序且规模较小时,选用插入排序较好
-
希尔排序: 对插入排序的一种改进, 改进思想源于序列越基本有序,插入排序效率越高
先将整个待排记录序列分割成若干列,即若干子序列,分别进行直接插入排序,待整个序列中的记录基本有序时,再对全体记录进行一次直接插入排序。
应用场景: 数据基本有序且规模较小
-
总结
- 捐赠|Donate, 实践撰文分享实属不易, 您的支持能为更多省时省事的分享提速, 谢谢!
微信 |
支付宝 |
MiXin |