基础算法之八大排序算法总结

文章目录

• • 稳定性
  • 插入排序
  • • 直接插入排序
    • 希尔排序
  • 交换排序
  • • 冒泡
    • 快排
  • 选择排序
  • • 简单选择排序
    • 堆排序
  • 归并排序
  • 基数排序

稳定性

如果排序后，相对位置不变，表示这个算法是稳定的。

插入排序

直接插入排序

插入排序就是把后面的数插入前面已拍好序的部分。

稳定的

希尔排序

当数组比较长的时候，直接插入排序效率不高，可能需要多次交换，研究发现，直接排序在数组长度比较小的时候，效率比较高。这个规律是希尔发现的，所以希尔排序就是解决直接插入排序的在数组比较长的时候效率不高的问题。

希尔排序的大概思路是，按照步长 k 将原来的 k 组，第一组为 0,k,2*k … 把这 k 组，每组做一次直接插入排序。然后减小步长，然后对新的组做直接插入排序，直到步长为 1 。

交换排序

冒泡

2 层循环，外层循环表示要比较的轮数，内层循环表示每轮比较的时候，如果左边比右边大，就交换。这样一轮下来，最右边的就是最大的。就像气泡在水里面冒出来。

是稳定的。

快排

某个元素作为参考，使比此元素小的都在此元素左边，比此元素大的都在此元素右边。然后分别对左边部分和右边部分做相同的处理。

一般以中间元素作为参照，然后有 left 和 right 分别指向左右，依次遍历，当 left 比参照大的时候互相交换，然后从 right 开始向左扫描，当 right 比参照小的时候，相互交换。然后以此循环，直到 left == right ，表示一轮扫描完成，然后分别把参照的左右两部分按照之前的规则扫描。

一般递归实现。

不稳定

选择排序

简单选择排序

和冒泡有些类似， 2 层循环，外层循环表示需要查找的轮数，内层循环表示每轮循环的时候，找出最小的和剩余的位排序部分的第一个。

堆排序

构造一个堆，使父节点永远是左右子树里面最大或者最小的。

归并排序

把数组分为 2 部分，然后依次排序，拍好序后合并。

可递归实现

基数排序

把所有的数，高位不足的补 0 ，使得每个元素的长度一致，然后从低位开始，安装数值的大小排序。最高位排好序后，就完成了排序。

参考资料：算法和数据结构学习-八种必需掌握的排序