快速排序算法
快速排排序是效率非常高的排序算法之一。
它的基本思想是：首先选择一个基准值，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都小于基准值，另一部分所有数据都大于基准值，并且经过一趟排序，所选择基准值已经换到了在它应该在的正确位置。然后再通过此方法堆这两部分数据分别进行快速排序，整个排序过程可以递归实现。但是具体的将待排序的数据分为两个部分的方法，却有很多：
举一个例子：
| 数组下标 | 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 6
swap(arr[begin], arr[right-1]);
return begin;
}
void QuickSort(int *arr, int left, int right)
{
if (left < right)
{
size_t p = Pation1(arr, left, right);
QuickSort(arr, left, p);
QuickSort(arr, p + 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 6
return begin;
}
void QuickSort(int *arr, int left, int right)
{
if (left < right)
{
size_t p = Pation2(arr, left, right);
QuickSort(arr, left, p);
QuickSort(arr, p + 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 p = Pation3(arr, left, right);
QuickSort(arr, left, p);
QuickSort(arr, p + 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 p = Pation3(arr, left, right);
s.push(p);//保存基准值左边数据的边界
s.push(left);
s.push(right);//保存基准值右边的数据的边界
s.push(p + 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;
else
return mid;
}
else
{
if (arr[left] < arr[mid])
return left;
else if (arr[right - 1] > arr[mid])
return right - 1;
else
return mid;
}
}相关阅读
假设我们现在对“6 1 2 7 9 3 4 5 10 8”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数（不
前言这些一个系列的文章，主要是自己学习算法和数据结构的一些笔记整理。从最简单开始，一步步深入，都是自己学习过程中的领悟。对于程
快速排序算法是一种分治排序算法.它将数组划分为两个部分,然后分别对两个部分进行排序.我们将看到,划分的准确位置取决于输入数组