【排序】快速排序实现

目录

一、快速排序是什么？

二、左右指针法

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];

总结

        抓住快排的思想要点，加上调试即可快速实现出排序算法。