2.0 排序算法

排序算法有很多，目前使用的比较多的有8种，分别是：

1. 冒泡排序(bubble sort)

2. 选择排序(select sort)：对冒泡排序的优化

3. 插入排序(insert sort)：又可细分为直接插入排序、二分插入排序

4. 希尔排序(shell sort)：对插入排序的优化，本身也是插入排序的一种，由于优化后的效率得到极大的提升，通常单独列出

5. 归并排序(merge sort)

6. 快速排序(quick sort)

7. 基数排序(radix sort)/桶排序(bucket sort)

8. 堆排序(heap sort):利用了堆(一种特殊的二叉树)这种数据结构，某种程度上，也可以认为是插入排序的一种特例

这些算法的排序时间复杂度各不相同  

• 其中冒泡排序、选择排序、插入排序的时间复杂度都是O(N²)

• 希尔排序的时间复杂度是O(N*(logN)²)

• 归并排序、快速排序、堆排序的时间复杂度都是O(N*logN)

• 基数排序的时间复杂度可以达到O(N)

在比较不同的排序算法的效率时，相同量级时间复杂度的排序算法，需要比较系数，不同量级的算法，肯定是量级越低，效率越高，下面是这些算法效率由低到高的排序：

在本章中，将会按照这个顺序逐一介绍每一个算法