【数据结构】排序算法——快速排序

谁借莪１个温暖的怀抱￠ 2022-05-25 11:13 238阅读 0赞

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

<table> 
 <thead> 
  <tr> 
   <th>数组下标</th> 
   <th>0</th> 
   <th>1</th> 
   <th>2</th> 
   <th>3</th> 
   <th>4</th> 
   <th>5</th> 
   <th>6</th> 
   <th>7</th> 
   <th>8</th> 
   <th>9</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>待排序数据</td> 
   <td>7</td> 
   <td>1</td> 
   <td>4</td> 
   <td>8</td> 
   <td>2</td> 
   <td>0</td> 
   <td>9</td> 
   <td>6</td> 
   <td>3</td> 
   <td>5</td> 
  </tr> 
 </tbody> 
</table>

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

1.  定义两个指针，begin和end分别指向第一个元素和最后一个元素，基准值`key=arr[end]`;
2.  begin从前向后移动，当遇到大于key的时候停下来，end从后向前移动，当遇到小于key的时候停下，交换begin和end对应的元素；
3.  重复上一步，直至begin与end相遇，begin对应的元素与key值进行交换。  
    ![这里写图片描述][70]  
    此方法的实现代码如下：

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.  定义两个指针，begin和end分别指向第一个元素和最后一个元素，基准值`key=arr[end]`;
2.  begin从前向后移动，当遇到大于key的时候停下来，将begin位置的数据放置end处，begin变为坑；
3.  end从后开始向前移动，当遇到小于key的时候停下来，将end处的数据放置坑（begin）处，end变为坑，begin开始移动；
4.  重复2、3两步，直至begin与end相遇，最后的一个坑放key。  
    ![这里写图片描述][70 1]

此方法的实现代码如下：

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.  定义两个指针，cur和pre分别指向第一个元素和-1，基准值`key=arr[end]`;
2.  cur从前向后移动，当遇到大于key的时候，cur++；当遇到小于key的时候，++pre后，如果pre与cur不在同一位置，则交换两个数据；
3.  重复第2步，直至cur不小于right边界，再++pre，如果pre不与right在同一个位置，那么交换两个数据。

如下图所示：  
![这里写图片描述][70 2]  
![这里写图片描述][70 3]  
此方法的实现代码如下：

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;
            else
                return mid;
        }
        else
        {
            if (arr[left] < arr[mid])
                return left;
            else if (arr[right - 1] > arr[mid])
                return right - 1;
            else
                return mid;
        }
    }

[70]: /images/20220525/2b42fc3b5dfb4673a39d5f07e5da36ed.png
[70 1]: /images/20220525/44b579493968456db977acd18c952ed7.png
[70 2]: /images/20220525/1a34be4ffe54484aba8983464ff21343.png
[70 3]: /images/20220525/c1dcca9c369443b59820fccd1e701119.png