题解 | #排序#

思路：

1、选出一个key，一般是最左边或是最右边的。

2、定义一个begin和一个end，begin从左向右走，end从右向左走。（需要注意的是：若选择最左边的数据作为key，则需要end先走；若选择最右边的数据作为key，则需要bengin先走）。

3、在走的过程中，若end遇到小于key的数，则停下，begin开始走，直到begin遇到一个大于key的数时，将begin和right的内容交换，end再次开始走，如此进行下去，直到begin和end最终相遇，此时将相遇点的内容与key交换即可。（选取最左边的值作为key）

4.此时key的左边都是小于key的数，key的右边都是大于key的数

5.将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作，此时此部分已有序

————————————————

版权声明：本文为CSDN博主「双鱼211」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接：https://blog.csdn.net/weixin_50886514/article/details/119045154

/*
思路：
1、选出一个key，一般是最左边或是最右边的。
2、定义一个begin和一个end，begin从左向右走，end从右向左走。（需要注意的是：若选择最左边的数据作为key，则需要end先走；若选择最右边的数据作为key，则需要bengin先走）。
3、在走的过程中，若end遇到小于key的数，则停下，begin开始走，直到begin遇到一个大于key的数时，将begin和right的内容交换，end再次开始走，如此进行下去，直到begin和end最终相遇，此时将相遇点的内容与key交换即可。（选取最左边的值作为key）
4.此时key的左边都是小于key的数，key的右边都是大于key的数
5.将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作，此时此部分已有序
————————————————
版权声明：本文为CSDN博主「双鱼211」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_50886514/article/details/119045154
*/

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    
    // 怎么少得了交换值函数呢
    void MySwap(int &a, int &b){
        int temp = 0;
        temp = a;
        a = b;
        b = temp; 
    }

    void MyQuickSort(vector<int> &arr, int begin, int end){
        // 有点二分法的影子精髓
        // begin ... key ... end
        // left smaller(begin), end first
        if(begin >= end){
            return;
        }
        // 新定义lef,right是为了保留begin,end
        int left = begin, right = end;
        int key = left;
        // 假设，left=0, right = end
        while(left < right){
            // 右边要选择小于key的元素,不符合条件的元素
            while(arr[right] >= arr[key] && left < right)
            {
                --right;
            }
            // 左边要选大于key的元素,不符合条件的元素
            while(arr[left] <= arr[key] && left< right){
                ++left;
            }
            // arr[right] < key <  arr[left], 则需要交换
            MySwap(arr[left], arr[right]);
        }
        //循环完后left == right, 再继续下一趟，直到元素只有一个
        MySwap(arr[left], arr[key]);
        MyQuickSort(arr, begin, left-1);//左边
        MyQuickSort(arr, right+1, end);//右边
    }
    vector<int> MySort(vector<int>& arr) {
        int LabBegin = 0;
        int LaEnd = arr.size()-1;
        MyQuickSort(arr, LabBegin, LaEnd);
        return arr;
    }
};