四、快速排序
- 快速排序,英文称为Quicksort，又称划分交换排序partition-exchange sort简称快排。
- 快速排序使用分治策略来把一个序列分为两个子序列。首先从数列中挑出一个元素，并将这个元素称为「基准」pivot。重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面，相同的数可以到任何一边。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区partition操作。之后，在子序列中继续重复这个方法，直到最后整个数据序列排序完成。
- 快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)。事实上，快速排序通常明显比其他算法更快，因为它的内部循环可以在大部分的架构上很有效率地达成。
步骤
- 从数列中挑出一个元素，称为"基准"(pivot)。
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
动画演示
python代码实现如下：
五、希尔排序
- 希尔排序也称递减增量排序，是插入排序的一种改进版本，英文称为Shell Sort，效率虽高，但它是一种不稳定的排序算法。
- 插入排序在对几乎已经排好序的数据操作时，效果是非常好的；但是插入排序每次只能移动一位数据，因此插入排序效率比较低。
- 希尔排序在插入排序的基础上进行了改进，它的基本思路是先将整个数据序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全部数据进行依次直接插入排序。
步骤
- 将元素分为n列，并对每列进行插入排序。
- 将n列元素按行进行合并。
- 重复步骤1-2，其中元素的列数为上次的一半。
动画演示
python代码实现如下：
六、归并排序
- 归并排序英文称为 Merge Sort，它是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。
- 将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。
- 归并排序严格遵循从左到右或从右到左的顺序合并子数据序列, 它不会改变相同数据之间的相对顺序, 因此归并排序是一种稳定的排序算法。
步骤
- 递归分解，将数组分解成left和right。如果这两个数组内部数据是有序的（转向步骤2-4）；如果无序，则对数组进行二分，直至分解出的小组只有一个元素，此时认为该小组内部有序。
- 合并两个有序数组，比较两个数组的最前面的数，谁小就先取谁，该数组的指针往后移一位。
- 重复步骤2，直至一个数组为空。
- 最后把另一个数组的剩余部分复制过来即可。
动画演示
python代码实现如下：
