一、快速排序的概念
1.1快排的定义
快速排序简称快排，快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
1.2快排的动态图
1.3快速排序的几种版本介绍
快排的基本思路
1、先找整个数组的key
2、找【begin， key-1】和【key + 1, end 】区间的key
3、再去重复递归左右区间，当区间只剩一个值或者不存在时就是最小规模的子问题。
1、hoare版本
2、挖坑法
挖坑法思路简介
第二个版本：挖坑法（PartSort）
右边找小，左边找大，右边先走
右边找到小与keyi的，然后停下来，右边的把值赋给
keyi这个位置，右边腾出一个空位
左边找大的然后赋值给这个空位
最后左右两个指针的相遇在一个空位，然后把keyi填进去
谁做keyi和谁先走不是固定的，
左边做keyi，右边先走
右边做keyi, 左边先走
3、前后指针法
前后指针法的思路简介：
cur指针在前面找小，找到比key小的值就++prev指针，交换prev和cur位置的值
prev和cur的关系
1、cur还没遇到比key大的值时，prev紧跟着cur一前一后
2、cur遇到比key大的值后，prev和cur之间间隔着一段比key大的值的区间
二、快速排序的递归实现
2.1 hoare版本的递归实现
有了前面的讲解，我们对于hoare版本的快速排序已经有了一定的了解了，我们现在实现其代码部分：（大家可以先理解我对hoare版本的定义再来看其实现代码，或者是结合起来理解）
int PartSort(int* a, int left, int right) { int keyi = left;//key设置成最左边的数 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 begin, int end) { //子区间相等只有一个值或者不存在那么就是递归结束的子问题 if (begin >= end) return; int keyi = PartSort(a, begin, end); // [begin, keyi - 1]keyi[keyi + 1, end] QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); }
贴一张图方便大家理解
2.2挖坑法的递归代码示例：
//挖坑法 int PartSort2(int* a, int left, int right) { int key = a[left]; //坑位 int pit = left; while (left < right) { //右边先走,找小于key while (left < right && a[right] >= key ) { --right; } a[pit] = a[right]; pit = right; //左边走，找大于key while (left < right && a[left] <= key) { ++left; } a[pit] = a[left]; pit = left; } a[pit] = key; return pit; } void QuickSort2(int* a, int begin, int end) { //子区间相等只有一个值或者不存在那么就是递归结束的子问题 if (begin >= end) return; int keyi = PartSort2(a, begin, end); // [begin, keyi - 1]keyi[keyi + 1, end] QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); }
2.3前后指针法的递归代码示例
//前后指针法 int PartSort3(int* a, int left, int right) { int keyi = left;//如果是a[left],则是局部变量，SWap后还是原来的值 //left则是下标 int prev = left, cur = left + 1; while (cur <= right) { if (a[cur] < a[keyi] && a[++prev] != a[cur]) Swap(&a[prev], &a[cur]); ++cur; } Swap(&a[prev], &a[keyi]); return prev; } void QuickSort3(int* a, int begin, int end) { //子区间相等只有一个值或者不存在那么就是递归结束的子问题 if (begin >= end) return; int keyi = PartSort3(a, begin, end); // [begin, keyi - 1]keyi[keyi + 1, end] QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); }
三、快速排序的非递归实现以及快排模板
3.1快排的非递归实现
快排的非递归应用场景是比较少的，因为快排也不是那么容易就爆栈，但是学习快排的非递归也能帮助我们更好地理解快排。
快排的非递归写法用C语言实现会相对复杂，因为快排的非递归需要利用栈来实现，但是C语言没有自己的STL库，所以要自己手写一个栈，相对比较麻烦些。
我们还是使用前后指针法来找key，然后用栈来实现递归的作用
栈的代码：
#pragma once #include<stdio.h> #include<stdlib.h> #include<stdbool.h> #include<assert.h> typedef int STDataType; typedef struct Stack//动态栈 { int* a; int top;//栈顶的位置 int capacity;//容量 }ST; STDataType StackTop(ST* ps);//返回栈顶的值 void StackInit(ST* ps);//初始化栈 void StackDestory(ST* ps);//销毁栈 void StackPop(ST* ps);//弹出 void StackPush(ST* ps, STDataType x);//插入 bool StackEmpty(ST* ps);//判断栈是否为空。 #include"Stack.h" void StackInit(ST* ps)//栈的初始化 { assert(ps); ps->a = NULL;//a点的值指向空 ps->top = 0;//栈底为0 ps->capacity = 0;//空间为0 } void StackDestory(ST* ps) { assert(ps); free(ps->a);//把a释放掉 ps->a = NULL; ps->capacity = ps->top = 0; } void StackPush(ST* ps, STDataType x)//入数据 { assert(ps); //满了就扩容 if (ps->top == ps->capacity)//如果栈的栈顶恰好和容量相等就扩容 { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; ps->a = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType)); if (ps->a == NULL) { printf("realloc fail\n"); exit(-1); } ps->capacity = newCapacity;//新的空间赋给旧的 } ps->a[ps->top] = x;//栈顶插入x; ps->top++;//top++ } void StackPop(ST* ps) { assert(ps); assert(ps->top > 0); --ps->top;//top--就相当于删除操作 } bool StackEmpty(ST* ps) { assert(ps); //两种写法 //if (ps->top > 0) //{ // return false; //} //else //{ // return true; //} return ps->top == 0; } STDataType StackTop(ST* ps) { assert(ps); assert(ps->top > 0); return ps->a[ps->top - 1];//访问栈顶元素（这里因为top我们设为0，所以访问栈顶元素相当于top-1 } int StackSize(ST* ps) { assert(ps); return ps->top; }
用前后指针加之栈来实现快排的代码：
快排的非递归写法
void QuickSort5(int* a, int begin, int end) { ST st; StackInit(&st); //入栈 StackPush(&st, begin); StackPush(&st, end); //栈是后进先出 while (!StackEmpty(&st)) { int right = StackTop(&st); StackPop(&st); int left = StackTop(&st); StackPop(&st); int keyi = PartSort3(a, left, right); //[left, keyi - 1][keyi + 1, right] if (left < keyi - 1)//还要继续入栈的条件 { StackPush(&st, left); StackPush(&st, keyi - 1); } if (keyi + 1 < right) { StackPush(&st, keyi + 1); StackPush(&st, right); } } StackDestory(&st); } PartSort3 //前后指针法 int PartSort3(int* a, int left, int right) { int mini = Getmini(a, left, right); Swap(&a[mini], &a[left]); int keyi = left;//如果是a[left],则是局部变量，SWap后还是原来的值 //left则是下标 int prev = left, cur = left + 1; while (cur <= right) { if (a[cur] < a[keyi] && a[++prev] != a[cur]) Swap(&a[prev], &a[cur]); ++cur; } Swap(&a[prev], &a[keyi]); return prev; }
3.2快排的模板（适用于算法竞赛）
它把key设为了中间值，这样好像是代码既短又是最优的情况。
#include <iostream> using namespace std; const int N = 100010; int q[N]; void quick_sort(int q[], int l, int r) { if (l >= r) return; int i = l - 1, j = r + 1, x = q[l + r >> 1]; while (i < j) { do i ++ ; while (q[i] < x); do j -- ; while (q[j] > x); if (i < j) swap(q[i], q[j]); } quick_sort(q, l, j); quick_sort(q, j + 1, r); }
四、快排的优化
4.1三数取中法优化快排
我们为什么要对快排进行优化？
原因：
有序的时候快排的时间复杂度是O（N^2）
数据量大时会爆栈
三数取中代码示例：比快排模板选key的可靠性要更高些
int Getmini(int* a, int left, int right)//三数取中 { int mid = left + right; //防止溢出可以写成int mid = left + (right - left) / 2; if (a[left] < a[mid]) { if (a[mid] < a[right]) { return mid; } else if (a[left] > a[right]) { return left; } else { return right; } } else { if (a[mid] > a[right]) { return mid; } else if (a[left] < a[right]) { return left; } else { return right; } } }
