排序算法总结(十大经典排序算法)
上文中提到一个题目,必须使用比较类排序。那么比较类和非比较类的区别在哪里呢
比较类排序: 通过比较元素来决定元素间的相对次序,其时间复杂度不能突破O(nlogn)。
非比价类排序: 不通过比较,可以用线性时间运行,如桶排序,计数排序,基数排序
各排序算法的类型
-
冒泡排序
依次比较相邻元素,让元素像冒泡一样向数组头部移动
算法描述:
1比较相邻的元素,如果第一个比第二个大,则交换。
2对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数
3重复步骤2,直到某一趟中没有任何交换,则排序结束
-
选择排序
依次选出第一大的,第二大的,直到排序完成
算法描述:
-
遍历数组,找到最小的元素放到第一位
-
遍历数组,找到第二小的放到第二位
-
重复以上步骤,直到排序完成
-
插入排序
将未确定数组中拿出一个数往已确定数组中插入
算法描述
-
第一个元素认为是已经配排序
-
去除下一个元素,往前面扫描,插入合适的位置,目前已确认两个元素
-
重复以上步骤直到排序完成
-
希尔排序,又称缩小增量排序
先将整个待排序列按增量分隔成若干子序列进行插入排序,然后将增量缩小,再进行一轮排序直到增量为1
-
归并排序
该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列
算法描述
-
把长度为n的输入序列分为两个长度为n/2的序列
-
把两个子序列分别采用归并排序
-
快速排序
同样使用了分治法,从数列中挑出一个元素作为基准,将比基准小的摆在基准前面,将比基准大的摆在基准后面,形成两个子序列。递归的把子数列进行快速排序
归并和快排的区别是,归并是合并起来,快速排序是逐渐分开
算法描述
1数列中挑出一个元素,称为基准
2重新排序数列,将元素中比基准小的放在基准前面,将所有元素比基摆在基准后面
3递归子数列
-
堆排序
将数组构建成大顶堆,将大顶堆的顶部输出,重新恢复大顶堆,重复以上知道排序完成
构建大顶堆的时间复杂度为O(n)
-
计数排序
计数排序要求输入的数据必须是有确定范围的整数,统计每个数出现的次数后依次输出数组中,要求数据较为均匀
-
桶排序
利用了函数的映射关系,将数据分到有限的桶内,每个桶内在排序。要求数据较为均匀
-
基数排序
基数排序是按照低位先排序后,再按高位排序,要求数据位数差异不大