快速排序

原理

设置一个关键值，一个左值，一个右边的值，分别向右边和左边遍历，左边的找比key大的，右边的找比key小的，找到后交换两个的值，直到左和右边相遇，交换key和a[左]值，然后一直递归下去 

代码实现

void QuickSort(int* a, int left,int right)
{if (right - left < 1){return;}int begin = left, end = right;int keyi = left;while (left < right){//为什么先走right,因为keyi在左边，极端情况下，right可能//一直走到头while (right > left && a[right] >= a[keyi]){right--;}while (left < right && a[left] <= a[keyi]){left++;}Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);keyi = left;QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}}

时间复杂度

由于每次都是要把一个序列分成两个部分，每一个序列都要操作N次（每一次虽然都会减少），所以一般情况下的时间复杂度为O(n*logN)

但是，我们所说的时间复杂都是在最坏的情况下，当序列有序的情况下，左边的区间没有，所以这里的时间复杂度为O（N^2）

代码改进

为了应对上面的序列有序的情况，我们有以下的两种改进

随机数

在序列中随机选出一个数作为该序列中的最左值

void QuickSort(int* a, int left,int right)
{if (right - left < 1){return;}int i = rand() % (right - left);i = i + left;Swap(&a[i], &a[left]);int begin = left, end = right;int keyi = left;while (left < right){//为什么先走right,因为keyi在左边，极端情况下，right可能//一直走到头while (right > left && a[right] >= a[keyi]){right--;}while (left < right && a[left] <= a[keyi]){left++;}Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);keyi = left;QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}}

中位数法

选出一个中位数，作为序列的左值

int GetMid(int* a, int left, int right)
{int mid = (right + left) / 2;if (a[mid] > a[left]){if (a[mid] < a[right]){return mid;}else //a[mid]>a[right]{if (a[right] > a[left]){return right;}else{return left;}}}else //a[mid]<a[left]{if (a[mid] > a[right]){return mid;}else if(a[left]<a[right]){return left;}else{return right;}}
}void QuickSort(int* a, int left,int right)
{if (right - left < 1){return;}int mid = GetMid(a, left, right);Swap(&a[mid], &a[left])int begin = left, end = right;int keyi = left;while (left < right){//为什么先走right,因为keyi在左边，极端情况下，right可能//一直走到头while (right > left && a[right] >= a[keyi]){right--;}while (left < right && a[left] <= a[keyi]){left++;}Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);keyi = left;QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}}

快速排序—前后指针法

void QuickSort1(int* a, int left, int right)
{if (right <=left){return;}int keyi = left;int prev = left;int cur = left + 1;while (cur <= right){if (a[cur] < a[keyi]){prev++;Swap(&a[prev], &a[cur]);cur++;}else{cur++;}}Swap(&a[prev], &a[keyi]);keyi = prev;QuickSort1(a, left, keyi - 1);QuickSort1(a, keyi + 1, right);
}

快速排序-非递归

这里主要运用的是数据结构的栈，先插入左右区间，进行单趟排序，再插入子区间，如此循环

void QuickSort2(int* a, int left, int right)
{SL sl;SLinit(&sl);SLpush(&sl, right);SLpush(&sl, left);while (!SLempty(&sl)){int begin = SLtop(&sl);SLpop(&sl);int end = SLtop(&sl);SLpop(&sl);//单趟排序int keyi = begin;int prev = begin;int cur = begin + 1;while (cur <= end){if (a[cur] < a[keyi]){prev++;Swap(&a[prev], &a[cur]);cur++;}else{cur++;}}Swap(&a[prev], &a[keyi]);keyi = prev;if (keyi + 1 < end){SLpush(&sl, end);SLpush(&sl, keyi + 1);}if (keyi - 1 > begin){SLpush(&sl, keyi - 1);SLpush(&sl, begin);}}SLdestory(&sl);
}