十大经典排序算法总结_算法,对半,对半直到1

算法分类：

比较类排序：插入排序，选择排序，希尔排序，冒泡排序，快速排序，堆排序，归并排序。

时间复杂度

算法总结：

1.冒泡排序：

算法的思想：

冒泡排序顾名思义，实际上每一趟之后都会使得当前最大的元素到最后面，也就是最大的次大的等等依次“浮出水面”。

算法的描述：

• 比较相邻的两个元素，如果不符合事先约定的大小顺序，我们就交换两个元素
• 重复比较相邻的两个元素，直到最后一对元素交换结束，此时最大的元素就会在最后面
• 重复上述步骤

动画演示

2.选择排序：

算法思想：

同样的顾明思义，我们总是选择当前所有元素当中最小的元素放到最前面，这就是选择排序的核心思想。

算法描述：

• 我们将数组分为两个区域，分别是，有序区和无序区，我们初始化有序区域是空，无序区域就是[0,n-1];
• 我们每一次都是从无序区域当中选择当前最小的元素放在有序区域的最后面
• 重复上述操作

动画演示：

3.插入排序

算法思想：

将数据分为两个区域，有序区域和无序区域，我们每一次从无序区域选择元素插入到有序区域当中，好比我们拿到扑克之后的洗牌操作。

算法描述：

• 从第一个元素开始，我们认为这个元素是有序的
• 去除下一个元素，在已经排序好的元素里面我们倒着遍历
• 如果当前元素大于待插入元素，我们就将当前元素后移一位
• 重复上述步骤，直到指针指向的元素小于带插入元素，或者是指针指向空
• 将待插入元素插入选定的位置
• 重复上面的操作直到整个序列变成有序的

动画演示：

4.希尔排序

算法思想：

他是建立在插入排序的基础上的，但是他是优先比较间隔较远的元素，因此又叫做缩小增量排序。其核心就是保证部分序列有序，这样就能减少移动的次数。

算法描述：

• 选择一个增量序列t1，t2，...，tk。其中序列递减，并且序列的最后一项必须是1.
• 按照增量的个数，对整个序列进行k趟排序。
• 每趟排序，根据对应的增量ti，我们对相应的若干长为ti的子序列，进行排序

动画演示：

5.归并排序

算法思想：

归并排序，实际上是采用分治算法，分而治之的思想，我使得它的最小部分有序，然后在最小部分有序的基础上，使得次小部分有序，这样最后我们就能使得最大的部分有序。

算法描述：

• 我们把长度为n的序列分为两个长度为n/2的序列
• 对两个序列分别对半分，直到每个序列当中只有一个元素
• 我们将两个排好的子序列合并成一个子序列

动画演示：

6.快速排序

算法思想：

它整体的思想就是每一趟都会选取基准点，将要排序的数据分成两部分，其中一部分比基准点小，另外一部分比基准点要大，然后按照分而治之的思想对这两部分进行同样的操作。

算法描述：

• 对于第一趟我们选取第一个元素作为基准点
• 对后面的元素进行移动，将后面的比基准点小的元素移动到前面
• 对前面的元素进行移动，将前面的比基准点大的元素移动到后面
• 重复二三操作，直到最后找到基准点的位置
• 以这一次的基准点为轴线，划分为两部分，对划分出来的两个部分进行同样的操作

动画演示：

7.堆排序

算法思想：

堆排序是建立堆得基础上的，我们根据需要构建最大堆或者是最小堆，那么堆的顶部的元素对应的就是最大或者是最小值。

算法描述：

• 首先我们根据给出的序列构建堆
• 然后将堆顶元素与数组的最后一个元素进行交换
• 重新维护堆
• 重复上面的二三操作，直到排序完成

动画演示：

8.计数排序

算法思想：

顾名思义算法的思想很简单，我们需要记录输入数据的最大值与最小值，我们需要统计最大值与最小值之间的所有元素的出现次数，最后我们遍历一次记录数组就可以得到最后的顺序。

算法描述：

• 对于输入的数据我们统计每个元素对应值的出现次数
• 遍历记录数组，按照出现次数依次输出

动画演示：

9.桶排序

算法思想：

将给出的数据分为多个部分，然后对于每个部分内部进行排序，使其部分内部有序，然后我们需要对所有的部分从小到大依次获取其中的有序元素即可，当所分出的部分的数目等于不同数据的个数的时候实际上类似与计数排序。

算法描述：

• 将数据分成多个部分
• 将每个部分进行内部排序
• 将多个部分进行合并

动画演示：

10.基数排序

算法思想：

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。

算法描述：

• 首先我们对于每个元素的最低位进行划分，然后收集，这个时候的各个元素的个位就是有序的
• 第二次我们需要对各个元素的次低位进行划分，然后收集，这个时候各个元素在次低位有序的基础上，最低位有序
• 重复直到最高位有序

动画演示：

动画演示