目录
一、递归
1、霍尔法：
2、挖坑法：
3、前后指针法：
二、非递归
三、完整代码：
基本思想：
先取这个待排序元素序列中的某一个元素最为key值，然后通过这个key值将这个序列分为两边，一边小于这个key，另一边大于这个key，然后接着对这个左边的序列和右边的序列进行相同的操作，直到所有的元素都在相应的位置上。
一、递归
1、霍尔法：
思路：
这里排序为升序
我们这里找最左边的元素作为key
定义一个变量指向最右边right，再来一个变量指向最左边left（注意，如果key在左边，那么就要从右边开始先走，如果key在右边，那么就要从左边开始走，这样才能保证这两个相遇的位置一定比key要小）
来个循环遍历这个序列：
right开始向左走找一个比key还要小的，
找到后left向右走找到一个比key还要大的，
接着交换这两个位置的元素。
所以结束条件就是left<right。
结束后交换此时这两个所在的共同位置和key的位置，key也要换到这个位置
最后再来递归即可（所以可以在最开始用两个变量begin和end记录left和right的位置）
OK！思路一出直接开写：
在写之前要两个函数，一个是交换函数：
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}另外一个为优化这个快速排序的代码：三数取中，也就是说在三个数中取中间大的那个数字
。这样可以使单趟排序后左边的和右边的元素个数差不多，进而减小递归的深度。
int GetMidNumi(int* a, int left, int right)
{int mid = (left + right) / 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 // a[left] > a[mid]{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}
}OK！现在可以开始写了
void QuickSort1(int* a, int left, int right)
{if (left >= right)return;int begin = left, end = right;//三数取中int midi = GetMidNumi(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;while (left < right){//右边先走找小的while (left < right && a[right] >= a[keyi])right--;//左边走找大的while (left < right && a[left] <= a[keyi])left++;if (left == right)break;Swap(&a[right], &a[left]);}Swap(&a[keyi], &a[left]);keyi = left;QuickSort1(a, begin, keyi - 1);//这里为左边的区间QuickSort1(a, keyi + 1, end);//这里为右边的区间
}2、挖坑法：
思路：
首先，将第一个元素存放在临时变量key中，此时将第一个元素定义为hole，这个时候这个hole就可以随便改了。
接着像霍尔法一样，right向左走找比key小的位置，此时将这个位置的元素赋值给hole，然后将hole改到这个right所在的位置。
然后left向右走找比key大的位置，找到后将这个位置的元素赋值给hole，然后将hole改到这个left所在的位置。
直到left == right后退出循环，此时将最开始的变量key放在hole中
最后左递归的区间为[begin, hole - 1]
右递归的区间为[ hole + 1, end]
OK！思路一出，直接开写：
void QuickSort2(int* a, int left, int right)
{if (left >= right)return;//三数取中int midi = GetMidNumi(a, left, right);Swap(&a[left], &a[midi]);int key = a[left];int begin = left, end = right;int hole = left;while(left < right){while (left < right && a[right] >= key)right--;//Swap(&a[hole], &a[right]);a[hole] = a[right];hole = right;while (left < right && a[left] <= key)left++;//Swap(&a[hole], &a[left]);a[hole] = a[left];hole = left;}a[hole] = key;QuickSort2(a, begin, hole - 1);QuickSort2(a, hole + 1, end);
}3、前后指针法：
思路：
首先：定义最左边为key，然后最左边为prev，prev的下一个为cur
然后如果cur所在的值小于key，那么++prev，然后将cur所在的值和prev所在的值相交换，在cur++。
如果cur的值不小于key，那么就cur++。
退出循环的条件为cur小于right。
最后交换此时prev所在的元素和最左边的元素。
理解：
prev和cur之间要么紧跟着，要么prev和cur中间间隔着比key大的一段区间。
OK！思路一出，直接开写
int QuickSort3(int* a, int left, int right)
{// 三数取中int midi = GetMidNumi(a, left, right);if (midi != left)Swap(&a[midi], &a[left]);int keyi = left;int prev = left;int cur = left + 1;while (cur <= right){if (a[cur] < a[keyi]){prev++;Swap(&a[cur], &a[prev]);cur++;continue;}else{cur++;continue;}}Swap(&a[prev], &a[keyi]);keyi = prev;return keyi;
}void QuickSort(int* a, int left, int right)
{if (left >= right)return;int keyi = QuickSort3(a, left, right);QuickSort3(a, left, keyi - 1);QuickSort3(a, keyi + 1, right);
}这里QuickSort3返回值与上面不同为后面非递归的完成做铺垫。
二、非递归
思路：
因为递归可能会存在栈溢出，那么就需要把这个程序修改为非递归。
那么就需要栈和循环来帮助我们实现递归转非递归。
1、首先将这个序列的right先入栈，再将left入栈（顺序其实是无伤大雅的），
2、然后来个循环，结束条件为这个栈为空
3、在循环中定义begin访问栈顶的元素，就是上面的left（left后入栈的）
定义end访问栈顶元素的下一个为right。
4、接着用QuickSort3来进行单趟排序，返回值记录在keyi中。
所以里面区间就变成了：[begin,keyi-1] keyi [keyi+1, end]（左边比keyi小，右边比keyi大）
5、接着判断，如果keyi+1小于end，那么依次将end和keyi+1入栈，
如果keyi-1大于begin，那么将依次将keyi-1和begin入栈。
所以此时循环上去就继续访问栈顶元素和栈顶元素的下一个来作为begin和end继续排序。
void QuickSortNonR(int* a, int left, int right)
{ST st;STInit(&st);STPush(&st, right);STPush(&st, left);while (!STEmpty(&st)){int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st);int keyi = QuickSort3(a, begin, end);// [begin,keyi-1] keyi [keyi+1, end]if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi+1);}if (begin < keyi-1){STPush(&st, keyi-1);STPush(&st, begin);}}STDestroy(&st);
}三、完整代码：
栈的代码：
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#define N 10typedef int STDataType;typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;//打印无法保证后进先出
//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//判断栈里面元素的个数
int STSize(ST* ps);
//判断栈顶元素是否为空
bool STEmpty(ST* ps);
//访问栈顶元素
STDataType STTPop(ST* ps);
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
//初始化栈
void STInit(ST* ps)
{assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);if (ps->a == NULL){perror("malloc fail");return;}ps->capacity = 4;ps->top = 0;//代表栈顶元素的下一个位置//ps->top = -1;//代表栈顶元素
}
//销毁栈
void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}
//入栈
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){STDataType* newnode = (STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity*2);if (newnode == NULL){perror("realloc fail");return;}ps->a = newnode;ps->capacity *= 2; }ps->a[ps->top] = x;ps->top++;
}
//出栈
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;}
//判断栈里面元素的个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}
//判断栈顶元素是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}
//访问栈顶元素
STDataType STTPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top-1];
}
快排代码：
#pragma once
#include<stdio.h>
#include<stdlib.h>void QuickSort1(int* a, int left, int right);
void QuickSort2(int* a, int left, int right);
int QuickSort3(int* a, int left, int right);
int GetMidNumi(int* a, int left, int right);int GetMidNumi(int* a, int left, int right)
{int mid = (left + right) / 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 // a[left] > a[mid]{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}
}void QuickSort1(int* a, int left, int right)
{if (left >= right)return;int begin = left, end = right;//随机选keyi/*int randi = left + (rand() % (right - left));Swap(&a[left], &a[randi]);*///三数取中int midi = GetMidNumi(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;while (left < right){//右边先走找小的while (left < right && a[right] >= a[keyi])right--;//左边走找大的while (left < right && a[left] <= a[keyi])left++;if (left == right)break;Swap(&a[right], &a[left]);}Swap(&a[keyi], &a[left]);keyi = left;QuickSort1(a, begin, keyi - 1);QuickSort1(a, keyi + 1, end);
}void QuickSort2(int* a, int left, int right)
{if (left >= right)return;//三数取中int midi = GetMidNumi(a, left, right);Swap(&a[left], &a[midi]);int key = a[left];int begin = left, end = right;int hole = left;while(left < right){while (left < right && a[right] >= key)right--;//Swap(&a[hole], &a[right]);a[hole] = a[right];hole = right;while (left < right && a[left] <= key)left++;//Swap(&a[hole], &a[left]);a[hole] = a[left];hole = left;}a[hole] = key;QuickSort2(a, begin, hole - 1);QuickSort2(a, hole + 1, end);
}int QuickSort3(int* a, int left, int right)
{// 三数取中int midi = GetMidNumi(a, left, right);if (midi != left)Swap(&a[midi], &a[left]);int keyi = left;int prev = left;int cur = left + 1;while (cur <= right){if (a[cur] < a[keyi]){prev++;Swap(&a[cur], &a[prev]);cur++;continue;}else{cur++;continue;}}Swap(&a[prev], &a[keyi]);keyi = prev;return keyi;
}
void QuickSort(int* a, int left, int right)
{if (left >= right)return;int keyi = QuickSort3(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);
}void QuickSortNonR(int* a, int left, int right)
{ST st;STInit(&st);STPush(&st, right);STPush(&st, left);while (!STEmpty(&st)){int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st);int keyi = PartSort3(a, begin, end);// [begin,keyi-1] keyi [keyi+1, end]if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi+1);}if (begin < keyi-1){STPush(&st, keyi-1);STPush(&st, begin);}}STDestroy(&st);
}