Node.js快速排序

举报
zhaoolee 发表于 2022/02/24 23:54:33 2022/02/24
【摘要】 题目 https://leetcode-cn.com/problems/sort-an-array /** * @param {number[]} nums * @return {number[]} */ var sortArray = function (nums) { function quickSort(slow, fast) { //...

题目 https://leetcode-cn.com/problems/sort-an-array

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {

    function quickSort(slow, fast) {


        // 1. 选择第一个元素作为基准, 并将第一个位置设置void 0

        let base = nums[slow];
        nums[slow] = void 0;


        // 2. 设置两个指针,left 为 slow索引, right 为fast 索引
        let left = slow;
        let right = fast;

        // 3. 如果left < rigth 则不断循环排序, 如果left === right, 则停止排序

        while (left < right) {

            if (nums[left] === void 0) {
                // 3.1 从right指针开始,如果right指向的值小于等于base, 
                // 则 left 接收right的值,right节点设置为空,left加1
                if (nums[right] < base) {
                    nums[left] = nums[right];
                    nums[right] = void 0;
                    left = left + 1;
                }
                // 如果right指针指向的值,大于等于base, 则,rigth - 1
                else {
                    right = right - 1;
                }
            } else if (nums[right] === void 0) {
                if (nums[left] >= base) {
                    nums[right] = nums[left];
                    nums[left] = void 0;
                    right = right - 1;
                }
                else {
                    left = left + 1;
                }
            } else {
                console.log("不可达")
            }
        }
        // 将base放入left和rigth重合的位置
        nums[left] = base;

        // 如果base左侧区域差值大于等于1,则开始递归调用

        if ((left - 1) - slow > 0) {
            quickSort(slow, left - 1);
        }

        // 如果base右侧区域差值大于1,则开始递归调用
        if (fast - (right + 1) > 0) {
            quickSort(right + 1, fast);
        }


        return


    }

    if (nums.length === 1) {
        return nums;
    } else {
        quickSort(0, nums.length - 1);
    }
    return nums;

};
leetcode

文章来源: www.jianshu.com,作者:zhaoolee,版权归原作者所有,如需转载,请联系作者。

原文链接:www.jianshu.com/p/d63620b92557

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200