前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >js 实现快速排序

js 实现快速排序

作者头像
蓓蕾心晴
发布2022-09-24 14:54:07
7910
发布2022-09-24 14:54:07
举报
文章被收录于专栏:前端小叙前端小叙
代码语言:javascript
复制
// 快速排序
// 稳定性
// 快速排序是以两个游标(指针)双向遍历,当两个指针相遇则遍历结束,并将相遇位置与基准值进行交换,递归出口为左游标>=右游标
// 快速排序的每一轮处理其实就是将这一轮的基准数归位,直到所有的数都归位为止,排序就结束了
function quickSort(arr) {
    let tmpArr = [...arr]; //复制数组
    return quick(tmpArr, 0, tmpArr.length - 1);
}
function quick(arr, i, j) {
    if (j - i <= 0) return; //说明数组只有一个值了
    let left = i,
        right = j;
    let base = left; //以左边第一个为基准值
    let center = arr[base];
    while (left < right) {
        //开始循环了
        //每次循环包括从右往左和从左往右
        while (left < right && center < arr[right]) {
            right--;
        }
        if (left < right) {
            //找到了,交换位置
            arr[base] = arr[right];
            arr[right] = center;
            base = right;
            left++;
        }
        while (left < right && center > arr[left]) {
            //找到了,交换位置
            left++;
        }
        if (left < right) {
            arr[base] = arr[left];
            arr[left] = center;
            base = left;
            right--;
        }
    }
    quick(arr, i, base - 1); //分别处理左右两侧了
    quick(arr, base + 1, j);
    return arr;
}
console.log(quickSort([6, 3, 7, 8, 2, 4, 0, 1, 6, 5]));
console.log(quickSort([1, 2, 3, 4, 5, 6, 7, 8, 9, 9]));


function quickSort( arr ) {
    if(arr.length <= 1) return arr;
    const num = arr[0];
    let left = [], right = [];
    for(let i = 1;i < arr.length; i++) {
        if(arr[i]<=num) left.push(arr[i]);
        else right.push(arr[i]);
    }
    return quickSort(left).concat([num],quickSort(right));
}
console.log(quickSort([6, 3, 7, 8, 2, 4, 0, 1, 6, 5]));
console.log(quickSort([1, 2, 3, 4, 5, 6, 7, 8, 9, 9]));

参考链接:

https://www.imooc.com/article/73247

https://blog.csdn.net/xinxxxxxxxxx/article/details/123032933

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-09-03,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档