【数据结构】排序算法——快速排序_快速排序怎么实现数据结构

　　快速排排序是效率非常高的排序算法之一。
　　它的基本思想是：首先选择一个基准值，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都小于基准值，另一部分所有数据都大于基准值，并且经过一趟排序，所选择基准值已经换到了在它应该在的正确位置。然后再通过此方法堆这两部分数据分别进行快速排序，整个排序过程可以递归实现。但是具体的将待排序的数据分为两个部分的方法，却有很多：
　　
举一个例子：

我们取最后一个元素5为基准值key
第一种方法：

1. 定义两个指针，begin和end分别指向第一个元素和最后一个元素，基准值key=arr[end];
2. begin从前向后移动，当遇到大于key的时候停下来，end从后向前移动，当遇到小于key的时候停下，交换begin和end对应的元素；
3. 重复上一步，直至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 div = Pation1(arr, left, right);
        QuickSort(arr, left, div);
        QuickSort(arr, div + 1, right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

第二种方法：挖坑法

1. 定义两个指针，begin和end分别指向第一个元素和最后一个元素，基准值key=arr[end];
2. begin从前向后移动，当遇到大于key的时候停下来，将begin位置的数据放置end处，begin变为坑；
3. end从后开始向前移动，当遇到小于key的时候停下来，将end处的数据放置坑（begin）处，end变为坑，begin开始移动；
4. 重复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 div = Pation2(arr, left, right);
        QuickSort(arr, left, div);
        QuickSort(arr, div + 1, right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

第三种方法：追赶法

1. 定义两个指针，cur和pre分别指向第一个元素和-1，基准值key=arr[end];
2. cur从前向后移动，当遇到大于key的时候，cur++；当遇到小于key的时候，++pre后，如果pre与cur不在同一位置，则交换两个数据；
3. 重复第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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

以上实现的快速排序是递归的，递归也是可以转换成循环，我们利用循环+栈来实现，非递归的快排。

#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);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

---

优化

　　快速排序时间复杂度一般为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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22