【数据结构】排序算法——快速排序
快速排排序是效率非常高的排序算法之一。
它的基本思想是：首先选择一个基准值，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都小于基准值，另一部分所有数据都大于基准值，并且经过一趟排序，所选择基准值已经换到了在它应该在的正确位置。然后再通过此方法堆这两部分数据分别进行快速排序，整个排序过程可以递归实现。但是具体的将待排序的数据分为两个部分的方法，却有很多：
举一个例子：
| 数组下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 待排序数据 | 7 | 1 | 4 | 8 | 2 | 0 | 9 | 6 | 3 | 5 |
我们取最后一个元素5为基准值key
第一种方法：
- 定义两个指针，begin和end分别指向第一个元素和最后一个元素，基准值
key=arr[end]; - begin从前向后移动，当遇到大于key的时候停下来，end从后向前移动，当遇到小于key的时候停下，交换begin和end对应的元素；
重复上一步，直至begin与end相遇，begin对应的元素与key值进行交换。
此方法的实现代码如下：size_t Pation1(int *arr, int left, int right)
{size_t begin = left;size_t end = right - 1;int key = arr[end];while (begin < end){while (begin < end && arr[begin] <= key)begin++;while (begin < end && arr[end] >= key)end--;if (begin < end)swap(arr[begin], arr[end]);}if (begin != right-1)// 1 2 4 5 6swap(arr[begin], arr[right-1]);return begin;
}
void QuickSort(int *arr, int left, int right)
{if (left < right){size_t div = Pation1(arr, left, right);QuickSort(arr, left, div);QuickSort(arr, div + 1, right);}
}
第二种方法：挖坑法
- 定义两个指针，begin和end分别指向第一个元素和最后一个元素，基准值
key=arr[end]; - begin从前向后移动，当遇到大于key的时候停下来，将begin位置的数据放置end处，begin变为坑；
- end从后开始向前移动，当遇到小于key的时候停下来，将end处的数据放置坑（begin）处，end变为坑，begin开始移动；
- 重复2、3两步，直至begin与end相遇，最后的一个坑放key。
此方法的实现代码如下：
size_t Pation2(int *arr, size_t left, size_t right){size_t begin = left;size_t end = right - 1;int key = arr[end];while (begin < end){while (begin < end && arr[begin] <= key)begin++;if (begin < end)arr[end--] = arr[begin];while (begin < end && arr[end] >= key)end--;if (begin < end)arr[begin++] = arr[end];}if (begin != right-1)arr[begin] = key;//1 2 3 4 5 6return begin;}void QuickSort(int *arr, int left, int right){if (left < right){size_t div = Pation2(arr, left, right);QuickSort(arr, left, div);QuickSort(arr, div + 1, right);}}
第三种方法：追赶法
- 定义两个指针，cur和pre分别指向第一个元素和-1，基准值
key=arr[end]; - cur从前向后移动，当遇到大于key的时候，cur++；当遇到小于key的时候，++pre后，如果pre与cur不在同一位置，则交换两个数据；
- 重复第2步，直至cur不小于right边界，再++pre，如果pre不与right在同一个位置，那么交换两个数据。
如下图所示：
此方法的实现代码如下：
size_t Pation3(int *arr, size_t left, size_t right){int index = GetMid(arr, left, right);if (index != right - 1)swap(arr[index], arr[right - 1]);int key = arr[right - 1];int cur = left;int pre = cur - 1;while (cur < right){if (arr[cur] < key && ++pre != cur)swap(arr[pre], arr[cur]);cur++;}if (++pre != right)swap(arr[pre], arr[right-1]);return pre;}void QuickSort(int *arr, int left, int right){if (left < right){size_t div = Pation3(arr, left, right);QuickSort(arr, left, div);QuickSort(arr, div + 1, right);}}
以上实现的快速排序是递归的，递归也是可以转换成循环，我们利用循环+栈来实现，非递归的快排。
#include <stack>void QuickSort(int *arr, size_t size){int left = 0;int right = size;stack<int> s;s.push(right);s.push(left);while (!s.empty()){left = s.top();s.pop();right = s.top();s.pop();if (left < right){size_t div = Pation3(arr, left, right);s.push(div);//保存基准值左边数据的边界s.push(left);s.push(right);//保存基准值右边的数据的边界s.push(div + 1);}}}
优化
快速排序时间复杂度一般为O(N*logN)，最坏为O(N*N)，快速排序的性能取决于递归树的深度，在最优的情况下，递归树深度为logN，最坏的情况下，递归深度为N。所以，基准值key的选择至关重要，如果选择的不合适，那么递归深度将会变大，从而造成效率下降。
对此，我们的解决方法是：三数取中法，顾名思义，就是在待排序数组中的首元素、中间元素、最后一个元素，这三个数据中选择中间大小的数据。
代码如下：
size_t GetMid(int *arr, size_t left, size_t right){size_t mid = left + ((right - left) >> 1);if (arr[left] < arr[right-1]){if (arr[left] > arr[mid])return left;else if (arr[right - 1] < arr[mid])return right - 1;elsereturn mid;}else{if (arr[left] < arr[mid])return left;else if (arr[right - 1] > arr[mid])return right - 1;elsereturn mid;}}
旧城等待，
不念不忘少年蓝@
港控/mmm°
还没有评论，来说两句吧...