当前位置：首页 > article >正文

代码随想录--排序算法

article 2025/2/28 20:02:39

912.排序数组

快速排序

思路：

		1.  设置一个pivot
		2. 将小于nums[pivot]的值 放在左边
		3. 将 大于nums[pivot]的值  放在 右边
		4. 递归调用

注意：必须先比较nums[high] 与pivot

代码：

class Solution {

    int partition(vector<int>&nums, int low, int high){
        int pivot = nums[low];
        while(low<high){
            while(low <high && nums[high]>=pivot){
                high--;
            }nums[low] = nums[high];

            while(low<high && nums[low]<=pivot){
                low++;
            }nums[high] = nums[low];

        }
        nums[low] = pivot;
        return low;
    }

    void quiksort(vector<int>&nums, int low, int high){
        if(low<high){
            int pos = partition(nums, low, high);
            quiksort(nums, low, pos-1);
            quiksort(nums, pos+1, high);
        }
    }

public:
    vector<int> sortArray(vector<int>& nums) {
        quiksort(nums, 0, (int)nums.size()-1);
        return nums;
    }
};