排序的十种算法（十大经典排序算法）

上文中提到一个题目，必须使用比较类排序。那么比较类和非比较类的区别在哪里呢

比较类排序： 通过比较元素来决定元素间的相对次序，其时间复杂度不能突破O(nlogn)。

非比价类排序： 不通过比较，可以用线性时间运行，如桶排序，计数排序，基数排序

各排序算法的类型

• 冒泡排序

依次比较相邻元素，让元素像冒泡一样向数组头部移动

算法描述：

1比较相邻的元素，如果第一个比第二个大，则交换。

2对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数

3重复步骤2，直到某一趟中没有任何交换，则排序结束

• 选择排序

依次选出第一大的，第二大的，直到排序完成

算法描述：

1. 遍历数组，找到最小的元素放到第一位
2. 遍历数组，找到第二小的放到第二位
3. 重复以上步骤，直到排序完成

• 插入排序

将未确定数组中拿出一个数往已确定数组中插入

算法描述

1. 第一个元素认为是已经配排序
2. 去除下一个元素，往前面扫描，插入合适的位置，目前已确认两个元素
3. 重复以上步骤直到排序完成

• 希尔排序，又称缩小增量排序

先将整个待排序列按增量分隔成若干子序列进行插入排序，然后将增量缩小，再进行一轮排序直到增量为1

• 归并排序

该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列

算法描述

1. 把长度为n的输入序列分为两个长度为n/2的序列
2. 把两个子序列分别采用归并排序

• 快速排序

同样使用了分治法，从数列中挑出一个元素作为基准，将比基准小的摆在基准前面，将比基准大的摆在基准后面，形成两个子序列。递归的把子数列进行快速排序

归并和快排的区别是，归并是合并起来，快速排序是逐渐分开

算法描述

1数列中挑出一个元素，称为基准

2重新排序数列，将元素中比基准小的放在基准前面，将所有元素比基摆在基准后面

3递归子数列

• 堆排序

将数组构建成大顶堆，将大顶堆的顶部输出，重新恢复大顶堆，重复以上知道排序完成

构建大顶堆的时间复杂度为O(n)

• 计数排序

计数排序要求输入的数据必须是有确定范围的整数，统计每个数出现的次数后依次输出数组中，要求数据较为均匀

• 桶排序

利用了函数的映射关系，将数据分到有限的桶内，每个桶内在排序。要求数据较为均匀

• 基数排序

基数排序是按照低位先排序后，再按高位排序，要求数据位数差异不大

十大排序顺口溜：快速冒泡，希尔插入，归并，选择堆，桶和计数，对比基数

故事解释：扫地比赛，为了报名快速冒泡，希尔（人名）插入队伍，归并地上的垃圾，选择别人的垃圾堆，放进桶里进行计数，对比重量基数后获胜。