数据结构-快速排序的三种实现方式及其优化

浅浅的花香味﹌ 2022-06-03 23:52 182阅读 0赞

#### **快速排序初步了解：** ####

##### 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。后面将提供一种快排的优化方式可以尽量避免出现Ο(n2)的复杂度。 #####

##### **基本思路** #####

##### 1.先从数据当中找出一个数据作为参照数 #####

##### 2.然后开始分区操作，大于参照数的就放到参照数右边，小于参照数的就放到参照数的左边. #####

##### 3.然后对左右分区继续进行该操作，知道区间里面只有一个数据的是时候，快排完成 #####

--------------------

#### **排序效果：** ####

![这里写图片描述][SouthEast]

--------------------

#### **一、左右指针法** ####

##### <1>**思路：**给定一个数组，再给定左右区间的下标值left，right（此处我给的是左右闭区间），给定一个基准值为arr\[right\]，接下来就是循环和递归的过程。单趟过程中，先让begin记录该区间的第一个下标（就像一个指针指向头一样），end记录最后一个值的下标，基准值为该区间的最后一个值。循环过程中，begin记录比基准值大的值，end记录比基准值小的值，判断如果begin和end还未相遇，则交换对应的值，再进行循环直至begin和end相遇。相遇后此时单趟排序完成，现在begin和end指向一个元素，该元素左侧都是比基准值小的值，右侧都是比基准值大的，将begin对应的值与基准值进行交换，开始递归左半区间和右半区间，重复上述过程。 #####

--------------------

##### <2>**图示单趟过程：** #####

![这里写图片描述][SouthEast 1]

##### 整体过程如下： #####

##### 1 5 6 2 7 4 #####

##### 1 2 6 5 7 4 #####

##### 1 2 4 5 7 6 #####

##### 1 2 4 5 6 7 #####

--------------------

##### <3>**实现代码** #####

//左右指针法
    void LRPoint(int* arr, int left, int right)
    {
        if (left >= right)
            return;
    
        assert(arr);
        int begin = left;
        int end = right;
        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]);
        }
    
        //begin end指向一起，与key交换
        swap(arr[begin], arr[right]);
    
        LRPoint(arr, left,begin - 1);
        LRPoint(arr, begin+1,right);
    }

--------------------

#### **二、挖坑法** ####

#### **<1>思路**：大体上如同左右指针法，但是左右指针法是在begin和end符合条件的值后，将begin和end对应的值进行交换；而挖坑法则是边找边替换，在最后再将key填入坑中。图中橙色元素由于此处的值赋值到了别处，可以形象的看做是一个“坑”。 ####

--------------------

##### <2>**图示单趟过程：** #####

![这里写图片描述][SouthEast 2]

##### 整体过程如下： #####

##### 1 5 6 2 7 4 #####

##### 1 5 6 2 7 5 #####

##### 1 2 6 2 7 5 #####

##### 1 2 6 6 7 5 #####

##### 1 2 4 6 7 5 #####

##### 1 2 4 6 7 6 #####

##### 1 2 4 5 7 6 #####

##### 1 2 4 5 7 7 #####

##### 1 2 4 5 6 7 #####

--------------------

##### <3>**实现代码** #####

void PitPoint(int* arr, int left, int right)
    {
        if (left >= right)
            return;
    
        int begin = left;
        int end = right;
        int key = arr[right];
    
        while (begin < end)
        {
            while (begin < end && arr[begin] <= key)
                begin++;
            arr[end] = arr[begin];
    
            while (begin < end && arr[end] >= key)
                end--;
            arr[begin] = arr[end];
        }
        arr[end] = key;
    
        PitPoint(arr, left, begin - 1);
        PitPoint(arr, begin + 1, right);
    }

--------------------

#### **三、前后指针法** ####

##### **<1>思路**：一开始使用cur记录left位置，prev记录cur的前一个位置，利用cur来寻找比基准值小的值，需要注意的是只有当**arr\[cur\] < arr\[right\]**和**++prev != cur**两个条件都满足才进行交换，此处还涉及如果arr\[cur\] < arr\[right\]不满足则不进行prev++，当条件都满足时进行交换，出了循环后将基准值放在prev++的位置。看着代码自己缕一遍就会发现规律了。 #####

--------------------

##### <2>**图示单趟过程：** #####

![这里写图片描述][SouthEast 3]

##### 整体过程如下： #####

##### 1 5 6 2 7 4 #####

##### 1 2 6 5 7 4 #####

##### 1 2 4 5 7 6 #####

##### 1 2 4 5 6 7 #####

--------------------

##### <3>**实现代码** #####

void FBPoint(int* arr, int left, int right)
    {
        if (left >= right)
            return;
    
        int cur = left;
        int prev = left - 1;
    
        while (cur < right)
        {
            if (arr[cur] < arr[right] && ++prev != cur)
                swap(arr[cur], arr[prev]);
            ++cur;
        }
        swap(arr[++prev], arr[right]);
    
        FBPoint(arr, left, prev - 1);
        FBPoint(arr, prev + 1, right);
    }

#### **四、非递归实现** ####

##### **<1>思路：** #####

##### 用栈来模拟实现递归操作，每次从栈中取出对应的左右边界进行操作；在push边界的顺序与取栈顶数据作为左右边界的顺序要对应。 #####

--------------------

##### **<2>实现代码：** #####

void NRQuickSort(int* arr, int sz)
    {
        assert(arr);
        stack<int> s;
        int left = 0;
        int right = sz;
        s.push(right);
        s.push(left);
        while (!s.empty())
        {
            left = s.top();
            s.pop();
            right = s.top();
            s.pop();
    
            if (left < right)
            {
                int begin = left;
                int end = right;
                int key = arr[right];
    
                while (begin < end)
                {
                    //1,5,6,2,7,4
                    while (begin < end && arr[begin] <= key)
                        begin++;
                    while (begin < end && arr[end] >= key)
                        end--;
    
                    if (begin < end)
                        swap(arr[begin], arr[end]);
                }
                swap(arr[begin], arr[right]);
    
                s.push(right);
                s.push(begin + 1);
                s.push(begin - 1);
                s.push(left);
            }
        }
    }

--------------------

#### **五、优化** ####

##### **<1>通过三数取中法选取key的下标：** #####

##### 当按照上面的代码如果每次取key的时候取到了待排序列中最大的或者最小的. 也就是序列有序的时候，快速排序的时间复杂度为O(N^2)，我们可以通过选择合适的key值来进行优化：也就是所谓的三数取中法（给定左右区间的下标，计算出中间下标，并返回这三个值中不大不小的那个），将该下标所对应的值和区间最右侧的值进行交换即可。拿左右指针法优化举例： #####

int GetMid(int* a, int left, int right)
    {
        int mid = left + ((right - left) >> 1);
    
        // left mid
        if (a[left] < a[mid])
        {
            if (a[right] < a[left])
                return left;
            else if (a[right] > a[mid])
                return mid;
            else
                return right;
        }
        else
        {
            //mid  left
            if (a[right] < a[mid])
                return mid;
            else if (a[right] < a[left])
                return left;
            else
                return right;
        }
    }
    
    
    void LRPoint(int* arr, int left, int right)
    {
        if (left >= right)
            return;
    
        assert(arr);
        int begin = left;
        int end = right;
        swap(arr[end], arr[GetMid(arr, left, right)]);
        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]);
        }
    
        //begin end指向一起，与key交换
        swap(arr[begin], arr[right]);
    
        LRPoint(arr, left,begin - 1);
        LRPoint(arr, begin+1,right);
    }

--------------------

##### **<2>小区间优化：** #####

##### **思路：**由于递归需要建立栈帧消耗十分大，我们可以判断如果该区间内的元素值小于n（可以取5~15，视情况而定）的时候直接采取插入排序来处理该区间内的数据，就不必再多建立那么多栈帧，从而提高效率。具体实现就不给出了，只需要添加一个判断条件再引入插入排序即可。 #####

[SouthEast]: /images/20220604/f973c9d6092d4d36b53f635e61e74ff8.png
[SouthEast 1]: /images/20220604/366b1e4cd10f49b9ade19cbdbfe48341.png
[SouthEast 2]: /images/20220604/7833ad8648704e409ee669f48eac72d6.png
[SouthEast 3]: /images/20220604/bd5fb14aa2f54f9abe909f4b34a96845.png