今天我们要讲的是快速排序，非常的哇塞！
简单了解一下快排------
下面介绍快排的三个方法，未优化和优化后的快排
First----hoare版本
也就是说先确立的一个下标为key的值为对比值，普遍可以认为左边第一个值就key值，然后，从右边发出，寻找比key值小的数字，当R停下时，L才动，然后找到比key大的值，然后进行L、R的交换，最终他们一定会相遇，相遇的下标对应的值就将key赋值给他，然后再分而治之，
[left,key-1] key [key+1,right] 就是一样一个递归
数据结构一定要学会画图来思考问题，让问题更加地清晰明了！
完整代码：
//hoare版本
void QuickSort(int* arr, int begin, int end)
{
//进来判断一下
if (begin >= end)
{
return;
}
int left = begin;
int right = end;
int key = left;
while (left < right)
{
//先走右边
while (left < right && arr[right] >= arr[key])
{
--right;
}
while (left < right && arr[left] <= arr[key])
{
++left;
}
//交换
Swap(&arr[left], &arr[right]);
}
//最后相遇了
Swap(&arr[key], &arr[left]);
key = left;//更新key的位置
QuickSort(arr, begin, key - 1);
QuickSort(arr, key + 1, end);
}
void PrintSort(int* arr, int len)
{
for (int i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
}
int main()
{
int arr[] = { 3,1,2,4,9,5,6};
int len = sizeof(arr) / sizeof(arr[0]);
QuickSort(arr,0, len-1);
PrintSort(arr, len);
}
下面介绍另外一种方法，被大神们优化一下， 比较好理解！
2、挖坑法-------顾名思义就是有一个坑
完整代码：
//挖坑法
void QuickSort(int* arr, int begin, int end)
{
if (begin >= end)
{
return;
}
int left = begin;
int right = end;
int key = arr[left];
int piti =left;//坑位
while (left < right)//控制范围
{
while (left < right && arr[right] >= key)
{
--right;
}
arr[piti] = arr[right];
piti = right;
while (left < right && arr[left] <= key)
{
++left;
}
arr[piti] = arr[left];
piti = left;
}
//还有最后相遇的一个坑位
arr[piti] = key;
QuickSort(arr, begin, piti - 1);
QuickSort(arr, piti + 1, end);
}
void PrintSort(int* arr, int len)
{
for (int i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
}
int main()
{
int arr[] = { 3,1,2,4,9,5,6};
int len = sizeof(arr) / sizeof(arr[0]);
QuickSort(arr,0, len-1);
PrintSort(arr, len);
}
第三种方法：前后指针版本
完整代码：
//前后指针版本
void QuickSort(int* arr, int begin, int end)
{
if (begin >= end)
{
return;
}
int prev = begin;
int cur = begin + 1;
int key = begin;
while (cur <= end)
{
if (arr[cur] < arr[key] && ++prev != cur)
{
Swap(&arr[cur], &arr[prev]);
}
++cur;
}
//最后只剩下一个prev
Swap(&arr[prev], &arr[begin]);
key = prev;
QuickSort(arr, begin, key - 1);
QuickSort(arr, key + 1, end);
}
void PrintSort(int* arr, int len)
{
for (int i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
}
int main()
{
int arr[] = { 3,1,2,4,9,5,6};
int len = sizeof(arr) / sizeof(arr[0]);
QuickSort(arr,0, len-1);
PrintSort(arr, len);
}
相信你学会这三种快排的方法不算难事，但是那都是没进行过优化的，接下来让我们来优化一下吧！前面三种方法的时间复杂度都是O（N），在效率上并没有提升太多
优化方法—：三数取中（在前后指针版本上面改善）
影响效率的障碍就是key，要不每次key都是最小，要 不key每次都是最大，那么效率肯定就上不去，如果我们让key是区域内的middle 那么效率更上一层了，所以三数取中。
//前后指针版本
void QuickSort(int* arr, int begin, int end)
{
if (begin >= end)
{
return;
}
int prev = begin;
int cur = begin + 1;
int key = begin;
//三数取中
int mid = GetMidIndex(arr, begin, end);
Swap(&arr[key], &arr[mid]);
while (cur <= end)
{
if (arr[cur] < arr[key] && ++prev != cur)
{
Swap(&arr[cur], &arr[prev]);
}
++cur;
}
//最后只剩下一个prev
Swap(&arr[prev], &arr[begin]);
key = prev;
QuickSort(arr, begin, key - 1);
QuickSort(arr, key + 1, end);
}
优化方法二：递归到小的子区间时，可以考虑使用插入排序
因为在数据有序或者接近有序的时候，插入排序的效率非常可观，至于为什么不用希尔，堆，是因为在大数据下用他们比较快，但是接近有序的时间复杂度插入排序更胜一筹！
这些数据划分区域就知道最后接近有序的递归次数就占了一半，所以说非常的庞大。
区域优化代码：
这里的插入排序的arr如果不加begin的话，那么每次都是最前面的20个数进行排序，那么无意义，arr+begin就是不同区域内的begin----end
这个优化就非常的爽了！
这些快排都是运用了递归的方式，递归也是一定的劣势，所以我们也必须要掌握非递归的方式
非递归我们运用的是栈完成快排
栈的性质是先进后出，我们可以完美地运用这个性质！
思路：
这完全就像是树的工作方式，先完成左树的排序，然后再进行右树的排序，穷尽到最后一个区域，最后再销毁一下栈就可以实现非递归的快排了
更形象一点：当然用队列也是一样的，运用好队列的性质就行好，控制好
因为这是纯C所以要先手搓一个栈，到C++就不用这么麻烦了，
非递归完整代码:
//栈
typedef struct Stack
{
int* arr;
int top;
int capacity;
}Stack;
void InitStack(Stack* ps)
{
ps->arr = NULL;
ps->top = ps->capacity = 0;
}
void StackPush(Stack* ps,int x)
{
//检测是否满了
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
int tmp = (int *)realloc(ps->arr,sizeof(int )*newcapacity);
ps->arr = tmp;
ps->capacity = newcapacity;
}
ps->arr[ps->top] = x;
ps->top++;
}
void StackPop(Stack* ps)
{
ps->top--;
}
void DestoryStack(Stack* ps)
{
ps->arr = NULL;
ps->top = ps->capacity = 0;
}
int StackTop(Stack* ps)
{
return ps->arr[ps->top-1];
}
bool StackEmpty(Stack* ps)
{
return ps->top==0;
}
//栈来实现非递归的快排
void QuickSort(int* arr, int begin, int end)
{
Stack st;
InitStack(&st);
StackPush(&st, end);
StackPush(&st, begin);
while (!StackEmpty(&st))
{
int left = StackTop(&st);
StackPop(&st);
int right = StackTop(&st);
StackPop(&st);
int keyi = QuickSort2(arr, left, right);
if (left < keyi - 1)
{
StackPush(&st, keyi - 1);
StackPush(&st, left);
}
if (keyi + 1 < right)
{
StackPush(&st, right);
StackPush(&st, keyi + 1);
}
}
DestoryStack(&st);
}
void PrintSort(int* arr, int len)
{
for (int i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
}
int main()
{
int arr[] = { 3,1,2,4,9,5,6};
int len = sizeof(arr) / sizeof(arr[0]);
QuickSort(arr,0,len-1);
PrintSort(arr, len);
}
伙伴们！快来试一下吧！！
如有错误，请指出！
