1、常见的排序算法
1.1 交换排序基本思想
冒泡排序属于交换排序之一，我们先来了解以下冒泡排序思想。
基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
2、快速排序的实现方法
递归实现与二叉树的前序遍历很相似，将区间划分为左右两半部分的常见方式有三种：1.hoare版本；2.挖坑法；3.左右指针法。
2.1 基本思想
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中
的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右
子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止 。
所以，在后面很重要的一点就是，左边走找小，右边走找大。
3 hoare（霍尔）版本
3.1 实现思路
我们规定排升序，排序数组名称为a，基准值 key，基准值下标 keyi，左 left，右 right。
1.选出一个key，key可以是需要排序的数组中任意一个元素，我们本篇文章选key为a[left]；
2.从数组右端（尾部）往左走，当a[right] < key(a[keyi])，right停下来；
3.然后从数组左端（首部）往右走，当a[left] > key(a[keyi])，left停下来；
4.交换a[left], a[right]；
5.循环步骤2、3、4，当 left与right 走到相同位置时，交换此位置的元素与 key，key 的位置就确定了。
6.此时 key 就将数组分为了左右两个区间，我们对左右两个区间分别使用前5步，然后再次确定了左右区间的key，递归左区间，再递归右区间，就实现了排序。
注意：步骤2、3的顺序不能换。至于为什么，我们思路图解后再说。
3.2 思路图解
我们的图解就是按照实现思路来画的。
3.3 为什么实现思路的步骤2、3不能交换
我们可以看到，思路图解里，当最后找到 3 时候是 R 先走，R先遇到 3，如果是 L 先走，左找大，L 遇见 3 不会停下来，会直接走到R的位置，R 位置是 9，这时候相遇，就交换，一旦交换，左区间就不是全部小于 key（6）了，这就会出现错误。因此，key 如果选在左边，右边先走。
Q：hoare版本我们是理解了，如果key选在右边，那是不是左边先走呢？
A：答案是一定的。这里其实就是 L遇到R 还是 R遇到L 的问题。我们依然可以用上面的解法来想这问题，当L遇到R 时，说明 R 已经停下，R 停下就是 a[right]<key，这时 L遇到R，相遇位置就是小于 key 的位置，交换（key，a[left]），这时最后一个小于 key 的元素就放在了最左边，而 key 就到了确定的位置，不用再调了，以key 为中点的左区间全部小于 key，右区间全大于 key；
key在右边，当 R遇到L 时，说明 L 已经停下，L 停下就是 a[left]>key，这时 R遇到L，相遇位置就是大于 key 的位置，交换（a[left]，key），这时最后一个大于 key 的元素就放在了最右边，而 key 就到了确定的位置，不用再调了，以 key 为中点的左区间全部小于 key，右区间全大于 key。
所以如果 key 选在左边，就先走右边；key 选在右边，就先走左边。
3.4 hoare版本代码实现
// 快速排序hoare版本 int PartSort1(int* a, int left, int right) { int keyi = left; while (left < right) { //右边找小 while (left < right && a[right] >= a[keyi]) { right--; } //左边找大 while (left < right && a[left] <= a[keyi]) { left++; } Swap(&a[left], &a[right]); } Swap(&a[keyi], &a[left]); return left; } void QuickSort(int* a, int left, int right) { if (left >= right) return; int keyi = PartSort1(a, left, right); QuickSort(a, left, keyi - 1); QuickSort(a, keyi + 1, right); }
3.5 hoare版本代码测试
void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } void Print(int* a, int n) { for (int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } //快速排序递归实现 //快速排序hoare版本 int PartSort1(int* a, int left, int right) { int keyi = left; while (left < right) { //右边找小 while (left < right && a[right] >= a[keyi]) { right--; } //左边找大 while (left < right && a[left] <= a[keyi]) { left++; } Swap(&a[left], &a[right]); } Swap(&a[left], &a[keyi]); return left; } void QuickSort(int* a, int left, int right) { if (left >= right) return; int keyi = PartSort1(a, left, right); QuickSort(a, left, keyi - 1); QuickSort(a, keyi + 1, right); } void test() { int a[] = { 6,3,2,1,5,7,9 }; QuickSort(&a, 0, sizeof(a) / sizeof(int) - 1); Print(&a, sizeof(a) / sizeof(int)); } int main() { test(); return 0; }
4、挖坑法
4.1 实现思路
我们规定排升序，排序数组名称为a，基准值 key，左 left，右 right。
1.选出一个key，key可以是需要排序的数组中任意一个元素，我们依然选key为a[left]，将a[left]交给key保存起来，被选为key的元素位置就是坑位；
2.从数组右端（尾部）往左走，当a[right] < key，right停下来，将a[right]放到坑位中，坑位就换为下标为 right 的位置，此时right不动；
3.然后从数组左端（首部）往右走，当a[left] > key，left停下来，将a[left]放到坑位中，坑位就换为下标为 left 的位置，此时left不动；
4.循环步骤2、3，当 left与right 走到相同位置时，这个位置就是最后一个坑位，将key放到这个坑位中，key的最终位置就确定下来了，后面就不用再调整了。
5.此时 key 就将数组分为了左右两个区间，我们对左右两个区间分别使用前4步，然后再次确定了左右区间的key，递归左区间，再递归右区间，就实现了排序。
挖坑法与hoare版本的区别：
1.挖坑法不需要去想最后的 L与R 相遇的位置的元素要小于key，因为最终相遇位置是坑位，直接将 key 放入坑位就好了；
2.不用去想为什么选左边为 key 要右边先走，选右边为 key 要左边先走，当选左边为 key 时，因为需要填左边的坑，所以肯定是右边先走。左边找小，右边找大来理解这句话更合适。
4.2 思路图解
4.3 挖坑法代码实现
// 快速排序挖坑法 int PartSort2(int* a, int left, int right) { int key = a[left]; int hole = left; while (left < right) { //右边找小 while (left < right && a[right] >= key) { right--; } a[hole] = a[right]; hole = right; //左边找大 while (left < right && a[left] <= key) { left++; } a[hole] = a[left]; hole = left; } a[hole] = key; return hole; } void QuickSort(int* a, int left, int right) { if (left >= right) return; int keyi = PartSort2(a, left, right); QuickSort(a, left, keyi - 1); QuickSort(a, keyi + 1, right); }
4.4 挖坑法代码测试
void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } void Print(int* a, int n) { for (int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } // 快速排序挖坑法 int PartSort2(int* a, int left, int right) { int key = a[left]; int hole = left; while (left < right) { //右边找小 while (left < right && a[right] >= key) { right--; } a[hole] = a[right]; hole = right; //左边找大 while (left < right && a[left] <= key) { left++; } a[hole] = a[left]; hole = left; } a[hole] = key; return hole; } void QuickSort(int* a, int left, int right) { if (left >= right) return; int keyi = PartSort2(a, left, right); QuickSort(a, left, keyi - 1); QuickSort(a, keyi + 1, right); } void test() { int a[] = { 6,3,2,1,5,7,9 }; QuickSort(&a, 0, sizeof(a) / sizeof(int) - 1); Print(&a, sizeof(a) / sizeof(int)); } int main() { test(); return 0; }
