力扣—912. 排序数组

912. 排序数组

题目:

给你一个整数数组 nums，请你将该数组升序排列。

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

示例：

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

提示：

• 1 <= nums.length <= 5 * 104
• -5 * 104 <= nums[i] <= 5 * 104

整体思路：快速排序

以第一个元素为基准值，从第一个元素开始与基准值比较

1如果大于基准值：将元素与第--j（因为j在所有元素最后面）个交换

2如果小于基准值：将元素与第++i（因为i在所有元素最前面）个交换

3相等就直接去比较下一个元素

   5，2，3，1

i  L                R  j

代码：

class Solution {
public:
    void Quick(vector<int> &arr,int L, int R) {
        if(L >= R) return;//递归结束条件
        int i = L - 1;//i在所有元素最前面
        int j = R + 1;//j在所有元素最后面
        int index = L;//从第一个元素开始比较
        int temp = arr[L];//以第一个元素最为基准值
        while(index < j){//如果index和j在同一位置结束循环
            if(arr[index] > temp) swap(arr[--j], arr[index]);//1
            else if(arr[index] < temp) swap(arr[++i], arr[index]);//2
            else index++;//3
        }
        //此时以基准值为中心，基准值前面都是比基准值小的，基准值后面都是比基准值大的
        //但是这两部分内部还没有排好序，所以递归将两边再排好
        Quick(arr, L, i);//比基准值小的部分
        Quick(arr, j, R);//比基准值大的部分

    }
    vector<int> sortArray(vector<int>& nums){
        if(nums.size() == 1) return nums;//长度等于1就不用排了直接输出即可
        Quick(nums, 0, nums.size() - 1);//调用函数进行快排
        return nums;//返回排好的数组
    }
};