LeetCode-912-排序数组

一：题目描述：

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

二：示例与提示

示例 1:

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

示例 2:

1 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

三：思路

实现快速排序

之前大一时候用C语言实现过快速排序

想想当时思路去想这个快排，还是下了很多的功夫

随意列出10个无序的数字，需要用到i，j两个变量，i在这列数的最左边，j在这列数的最右边，在这列数中随意找到一个数设置基准值（这里为了方便将第一个数设置为基准），首先让j向左移动，让i向右移动。

j找到一个比基准值小的数2停下来，然后i向右移动找到比基准值大的数6停下来，然后将i，j所指向的数进行交换。

交换后，j继续向左移动找到比基准值小的数4停下来，然后i向右移动找到比基准值大的数7停下来，然后将i，j所指向的数进行交换。

接下来j继续向左移动找到比基准值小的数3，i向右移动和j碰面，此时i和j在同一个位置上停下来，此时将i和j所指向的数和基准值进行交换，即将3和5进行交换。

即基准值归位后，基准值左边的都是小于基准值5的数，在基准值右边的都是大于基准值5的数。

这里需要提一点的是，为什么每次都需要j先移动，因为当最后i和j相碰时，此时所指向的是j寻找到比基准值小的数字，然后和基准值交换能确保基准值左边的都是小于基准值的数字，但是如果i先右边移动的话，最后i和j相碰时，i和j所指向的是i寻找得比基准值大的数，此时和基准值相交换，基准值左边是有一个比基准值大的数，没有达到我们需要的排序效果。

之后我们将5左边的拉出来再进行排序，此时选的基准值是3，根据原先的流程再来一遍。

这就是快速排序的逻辑。

最后总结下快排的步骤和注意点：

1.选取基准点
2.永远是j先向左移动，i再向右移动
3.当i，j碰面时候，将i和j所指向的数和基准值交换
4.然后处理左半边和右半边（递归）

四：代码 + 复杂度分析

快速排序

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    quickSort(nums, 0, nums.length - 1)
    return nums
};

const quickSort = (nums, left, right) => {
    //终止条件
    if(left >= right) {
        return 
    }
    //单层逻辑
    //i, j是需要移动的指针
    let i = left
    let j = right
    //基准值永远是最左边的元素
    let temp = nums[left]
    while(i < j) {
        //右边先移动
        //两个条件判断 
        //右边找小于基准值的
        while(nums[j] >= temp && i < j) {
            j--
        }
        //左边移动 
        //左边找大于基准值的
        while(nums[i] <= temp && i < j) {
            i++
        }
        //找到对应要交换的值交换
        let t = nums[i]
        nums[i] = nums[j]
        nums[j] = t

    }
    //将I和j同时指向的元素与基准值交换
    nums[left] = nums[i]
    nums[i] = temp
    //调用递归 分冶
    quickSort(nums, left, i - 1)
    quickSort(nums, i + 1, right)
}

时间复杂度：O(nlogn)
- 最好情况下的时间复杂度为O(nlogn)。
- 最坏情况下的时间复杂度为O(n^2)。
- 在平均情况下，快速排序的时间复杂度为O(nlogn)