快排（递归）
思路：
任取待排序元素序列中的某个元素作为基准值，按照该基准值，将待排序的元素分为两个子序列，左子序列的元素全部小于基准值，右子序列的元素全部大于基准值；然后左右子序列重复此操作，直到所有将所有元素排序完 右边找小，左边找大
将整个序列按照基准值划分为左右两部分的常见方式有三种：霍尔版本，挖坑法，前后指针法
单趟排序
选择基准值key（一般默认选择第一个数）
单趟排序的结果，小的数在key左边，大的数在key右边
霍尔版本
当第一个数为key时，为保证相遇位置的值一定比key小，right先走
R找到比key小的数停下，L撞到R相遇
L找到比key大的数与R找到比key小的数进行交换，然后停下，R撞到L相遇
每次基准值确定之后，就代表这个基准值的位置在整个排序中位置就确定好了，不需要再进行变动；接下来只需要在基准值的两边重复此操作，直到两边都只剩余一个元素，便说明排序完成
int Partsort1(int* a, int left, int right) { int keyi = left; while (right > left) { while (right>left && a[right] >= a[keyi]) { right--; } while (right>left && a[left] <= a[keyi]) { left++; } Swap(&a[right], &a[left]); } int meet = right; Swap(&a[meet], &a[keyi]); return meet; } void Quicksort(int* a, int left, int right) { if (right <= left) { return; } //[left,mid-1] mid [mid+1,right] int mid = Partsort1(a, left, right); Quicksort(a, left, mid - 1); Quicksort(a, mid + 1, right); }
完成第一趟排序之后，在进行右子序列排序时，发现第一个数（基准值）相较于其他的数还是偏大的，一般情况下基准值都是选择中间值，所以需要对于选基准值进行优化
三数取中
//三数取中 int Getmidindex(int* a, int left, int right) { int mid = left + (right - left) / 2; if (a[right] > a[mid]) { if (a[mid] > a[left]) { return mid; } // a[mid]<=a[left] else if (a[right] > a[left]) { return left; } // a[right]<=a[left] else { return right; } } else { if (a[right] > a[left]) { return right; } // a[right]<=a[left] else if (a[mid] > a[left]) { return left; } // a[mid]<=a[left] else { return mid; } } }
优化后的结果
挖坑法
将第一个数据令为基准值，并将存放在临时变量中，形成一个坑位
第一次单趟排序
剩余的排序
算法实现
int Partsort2(int* a, int left, int right) { //三数取中 int key = Getmidindex(a, left, right); Swap(&a[left], &a[key]); int hole = left; while (right > left) { //右边找小 填到左边的坑 while (right > left && a[right] >= key) { right--; } a[hole] = a[right]; hole = right; //左边找大 填到右边的坑 while (right > left && a[left] <= key) { left++; } a[hole] = a[left]; hole = left; } a[hole] = key; return hole; } void Quicksort(int* a, int left, int right) { if (right <= left) { return; } int mid = Partsort2(a, left, right); Quicksort(a, left, mid - 1); Quicksort(a, mid + 1, right); }
前后指针法
初始化时，prev指针指向序列的开头，cur指针指向prev指针的后一个位置
cur指针找小于key的数；prev指针要么紧跟着cur指针要么停留在比key大的数前面
cur指针遇到比key小的值时，便会停下来，++prev，交换prev和cur位置的值
剩余的排序
算法实现
int Partsort3(int* a, int left, int right) { int key = Getmidindex(a, left, right); Swap(&a[left], &a[key]); int prev = left; int cur = left + 1; while (cur <= right) { if (a[cur] < a[key] && ++prev != cur) { Swap(&a[cur], &a[prev]); } ++cur; } Swap(&a[prev], &a[key]); return prev; } void Quicksort(int* a, int left, int right) { if (right <= left) { return; } int mid = Partsort3(a, left, right); Quicksort(a, left, mid - 1); Quicksort(a, mid + 1, right); }
