十大排序算法小结

青旅半醒 2022-05-22 12:39 154阅读 0赞

相关博客：

[排序算法：冒泡排序、插入排序、选择排序、希尔排序][Link 1]

[排序算法：归并排序、快速排序][Link 2]

[排序算法：桶排序、计数排序、基数排序][Link 3]

[排序算法：堆排序][Link 4]

--------------------

前面学习了10中最基本的排序算法，这篇博客主要是对这10种排序算法的小结：

**1、这十种排序算法可以分为两大类：**

（1）非线性时间排序算法：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。这类算法包括：冒泡排序、插入排序、选择排序、希尔排序、归并排序、快速排序、堆排序。

（2）线性时间非比较类排序算法：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。 这类算法包括：桶排序、计数排序、基数排序。不过，虽然这几种算法的时间复杂度比较低，但是他们对要排序的数据要求也比较苛刻。

**2、复杂度分析：**

<table> 
 <tbody> 
 <tr> 
 <td style="text-align:center;vertical-align:middle;">&nbsp;</td> 
 <td style="text-align:center;vertical-align:middle;">排序方法</td> 
 <td style="text-align:center;vertical-align:middle;">最好时间复杂度</td> 
 <td style="text-align:center;vertical-align:middle;">最坏时间复杂度</td> 
 <td style="text-align:center;vertical-align:middle;">平均时间复杂度</td> 
 <td style="text-align:center;vertical-align:middle;">空间复杂度</td> 
 <td style="text-align:center;vertical-align:middle;">稳定性</td> 
 </tr> 
 <tr> 
 <td colspan="1" style="text-align:center;vertical-align:middle;width:78px;"> 非线性 时间排 序算法 </td> 
 <td style="text-align:center;vertical-align:middle;">冒泡排序</td> 
 <td style="text-align:center;vertical-align:middle;">O(n)</td> 
 <td style="text-align:center;vertical-align:middle;">O(n^2)</td> 
 <td style="text-align:center;vertical-align:middle;">O(n^2)</td> 
 <td style="text-align:center;vertical-align:middle;">O(1)</td> 
 <td style="text-align:center;vertical-align:middle;">稳定</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:middle;">插入排序</td> 
 <td style="text-align:center;vertical-align:middle;">O(n)</td> 
 <td style="text-align:center;vertical-align:middle;">O(n^2)</td> 
 <td style="text-align:center;vertical-align:middle;">O(n^2)</td> 
 <td style="text-align:center;vertical-align:middle;">O(1)</td> 
 <td style="text-align:center;vertical-align:middle;">稳定</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:middle;">选择排序</td> 
 <td style="text-align:center;vertical-align:middle;">O(n^2)</td> 
 <td style="text-align:center;vertical-align:middle;">O(n^2)</td> 
 <td style="text-align:center;vertical-align:middle;">O(n^2)</td> 
 <td style="text-align:center;vertical-align:middle;">O(1)</td> 
 <td style="text-align:center;vertical-align:middle;">不稳定</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:middle;">希尔排序</td> 
 <td style="text-align:center;vertical-align:middle;">O(n)</td> 
 <td style="text-align:center;vertical-align:middle;">O(n^2)</td> 
 <td style="text-align:center;vertical-align:middle;">O(n^1.3)</td> 
 <td style="text-align:center;vertical-align:middle;">O(1)</td> 
 <td style="text-align:center;vertical-align:middle;">不稳定</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:middle;">归并排序</td> 
 <td style="text-align:center;vertical-align:middle;">O(nlogn)</td> 
 <td style="text-align:center;vertical-align:middle;">O(nlogn)</td> 
 <td style="text-align:center;vertical-align:middle;">O(nlogn)</td> 
 <td style="text-align:center;vertical-align:middle;">O(n)</td> 
 <td style="text-align:center;vertical-align:middle;">稳定</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:middle;">快速排序</td> 
 <td style="text-align:center;vertical-align:middle;">O(nlogn)</td> 
 <td style="text-align:center;vertical-align:middle;">O(n^2)</td> 
 <td style="text-align:center;vertical-align:middle;">O(nlogn)</td> 
 <td style="text-align:center;vertical-align:middle;">O(1)</td> 
 <td style="text-align:center;vertical-align:middle;">不稳定</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:middle;">堆排序</td> 
 <td style="text-align:center;vertical-align:middle;">O(nlogn)</td> 
 <td style="text-align:center;vertical-align:middle;">O(nlogn)</td> 
 <td style="text-align:center;vertical-align:middle;">O(nlogn)</td> 
 <td style="text-align:center;vertical-align:middle;">O(1)</td> 
 <td style="text-align:center;vertical-align:middle;">不稳定</td> 
 </tr> 
 <tr> 
 <td colspan="1" style="text-align:center;vertical-align:middle;width:78px;"> 线性时间 排序算法 </td> 
 <td style="text-align:center;vertical-align:middle;">桶排序</td> 
 <td style="text-align:center;vertical-align:middle;">O(n)</td> 
 <td style="text-align:center;vertical-align:middle;">O(n^2)</td> 
 <td style="text-align:center;vertical-align:middle;">O(n)</td> 
 <td style="text-align:center;vertical-align:middle;">O(n+k)</td> 
 <td style="text-align:center;vertical-align:middle;">稳定</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:middle;">计数排序</td> 
 <td style="text-align:center;vertical-align:middle;">O(n+k)</td> 
 <td style="text-align:center;vertical-align:middle;">O(n+k)</td> 
 <td style="text-align:center;vertical-align:middle;">O(n+k)</td> 
 <td style="text-align:center;vertical-align:middle;">O(n+k)</td> 
 <td style="text-align:center;vertical-align:middle;">稳定</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:middle;">基数排序</td> 
 <td style="text-align:center;vertical-align:middle;">O(n*k)</td> 
 <td style="text-align:center;vertical-align:middle;">O(n*k)</td> 
 <td style="text-align:center;vertical-align:middle;">O(n*k)</td> 
 <td style="text-align:center;vertical-align:middle;">O(n+k)</td> 
 <td style="text-align:center;vertical-align:middle;">稳定</td> 
 </tr> 
 <tr> 
 <td colspan="7" style="text-align:center;vertical-align:middle;width:78px;">其中k为桶的数量</td> 
 </tr> 
 </tbody> 
</table>

### 二、算法主要思想： ###

**1、冒泡排序：**

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系的要求。如果不满足就让它俩互换位置。一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作。

**2、插入排序：**

将数组的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。算法的核心思想就是，取未排序区间中的元素，在已排序区间中找到合适的位置将其插入，并保证已排序区间的数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

**3、选择排序：**

选择排序的实现思路和插入排序类似，也分为已排序区间和未排序区间。但是选择排序每次会从未排序区间中选择最小（最大）的元素，存放已排序区间的末尾。重复此操作，直到所有元素排序完毕。

上面三种排序的时间复杂度都是O(n^2)，比较高，适合小规模数据的排序。

**4、希尔排序：**

希尔排序是简单插入排序的改进版。他与插入排序的不同之处在于，它会优先比较较远的元素。希尔排序又叫缩小增量排序。希尔排序的核心在于间隔序列的设定（也就是增量）。既可以提前设定好间隔序列，也可以动态定义间隔序列。

**5、归并排序：**

归并排序的采用分治思想，如果要排序一个数组，我们先把数组从中间分成前后两个部分，然后对前后两个部分分别进行排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。核心是merge()合并函数。

**6、快速排序：**

快速排序也是利用分治思想。如果要排序一组数据，我们先选择这组数据中任意一个数据作为分区点pivot，然后遍历这组数据，将小于分区点pivot的放到左边，大于分区点pivot的放到右边，将pivot放到中间。然后再分别对左右两部分进行排序。核心是partition()函数。

**7、堆排序：**

堆排序是指利用堆这种数据结构进行排序的一种算法，堆排序分为建堆和排序两大步骤。堆需要满足一下两个特性：

①堆是一种完全二叉树，也就是除了最后一层，其他层的节点个数都是满的，最后一个节点都靠左排列。所以可以使用数组来存储堆中每个节点的值

②堆中每一个节点的值都必须大于等于（或小于等于）其左右子节点的值。

（1）首先对要排序的数据进行建堆。建堆结束后，数组中的数据已经是按照大顶堆的特性组织的。数组中的第一个元素就是堆顶（即最大值）。

（2）将堆顶元素a\[1\]与最后一个元素a\[n\]交换，这时，最大元素就放到了下标为n的位置。

（3）重新堆化：交换后新的堆顶可能违反堆的性质，需要重新进行堆化。

（4）重复(2)(3)操作，直到最后堆中只剩下下标为1的元素，排序就完成了。

**8、桶排序：**

桶排序的核心思想就是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶排序完之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

适用场景：首先，要排序的数据需要很容易就能划分成m个桶，并且，桶与桶之间有着天然的大小顺序。这样每个桶内数据都排序完之后，桶与桶之间的数据不需要在进行排序。其次，数据在各个桶之间的分布比较均匀的。所以，桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。

**9、计数排序：**

计数排序可以看成是桶排序的一种特殊情况，只是桶的大小粒度不一样。当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。

适用场景：计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。

**10、基数排序：**

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，因为基数要借助桶排序或者计数排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了。

[Link 1]: https://blog.csdn.net/a745233700/article/details/86683603
[Link 2]: https://blog.csdn.net/a745233700/article/details/86689225
[Link 3]: https://blog.csdn.net/a745233700/article/details/86693150
[Link 4]: https://blog.csdn.net/a745233700/article/details/86696956