数据结构——快速排序

目录

一、排序思想

二、代码实现

（一）hoare版

1、原版——固定选key

2、随机选key、三数取中选key

（二）挖坑法

（三）前后指针法

（四）小区间优化

（五）非递归写法

---

一、排序思想

任取待排序元素序列中的某元素作为基准值，按照该基准值将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右两子序列重复该过程，直到所有元素都排列在相应位置上为止。

---

二、代码实现

下列所有代码示例均是排成升序。

注：

快排在对存在大量相同的数据排序时，效率很低，这种情况三路划分可以解决，感兴趣的朋友可以自行了解，这里不作介绍。

---

（一）hoare版

1、原版——固定选key

缺点：

固定位置选key，在数据有序或几乎有序时容易栈溢出。

注：

选最左边元素为key，最右边先开始选数

选最右边元素为key，最左边先开始选数

#include<stdio.h>void Print(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//haore
void QuickSort1(int* a, int left, int right)
{if (left >= right){return;}int begin = left;int end = 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]);keyi = left;//begin keyi-1  keyi  key+1 endQuickSort1(a, begin, keyi - 1);QuickSort1(a, keyi+1, end);}int main()
{int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };QuickSort1(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1);Print(arr, 10);return 0;
}

2、随机选key、三数取中选key

思想较之于原版并没有本质变化，只是优化了选key的方式。

#include<stdio.h>
#include<stdlib.h>//打印
void Print(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}//交换
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//三数取中
int Midnum(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{if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}}//快排(升序)——hoare(优化选key)
void QuickSort(int* a,int left,int right)
{if (left >= right){return;}int begin = left;int end = right;//随机选key/*int ran = left + rand() % (right - left);Swap(&a[left], &a[ran]);int keyi = left;*///三数取中选keyint mid = Midnum(a,left, right);Swap(&a[left], &a[mid]);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]);}//将key移至中间Swap(&a[left], &a[keyi]);//更新keyikeyi = left;//递归 [begin,keyi-1] keyi [keyi+1,end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}int main()
{int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };QuickSort(arr, 0, sizeof(arr) / sizeof(arr[0])-1);Print(arr, 10);return 0;
}

---

（二）挖坑法

思想：

将选定的key存起来，原本key的位置就空出来成为一个坑位，然后将找到的符合要求的元素填入坑内，该元素原本所在的位置成为新的坑位，循环往复。

其实就是一个不断填坑造坑的过程。

#include<stdio.h>//打印
void Print(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}//交换
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//三数取中
int GetMidnum(int* a, int left, int right)
{int mid = (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//a[left]<a[mid]{if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}
}//快排(升序)——挖坑法
void QuickSort3(int* a, int left, int right)
{if (left >= right){return;}int begin = left, end = right;int mid = GetMidnum(a, left, right);Swap(&a[left], &a[mid]);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;//[begin,hole-1] hole [hole+1,end]QuickSort3(a, begin, hole - 1);QuickSort3(a, hole+1, end);
}int main()
{int arr[] = { 9,8,7,6,5,4,3,2,1,0 };QuickSort3(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1);Print(arr, sizeof(arr) / sizeof(arr[0]));return 0;
}

---

（三）前后指针法

思想：

1、cur找到比key小的值，++prev，cur和prev位置的值交换，++cur
2、cur找到比key大的值，++cur

循环往复

其实就是将比key大的值向右扔，将比key小的值向左扔。

注：

1、prev要么紧跟着cur
2、prev要么跟cur中间间隔着比key大的一段值区间

#include<stdio.h>//打印
void Print(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}//交换
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//三数取中
int GetMidnum(int* a, int left, int right)
{int mid = (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//a[left]<a[mid]{if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}
}//快排——前后指针法
void QuickSort4(int* a, int left, int right)
{if (left >= right){return;}int mid = GetMidnum(a, left, right);Swap(&a[left], &a[mid]);int keyi = left;int prev = left;int cur = left + 1;while (cur <= right){if (a[cur] < a[keyi] && cur != ++prev){Swap(&a[cur], &a[prev]);}cur++;}//a[prev]永远都比a[keyi]小Swap(&a[prev], &a[keyi]);//更新keyikeyi = prev;//[left,keyi-1] keyi [keyi+1,right]QuickSort4(a, left, keyi - 1);QuickSort4(a, keyi+1, right);
}int main()
{int arr[] = { 9,8,7,6,5,4,3,2,1,0,11,13,14};QuickSort4(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1);Print(arr, sizeof(arr) / sizeof(arr[0]));return 0;
}

---

（四）小区间优化

①主要针对递归层数太多的情况。

②小区间优化需要用到直接插入排序，不了解的朋友可以先移步直接插入排序

#include<stdio.h>
#include"InsertSort.h"//打印
void Print(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}//交换
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//三数取中
int GetMidnum(int* a, int left, int right)
{int mid = (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//a[left]<a[mid]{if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}
}//快排——前后指针法
int _QuickSort5(int* a, int left, int right)
{int mid = GetMidnum(a, left, right);Swap(&a[left], &a[mid]);int keyi = left;int prev = left;int cur = left + 1;while (cur <= right){if (a[cur] < a[keyi] && cur != ++prev){Swap(&a[cur], &a[prev]);}cur++;}//a[prev]永远都比a[keyi]小Swap(&a[prev], &a[keyi]);//更新keyikeyi = prev;return keyi;
}void QuickSort5(int* a, int left, int right)
{if (left >= right){return;}if (right - left + 1 > 10){int keyi = _QuickSort5(a, left, right);//[left,keyi-1] keyi [keyi+1,right]QuickSort5(a, left, keyi - 1);QuickSort5(a, keyi + 1, right);}//小区间优化else{IsertSort(a+left, right - left + 1);}
}int main()
{int arr[] = { 9,8,7,6,5,4,3,2,1,0,11,2,4,45,33 };QuickSort5(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1);Print(arr, sizeof(arr) / sizeof(arr[0]));return 0;
}

---

（五）非递归写法

此处是用栈来辅助改成循环，需要用到栈。

思想：

①将初始区间入栈

②从栈中取一段区间进行单趟快排并分割

③将分割出的子区间入栈（区间内元素数量>=2）

#include<stdio.h>
#include"Stack.h"//打印
void Print(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}//交换
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//三数取中
int GetMidnum(int* a, int left, int right)
{int mid = (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//a[left]<a[mid]{if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}
}//快排——前后指针法
int _QuickSort6(int* a, int left, int right)
{int mid = GetMidnum(a, left, right);Swap(&a[left], &a[mid]);int keyi = left;int prev = left;int cur = left + 1;while (cur <= right){if (a[cur] < a[keyi] && cur != ++prev){Swap(&a[cur], &a[prev]);}cur++;}//a[prev]永远都比a[keyi]小Swap(&a[prev], &a[keyi]);//更新keyikeyi = prev;return keyi;
}//快排——非递归形式
void QuickSort6(int* a, int left, int right)
{ST st;StackInit(&st);//将初始区间入栈StackPush(&st, right);StackPush(&st, left);while (!Empty(&st)){int begin = StackTop(&st);StackPop(&st);int end = StackTop(&st);StackPop(&st);//分割母区间int keyi = _QuickSort6(a, begin, end);//[begin,keyi-1]  keyi  [keyi+1,end]//将子区间入栈(元素>=2)if (keyi + 1 < end){StackPush(&st, end);StackPush(&st, keyi+1);}if (begin < keyi - 1){StackPush(&st, keyi - 1);StackPush(&st, begin);}}StackDestroy(&st);
}int main()
{int arr[] = { 9,7,8,5,4,6,3,1,2,0 };QuickSort6(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1);Print(arr, sizeof(arr) / sizeof(arr[0]));return 0;
}

---

感谢阅读，本文如有疏漏不当之处，烦请各位指正。