在本文中使用到的升序，降序，交换函数的代码见：这篇博客
快速排序（递归实现）
快速排序的基本思想是在待排序序列中找到一个基准值（一般取待排序序列的最后一个元素），然后将该基准值放置在一个合适的位置，使得在基准值之前的元素都小于等于基准值，基准值之后的元素都大于等于基准值。
然后再对基准值之前的序列使用上述方法进行排序寻找基准值位置，对基准值之后的序列使用上述方法进行排序寻找基准值位置。所以这是一个递归的过程。
根据这个合适的位置寻找的方式可以分为两种方法来实现。一种是交换法，一种是挖坑法。
1. 交换法实现快速排序
排序思路如下：
所以将上述的过程1封装为一个函数，该函数的实现就是不断的交换的过程，因此及该方法也成为交换法：
（1）首先对待排序序列使用该函数，使基准值之前的元素小于等于基准值，基准值之后的元素大于等于基准值，同时返回基准值所在的下标位置left；
（2）然后对left之前的序列进行（1）~（3）的过程；
（3）再对left之后的序列进行（1）~（3）的过程；
所以，上述的（1）~（3）可以作为递归函数的过程，当待排序序列的元素个数为小于等于1时，递归函数返回，不用再进行（1）~（3）的过程。
代码实现如下：
void QuickSort(int arr[],int size)
{
if(arr == NULL || size <= 1)
{
return;
}
int left = 0;
int right = size;
_QuickSort(arr,left,right);
}
//递归函数
void _QuickSort(int arr[],int left,int right)
{
if(arr == NULL || right - left <= 1)
{
return;
}
//先找一个基准值，这里设置数组最后一个元素基准值
//找到放置基准值的位置，使得在该位置之前的数组元素小于等于基准值
//在该位置之后的数组元素大于等于基准值
int mid = Pattern2(arr,left,right);
_QuickSort(arr,left,mid);
_QuickSort(arr,mid + 1,right);
}
交换函数为：
//交换法
int Pattern1(int arr[],int left,int right)
{
//该函数用于给基准值找一个合适的位置，
//使得在基准值之前的元素都小于等于基准值
//在基准值之后的元素都大于等于基准值
//所以要先从前往后遍历使数组前面的元素小于等于基准值
//从后往前遍历使后面的元素大于等于基准值
//当两个遍历索引相遇时，一定找到了小于基准值和大于据准值元素的分界点
//此时将分界点处的值替换为基准值即可保证上述的要求
//如果数组只有一个元素，则基准值直接放置在起始位置即可
if(right - left <= 1)
{
return left;
}
//从起始位置开始往后遍历寻找大于基准值的数组元素
int left_index = left;
int right_index = right - 1;
//从末尾位置开始往前遍历寻找小于基准值的数组元素
//将基准值设置为所在区间的最后一个元素值
int basic_value = arr[right - 1];
while(left_index < right_index)
{
//如果从前往后找到大于基准值的元素，就停下来
while(left_index < right_index && arr[left_index] <= basic_value)
{
left_index++;
}
//如果从后往前找到小于基准值的元素，就停下来
while(left_index < right_index && arr[right_index] >= basic_value)
{
right_index--;
}
//交换停下来的两个值
Swap(&arr[left_index],&arr[right_index]);
}
Swap(&arr[left_index],&arr[right - 1]);
return left_index;
}
2. 挖坑法实现快速排序
该方法在实现是：
（1）先将基准值之前的元素小于等于基准值，之后的元素大于等于基准值。
（2）然后对基准值之前的序列调用递归函数
（3）最后对基准值之后的序列调用递归函数。
只是在（1）的实现上与上述的交换法不同，如下图：
//挖坑法
int Pattern2(int arr[],int left,int right)
{
if(right - left <= 1)
{
return left;
}
int left_index = 0;
int right_index = right - 1;
//基准值为带排序序列的最后一个元素
int basic_value = arr[right - 1];
//当left_index和right_index没有相遇时
while(left_index < right_index)
{
//如果没有相遇且left_index遇到小于等于基准值的元素，则left_index后移
while(left_index < right_index && arr[left_index] <= basic_value)
{
left_index++;
}
//如果没有相遇且left_index遇到大于基准值的元素
if(arr[left_index] > basic_value)
{
//将该元素赋值到坑所在位置
arr[right_index] = arr[left_index];
}
//同理
while(left_index < right_index && arr[right_index] >= basic_value)
{
right_index--;
}
if(arr[right_index] < basic_value)
{
arr[left_index] = arr[right_index];
}
}
//当left_index与right_index相遇时，一定位于坑所在的位置
//此时，将基准值赋值到该处即可
arr[left_index] = basic_value;
//返回基准值放置的位置
return left_index;
}
非递归实现快速排序
如果不为空，则该栈顶元素必为带排序序列的尾坐标。出栈后，再取栈顶元素，该栈顶元素必为待排序序列的首坐标，然后 再出栈，如果待排序序列的元素个数小于等于1，此时不用再进行下面的处理，重新回到（2）进行新一轮的处理；
（3）将上述的两个首尾坐标利用交换法或挖坑法进行处理，得到基准值的坐标；
（4）将基准值之前的序列首尾坐标分别入栈；
（5）将基准值之后的序列首尾坐标分别入栈；
（6）重复（2）~（5）的操作。
以下有关的栈的操作实现见：这篇博客
根据上述思路，代码实现如下：
void QuickSortByLoop(int arr[],int size)
{
if(arr == NULL || size <= 1)
{
return;
}
SeqStack stack;//定义栈
InitSeqStack(&stack);//初始化栈
//入栈整个待排序序列的首位坐标
SeqStackPush(&stack,0);
SeqStackPush(&stack,size);
int left;
int right;
while(1)
{
//取栈顶元素作为带排序序列的尾坐标
int ret = SeqStackTop(&stack,&right);
if(ret == -1)//栈定为空，带排序序列处理完
{
return;
}
//出栈后再取栈顶元素
SeqStackPop(&stack);
//此时的栈定元素必为带排序序列的首坐标
SeqStackTop(&stack,&left);
//出栈栈顶元素
SeqStackPop(&stack);
//如果带排序序列元素个数小于等于1，则该序列必然已经排好序
//且不能在分为更小的序列，也就不需要再进行排序再进行入栈了
if(right - left <= 1)
{
continue;
}
//对带排序序列进行排序处理
int mid = Pattern1(arr,left,right);
//将带排序序列分为两部分分别入栈，进行处理
SeqStackPush(&stack,left);
SeqStackPush(&stack,mid);
SeqStackPush(&stack,mid + 1);
SeqStackPush(&stack,right);
}
return;
}
快速排序的时间复杂度为：O(nlogn)（平均时间复杂度），O(n^2)（最坏时间复杂度）
最快空间复杂度：O(n)
稳定性：不稳定