排序算法

数据结构8种排序时间和空间复杂度对比
七大查找算法
学了这么多年算法，你还不知道时间复杂度和空间复杂度如何计算吗？
排序算法上——冒泡排序、插入排序和选择排序 --- 棒棒的！
九种排序算法的可视化及比较
【算法】8种排序算法（Java）

算法动态演示：
排序算法演示
Comparison Sorting Algorithms

1、冒泡排序，稳定
在冒泡排序时，计算机从右向左遍历数组，比较相邻的两个元素。如果两个元素的顺序是错的，那么sorry，请两位互换。如果两个元素的顺序是正确的，则不做交换。经过一次遍历，我们可以保证最小的元素(泡泡)处于最左边的位置。

然而，经过这么一趟，冒泡排序不能保证所有的元素已经按照次序排列好。我们需要再次从右向左遍历数组元素，进行冒泡排序。这一次遍历，我们不用考虑最左端的元素，因为该元素已经是最小的。遍历结束后，继续重复扫描…… 总共可能进行n-1次的遍历。

如果某次遍历过程中，没有发生交换，bingo，这个数组已经排序好，可以中止排序。如果起始时，最大的元素位于最左边，那么冒泡算法必须经过n-1次遍历才能将数组排列好，而不能提前完成排序。

2、直接插入排序，稳定
对于起始数组来说，我们认为最初，有一名学生，也就是最左边的元素(i=0)，构成一个有序的队伍。

随后有第二个学生(i=1)加入队伍，第二名学生交换到应在的位置；随后第三个学生加入队伍，第三名学生交换到应在的位置…… 当n个学生都加入队伍时，我们的排序就完成了。

2.1、二分插入排序（Binary Insertion Sort），稳定
这是对直接插入排序的改进，由于已排好序的部分是有序的，所以我们就能使用二分查找法确定我们的插入位置，而不是一个个找，除了这点，它跟插入排序没什么区别，差别在于插入位置的确定而已，性能却能因此得到不少改善。

3、选择排序，不稳定
先找到起始数组中最小的元素，将它交换到i=0；然后寻找剩下元素中最小的元素，将它交换到i=1的位置…… 直到找到第二大的元素，将它交换到n-2的位置。这时，整个数组的排序完成。

4、希尔排序（插入排序的一种，是针对直接插入排序算法的改进），不稳定
我们在冒泡排序中提到，最坏的情况发生在大的元素位于数组的起始。这些位于数组起始的大元素需要多次遍历，才能交换到队尾。这样的元素被称为乌龟(turtle)。

乌龟元素的原因在于，冒泡排序总是相邻的两个元素比较并交换。所以每次从右向左遍历，大元素只能向右移动一位。(小的元素位于队尾，被称为兔子(rabbit)元素，它们可以很快的交换到队首。)

希尔排序是以更大的间隔来比较和交换元素，这样，大的元素在交换的时候，可以向右移动不止一个位置，从而更快的移动乌龟元素。比如，可以将数组分为4个子数组（i=4k, i=4k+1, i=4k+2, i=4k+3），对每个子数组进行冒泡排序。比如子数组i=0，4，8，12...。此时，每次交换的间隔为4。

完成对四个子数组的排序后，数组的顺序并不一定能排列好。希尔排序会不断减小间隔，重新形成子数组，并对子数组冒泡排序…… 当间隔减小为1时，就相当于对整个数组进行了一次冒泡排序。随后，数组的顺序就排列好了。

希尔排序不止可以配合冒泡排序，还可以配合其他的排序方法完成。

5、快速排序（对冒泡排序的一种改进），不稳定
我们依然考虑按照身高给学生排序。在快速排序中，我们随便挑出一个学生，以该学生的身高为参考(pivot)。然后让比该学生低的站在该学生的右边，剩下的站在该学生的左边。

很明显，所有的学生被分成了两组。该学生右边的学生的身高都大于该学生左边的学生的身高。

我们继续，在低身高学生组随便挑出一个学生，将低身高组的学生分为两组(很低和不那么低)。同样，将高学生组也分为两组(不那么高和很高)。

如此继续细分，直到分组中只有一个学生。当所有的分组中都只有一个学生时，则排序完成。

5.1、改进型快速排序（Improved Quick Sort）
快速排序的缺点是使用了递归，如果数据量很大，大量的递归调用会不会导致性能下降呢？我想应该会的，所以我打算作这么种优化，考虑到数据量很小的情况下，直接选择排序和快速排序的性能相差无几，那当递归到子数组元素数目小于30的时候，我就是用直接选择排序，这样会不会提高一点性能呢？

6、堆排序，不稳定
堆(heap)是常见的数据结构。它是一个有优先级的队列。最常见的堆的实现是一个有限定操作的Complete Binary Tree。这个Complete Binary Tree保持堆的特性，也就是父节点(parent)大于子节点(children)。因此，堆的根节点是所有堆元素中最小的。堆定义有插入节点和删除根节点操作，这两个操作都保持堆的特性。

我们可以将无序数组构成一个堆，然后不断取出根节点，最终构成一个有序数组。

7、桶排序（Bucket Sort）

这是迄今为止最快的一种排序法，其时间复杂度仅为Ο(n)，也就是线性复杂度！不可思议吧？但它是有条件的。举个例子：一年的全国高考考生人数为500万，分数使用标准分，最低100，最高900，没有小数，你把这500万元素的数组排个序。我们抓住了这么个非常特殊的条件，就能在毫秒级内完成这500万的排序，那就是：最低100，最高900，没有小数，那一共可出现的分数可能有多少种呢？一共有900-100+1=801，那么多种，想想看，有没有什么“投机取巧”的办法？方法就是创建801个“桶”，从头到尾遍历一次数组，对不同的分数给不同的“桶”加料，比如有个考生考了500分，那么就给500分的那个桶（下标为500-100）加1，完成后遍历一下这个桶数组，按照桶值，填充原数组，100分的有1000人，于是从0填到999，都填1000，101分的有1200人，于是从1000到2019，都填入101……如图：

很显然，如果分数不是从100到900的整数，而是从0到2亿，那就要分配2亿个桶了，这是不可能的，所以桶排序有其局限性，适合元素值集合并不大的情况。

7.1、基数排序，稳定

基数排序是对桶排序的一种改进，这种改进是让“桶排序”适合于更大的元素值集合的情况，而不是提高性能。它的思想是这样的，比如数值的集合是8位整数，我们很难创建一亿个桶，于是我们先对这些数的个位进行类似桶排序的排序（下文且称作“类桶排序”吧），然后再对这些数的十位进行类桶排序，再就是百位……一共做8次，当然，我说的是思路，实际上我们通常并不这么干，因为C++的位移运算速度是比较快，所以我们通常以“字节”为单位进行桶排序。但下图为了画图方便，我是以半字节（4
bit）为单位进行类桶排序的，因为字节为单位进行桶排得画256个桶，有点难画，如图：

8、归并排序，稳定

其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。

总结