快速排序可以理解为挖坑排序

基本思想是：

1．先从数列中取出一个数作为基准数。

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数。

将数组的第一个数当作坑，然后从前往后比较，碰到比现在坑中小的数字，将当前位置挖成坑，并将这两个数互换，然后从后往前比较，碰到比现在坑中小的数字，将当前位置挖成坑，并将这两个数互换，然后进行递归。

|     0      |    1     |    2   |    3     |    4   |    5     |    6   |    7   |    8     |   9    |
| --------   | -----:   | :----: | -----:   | :----: | -----:   | :----: | :----: | -----:   | :----: |
|     72     |    6     |    57  |    88    |    60  |    42    |    83  |    73  |    48    |   85   |

以一个数组作为示例，取区间第一个数为基准数。 初始时，i = 0; j = 9; X = a[i] = 72

由于已经将a[0]中的数保存到X中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。

从j开始向前找一个比X小或等于X的数。当j=8，符合条件，将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++; 这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数，当i=3，符合条件，将a[3]挖出再填到上一个坑中a[8]=a[3]; j--;

数组变为：

|     0      |    1     |    2   |    3     |    4   |    5     |    6   |    7   |    8     |   9    |
| --------   | -----:   | :----: | -----:   | :----: | -----:   | :----: | :----: | -----:   | :----: |
|     48     |    6     |    57  |    88    |    60  |    42    |    83  |    73  |    88    |   85   |

i = 3; j = 7; X=72

再重复上面的步骤，先从后向前找，再从前向后找。 从j开始向前找，当j=5，符合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; i++; 从i开始向后找，当i=5时，由于i==j退出。 此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将X填入a[5]。

数组变为：

|     0      |    1     |    2   |    3     |    4   |    5     |    6   |    7   |    8     |   9    |
| --------   | -----:   | :----: | -----:   | :----: | -----:   | :----: | :----: | -----:   | :----: |
|     48     |    6     |    57  |    42    |    60  |    72    |    83  |    73  |    88    |   85   |

可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。

对挖坑填数进行总结

1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。

2．j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。

3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。

4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。

====================================================

希尔排序可以理解为跳跃排序

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

以数组{26, 53, 67, 48, 57, 13, 48, 32, 60, 50 }为例，步长序列为{5,2,1}

初始化关键字： [26, 53, 67, 48, 57, 13, 48, 32, 60, 50 ]

最后的排序结果：

13 26 32 48 48 50 53 57 60 67

====================================================

选择排序

在未排序序列中找到最小元素，存放到排序序列的起始位置 
再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。  
以此类推，直到所有元素均排序完毕。 

====================================================

插入排序

从第一个元素开始，该元素可以认为已经被排序 取出下一个元素，在已经排序的元素序列中从后向前扫描 如果该元素（已排序）大于新元素，将该元素移到下一位置 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置中
重复步骤2

====================================================

桶排序

假设待排序的数组a中共有N个整数，并且已知数组a中数据的范围[0, MAX)。在桶排序时，创建容量为MAX的桶数组r，并将桶数组元素都初始化为0；将容量为MAX的桶数组中的每一个单元都看作一个"桶"。在排序时，逐个遍历数组a，将数组a的值，作为"桶数组r"的下标。当a中数据被读取时，就将桶的值加1。例如，读取到数组a[3]=5，则将r[5]的值+1。

*桶排序的速度比快速排序还要快，因为桶排序是用空间换时间。*