【排序】快速排序实现
目录
一、快速排序是什么？
二、左右指针法
1.实现原理
2.代码如下：
三、挖坑法
1.实现原理
2.代码如下：
四、前后指针法
1.实现原理
2.代码如下：
五、三数取中
1.实现思想
2.代码如下：
3.使用方法
总结
前言
快排是公认的排序效率之王，加上三数取中与小区间优化更是无人能敌。
一、快速排序是什么？
快排分为三种实现方式：
①左右指针法
②挖坑法
③前后指针法
其中左右指针与挖坑法实现原理差不多一样：（只是挖坑法多创建一个临时变量存储坑中的数据）它们俩都是选大的的通过自己的方式放在后面，选出小的通过自己的方式放前面，通过递归就可将整个数组进行排序。
前后指针法同样是选大的放后面，选小的放前面，但是与上面两个不同的是它只从一头开始遍历。
二、左右指针法
1.实现原理
① 定义两个指针，一个从左边遍历，一个从右边遍历。
② 定义一个key值用来做比较的基准值。
③ 如果key是最左边的值，那么就让right先向左找小值，反之，就让left先找大值。
目的：在left与right相遇时，在与key值交换时能够交换大值（小值），否则会出现数据错误。
④ 假定key值定义为最左边的数字，
right向左走找比key值大的数据，找到后停下，
left向右走找比key值小的数据，找到后停下，
此时交换left与right对应的值，循环往复直至left与right相遇。
⑤ 相遇后，将相遇点与keyi对应的数据进行交换，此时数组将会达到key左边的数字都小于key，右边的数字都大于key，后续通过递归可实现整个数组的排序。
2.代码如下：
#include <stdio.h>void swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}
// 左右指针法
void QuickSort1(int* arr, int begin, int end)
{if (begin >= end){return;}int left = begin;int right = end;int keyi = left;while (left < right){// right向左找小while (left < right && arr[right] >= arr[keyi]){right--;}while (left < right && arr[left] <= arr[keyi]){left++;}// key的大值与小值进行换位swap(&arr[left], &arr[right]);}// 左右指针相遇，与key换位int meeti = left;swap(&arr[meeti], &arr[keyi]);QuickSort1(arr, begin, meeti - 1);QuickSort1(arr, meeti + 1, end);
}
int main()
{int arr[] = { 5,3,6,9,8,7,2,0,1,4 }; size_t len = sizeof(arr) / sizeof(arr[0]);QuickSort1(arr, 0, len - 1);return 0;
}三、挖坑法
1.实现原理
挖坑法与左右指针法大致相同。
① 选出一个key值，并将其所在的位置定为坑（坑可被覆盖 -> 放数据，坑中的数据被保存在了key中）
② 定义两个指针，一个从左边遍历，一个从右边遍历。
③同左右指针法相同，
如果key是最左边的值，那么就让right先向左找小值，反之，就让left先找大值。
目的：在left与right相遇时，在与key值交换时能够交换大值（小值），否则会出现数据错误。
④ 假定key值定义为最左边的数字：
right找到比key值大的数据停下，将此数入坑，同时right所在的位置变为新坑；
left向右走找比key值小的数据，找到后停下，将此数入坑，同时left所在的位置变为新坑；
循环此过程直至两指针相遇。
⑤ 将key值入坑，此时数组将会达到key左边的数字都小于key，右边的数字都大于key，后续通过递归可实现整个数组的排序。
2.代码如下：
// 挖坑法
void QuickSort2(int* arr, int begin, int end)
{if (begin >= end){return;}int left = begin;int right = end;int key = arr[left];int pivot = left;while (left < right){// right向左找小while (left < right && arr[right] >= key){right--;}// 入坑，更新坑位arr[pivot] = arr[right];pivot = right;// left向右找大while (left < right && arr[left] <= key){left++;}arr[pivot] = arr[left];pivot = left;}// 相遇，key值入坑arr[pivot] = key;QuickSort2(arr, begin, pivot - 1);QuickSort2(arr, pivot + 1, end);
}// 挖坑法
void QuickSort2(int* arr, int begin, int end)
{if (begin >= end){return;}int left = begin;int right = end;int key = arr[left];int pivot = left;while (left < right){// right向左找小while (left < right && arr[right] >= key){right--;}// 入坑，更新坑位arr[pivot] = arr[right];pivot = right;// left向右找大while (left < right && arr[left] <= key){left++;}arr[pivot] = arr[left];pivot = left;}// 相遇，key值入坑arr[pivot] = key;QuickSort2(arr, begin, pivot - 1);QuickSort2(arr, pivot + 1, end);
}
int main()
{int arr[] = { 5,3,6,9,8,7,2,0,1,4 }; size_t len = sizeof(arr) / sizeof(arr[0]);QuickSort1(arr, 0, len - 1);return 0;
}四、前后指针法
1.实现原理
① 定义两个指针，一前(cur)一后(prev)。
② 定义一个key值，用来作为单趟排序的基准值。
② 让前面的指针继续向前遍历，如果找到比key值小的，++prev后与其交换。
③ 重复②直至cur到达数组末尾，交换prev与keyi对应的数据。
④ 此时数组将会达到key左边的数字都小于key，右边的数字都大于key，后续通过递归可实现整个数组的排序。
2.代码如下：
// 前后指针法
void QuickSort3(int* arr, int begin, int end)
{if (begin >= end){return;}int left = begin;int right = end;int key = arr[left];int prev = left;int cur = prev + 1;while (cur <= end){if (arr[cur] < key && ++prev != cur)// 减少不必要的swap{swap(&arr[prev], &arr[cur]);}++cur;}swap(&arr[prev], &arr[begin]);QuickSort3(arr, begin, prev - 1);QuickSort3(arr, prev + 1, end);
}int main()
{int arr[] = { 5,3,6,9,8,7,2,0,1,4 }; size_t len = sizeof(arr) / sizeof(arr[0]);QuickSort3(arr, 0, len - 1);return 0;
}五、三数取中
1.实现思想
当待排序数组本来是逆序时，快排效率将降到最低，为O(N2)，每次都许哟啊对每个数进行交换位置2次，所以产生了三数去中的方法：
取得数组最开始、最末尾、最中间中的中间值来平衡key值。
2.代码如下：
// 三数取中
int GetMidIndex(int* arr, int begin, int end)
{int mid = (end - begin) / 2 + begin;if (arr[begin] < arr[end]){// begin < end < midif (arr[mid] > arr[end]){return end;}// mid < begin < endelse if (arr[mid] < arr[begin]){return begin;}// begin < mid < endelse{return mid;}}// end < beginelse{// mid < end < beginif (arr[mid] < arr[end]){return end;}//end < begin < midelse if(arr[mid] > arr[begin]){return begin;}else{return mid;}}
}3.使用方法
在取key值时仍可继续取left位置的值，但是在此之前做一次交换即可。
int index = GetMidIndex(arr, begin, end);swap(&arr[index], &arr[left]);int key = arr[left];
总结
抓住快排的思想要点，加上调试即可快速实现出排序算法。