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]);//1else if(arr[index] < temp) swap(arr[++i], arr[index]);//2else 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;//返回排好的数组}
};