快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，
其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{
if(right - left <= 1)
return;
// 按照基准值对array数组的 [left, right)区间中的元素进行划分
int div = partion(array, left, right);
// 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
// 递归排[left, div)
QuickSort(array, left, div);
// 递归排[div+1, right)
QuickSort(array, div+1, right);
}
上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，同学们在写递归框架时可想想二叉 树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。
实现：
//快排
void QuickSort(int* a,int begin,int end) {
if (begin >= end) {
return;
}
int mid = GetMid(a, begin, end);
Swap(&a[begin], &a[mid]);
int left = begin, right = end;
int key = begin;
while (left < right) {
//右边找小值
while (left < right && a[right] >= a[left]) {
right--;
}
//左边找大值
while (left < right && a[left] <= a[key]) {
left++;
}
//如果数组有序，找不到位置，那么此时就会左右相等，不进行交换
Swap(&a[left], &a[right]);
}
Swap(&a[left],&a[key]);
key = left;
QuickSort(a,begin,key-1);
QuickSort(a,key+1,end);
}
改进版：
void Swap(int* a,int* b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
int GetMid(int* a, int begin, int end) {
int mid = (end - begin) / 2;
if (a[begin] < a[mid])
{
if (a[mid] < a[end])
return mid;
else if (a[begin] > a[end])
return begin;
else
return end;
}
else
{
if (a[mid] > a[end])
return mid;
else if (a[begin] < a[end])
return begin;
else
return end;
}
}
int PartSort1(int* a, int begin, int end)
{
int mid = GetMid(a, begin, end);
Swap(&a[mid], &a[begin]);
int left = begin, right = end;
int keyi = begin;
if (end - begin + 1 < 10) {
InsertSort(a+begin,end - begin + 1);
}
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 Swap(int* a,int* b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
int GetMid(int* a, int begin, int end) {
int mid = (end - begin) / 2;
if (a[begin] < a[mid])
{
if (a[mid] < a[end])
return mid;
else if (a[begin] > a[end])
return begin;
else
return end;
}
else
{
if (a[mid] > a[end])
return mid;
else if (a[begin] < a[end])
return begin;
else
return end;
}
}
//挖坑法块排
int PartSort2(int* a,int begin,int end) {
int mid = GetMid(a, begin, end);
Swap(&a[begin], &a[mid]);
int key = a[begin];
int hole = begin;
while (begin < end) {
//右边找小值
while (begin < end && a[end] >= key) {
end--;
}
a[hole] = a[end];
hole = end;
//左边找大值
while (begin < end && a[begin] <= key) {
begin++;
}
a[hole] = a[begin];
hole = begin;
}
a[hole] = key;
return hole;
}
前后指针法：
void Swap(int* a,int* b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
int GetMid(int* a, int begin, int end) {
int mid = (end - begin) / 2;
if (a[begin] < a[mid])
{
if (a[mid] < a[end])
return mid;
else if (a[begin] > a[end])
return begin;
else
return end;
}
else
{
if (a[mid] > a[end])
return mid;
else if (a[begin] < a[end])
return begin;
else
return end;
}
}
//前后指针
int PartSort3(int* a, int begin, int end) {
int mid = GetMid(a, begin, end);
Swap(&a[begin], &a[mid]);
int pre = begin, cur = begin + 1;
int key = begin;
while (cur <= end) {
//cur找小值
if (a[cur] <= a[key] && ++pre != cur) {
Swap(&a[pre], &a[cur]);
}
cur++;
}
Swap(&a[pre], &a[key]);
return pre;
}
快速排序的特性总结：
-
快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
-
时间复杂度：O(N*logN)
-
空间复杂度：O(logN)
-
稳定性：不稳定