各位CSDN的uu们好呀，今天又是小雅兰的数据结构与算法专栏啦，下面，就让我们进入快速排序的世界吧！！！
快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右 子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
hoare法
单趟动图如下：
//hoare法 int PartSort1(int* a, int left, int right) {int keyi = left;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 QuickSort(int* a, int begin, int end) {if (begin >= end){return;}int keyi = PartSort1(a, begin, end);//[begin,keyi-1] keyi [keyi+1,end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end); }测试一下快速排序：
void TestQuickSort()
{
int a[] = { 2,1,4,3,6,5,7,9,8,10 };
PrintArray(a, sizeof(a) / sizeof(a[0]));
QuickSort(a, 0, sizeof(a) / sizeof(a[0]) - 1);
PrintArray(a, sizeof(a) / sizeof(a[0]));
}
这边有一个问题
如何保证left和right相遇的位置一定比keyi小呢？
左边作keyi，右边先走，保障了相遇位置的值比keyi小或者是就是keyi的位置
left和right相遇，无非就是两种情况，left遇right和right遇left
情况一：left遇right，right是停下来，left在走。right先走，right停下来的位置一定比keyi小，相遇的位置就是right停下来的位置，就一定比keyi小。
情况二：right遇left，在相遇这一轮，left就没动，right在移动，跟left相遇，相遇位置就是left的位置，left的位置就是keyi的位置，或者交换过一些轮次，相遇left的位置一定比keyi小
右边作keyi，左边先走，保障了相遇位置的值比keyi大
挖坑法
//挖坑法 int PartSort2(int* a, int left, int right) {int key = a[left];int hole = left;while (left < right){//右边找小//要防止死循环和越界的问题while (left < right && a[right] >= key){--right;}a[hole] = a[right];hole = right;//左边找大while (left < right && a[left] <= key){++left;}a[hole] = a[left];hole = left;}a[hole] = key;return hole; } void QuickSort(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); }
前后指针法
//前后指针法 int PartSort3(int* a, int left, int right) {int prev = left;int cur = left + 1;int keyi = left;while (cur <= right){if (a[cur] < a[keyi]){++prev;Swap(&a[prev], &a[cur]);}++cur;}Swap(&a[prev], &a[keyi]);keyi = prev;return keyi; } void QuickSort(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); }
快速排序优化
- 三数取中法选key
- 递归到小的子区间时，可以考虑使用插入排序
- 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
- 时间复杂度：O(N*logN)
- 空间复杂度：O(logN)
- 稳定性：不稳定
三数取中：
int GetMidIndex(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 right;}else{return left;}}else // a[left] > a[mid]{if (a[mid] > a[right]){return mid;}else if (a[left] > a[right]){return right;}else{return left;}} }
优化后的所有方式源代码：
int GetMidIndex(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 right;
}
else
{
return left;
}
}
else // a[left] > a[mid]
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] > a[right])
{
return right;
}
else
{
return left;
}
}
}
// hoare
// [left, right]
int PartSort1(int* a, int left, int right)
{
int midi = GetMidIndex(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;
}Swap(&a[left], &a[right]);
}Swap(&a[keyi], &a[left]);
return left;
}
// 挖坑法
// [left, right]
int PartSort2(int* a, int left, int right)
{
int midi = GetMidIndex(a, left, right);
Swap(&a[left], &a[midi]);int key = a[left];
int hole = left;
while (left < right)
{
// 右边找小
while (left < right && a[right] >= key)
{
--right;
}a[hole] = a[right];
hole = right;// 左边找大
while (left < right && a[left] <= key)
{
++left;
}a[hole] = a[left];
hole = left;
}a[hole] = key;
return hole;
}// 前后指针法
// [left, right]
int PartSort3(int* a, int left, int right)
{
int midi = GetMidIndex(a, left, right);
Swap(&a[left], &a[midi]);int prev = left;
int cur = left + 1;
int keyi = left;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[prev], &a[cur]);
}++cur;
}Swap(&a[prev], &a[keyi]);
keyi = prev;
return keyi;
}
void QuickSort(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);
}
快速排序非递归
void QuickSortNonR(int* a, int begin, int end) {Stack st;StackInit(&st);StackPush(&st, end);StackPush(&st, begin);while (!StackEmpty(&st)){int left = StackTop(&st);StackPop(&st);int right = StackTop(&st);StackPop(&st);int keyi = PartSort1(a, left, right);// [left, keyi-1] keyi [keyi+1, right]if (keyi + 1 < right){StackPush(&st, right);StackPush(&st, keyi + 1);}if (left < keyi - 1){StackPush(&st, keyi - 1);StackPush(&st, left);}}StackDestroy(&st); }测试一下快速排序非递归：
void TestQuickSortNonR()
{
int a[] = { 2,1,4,3,6,5,7,9,8,10 };
PrintArray(a, sizeof(a) / sizeof(a[0]));
QuickSortNonR(a, 0, sizeof(a) / sizeof(a[0]) - 1);
PrintArray(a, sizeof(a) / sizeof(a[0]));
}
Stack.h和Stack.c的内容：
#pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef int STDataType; typedef struct Stack {STDataType* a;int top;//栈顶int capacity;//容量 }Stack;// 初始化栈 void StackInit(Stack* pst);// 销毁栈 void StackDestroy(Stack* pst);// 入栈 void StackPush(Stack* pst, STDataType x);// 出栈 void StackPop(Stack* pst);// 获取栈顶元素 STDataType StackTop(Stack* pst);// 获取栈中有效元素个数 int StackSize(Stack* pst);// 检测栈是否为空 bool StackEmpty(Stack* pst);#include"Stack.h" // 初始化栈 void StackInit(Stack* pst) {assert(pst);pst->a = NULL;pst->top = 0;pst->capacity = 0; } // 销毁栈 void StackDestroy(Stack* pst) {assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0; } // 入栈 void StackPush(Stack* pst, STDataType x) {assert(pst);//扩容if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capacity = newcapacity;}pst->a[pst->top] = x;pst->top++; } // 检测栈是否为空 bool StackEmpty(Stack* pst) {assert(pst);if (pst->top == 0){return true;}else{return false;}//return pst->top==0; } // 出栈 void StackPop(Stack* pst) {assert(pst);assert(!StackEmpty(pst));pst->top--; } // 获取栈顶元素 STDataType StackTop(Stack* pst) {assert(pst);assert(!StackEmpty(pst));return pst->a[pst->top - 1]; }// 获取栈中有效元素个数 int StackSize(Stack* pst) {assert(pst);return pst->top; }
好啦，小雅兰的快速排序的所有的内容就到这里啦，还要继续加油学数据结构与算法啦，敬请期待小雅兰下一篇的归并排序的内容！！！
