JavaScript冒泡、插入、快速排序

1.冒泡排序,性能已优化

function bubbleSort(ary) {
        var len = ary.length, flag = null;
        if (len > 1) {
            for (var i = 0; i < len - 1; i++) {
                flag = false;//位置变更标识符,可以优化性能
                for (var j = 0; j < len - 1 - i; j++) {
                    //console.log(i);
                    if (ary[j] > ary[j + 1]) {
                        var temp = ary[j];
                        ary[j] = ary[j + 1];
                        ary[j + 1] = temp;
                        flag = true;//有位置交换则改变flag的值
                    }
                }
                if (!flag) {//检测到上一轮已经没有过位置变更,就说明排序已经完成
                    break;
                }
            }
        }
        return ary;
    }
    var ary1 = [111, 99, 12, 32, 78, 88, 34];
    console.log(bubbleSort(ary1));

2.插入排序

function insertSort(ary) {
        var len = ary.length;
        if (len > 1) {
            for (var i = 1; i < len; i++) {
                if (ary[i] < ary[i - 1]) {  //当前项小于前一项的时候才向前插入
                    var cur = ary[i], j = i - 1;    //保存第i项的值,找到前一项的索引
                    while (j >= 0 && cur < ary[j]) {    //前一项存在且第i项的值小于前一项
                        ary[j + 1] = ary[j];        //当前比较项赋值为前一项的值
                        j--;                        //继续向前查找
                    }
                    ary[j + 1] = cur;           //将第i项插入到当前位置
                }
            }
        }
        return ary;
    }
    
    var ary2 = [111, 99, 12, 32, 78, 88, 34];
    console.log(insertSort(ary2));

3.快速排序

function quickSort(ary) {
        if (ary.length <= 1) {
            return ary;
        }
        var midIndex = Math.floor(ary.length / 2);
        var minItem = ary.splice(midIndex, 1)[0];
        var leftAry = [], rightAry = [];
        for (var i = 0; i < ary.length; i++) {
            var cur = ary[i];
            cur < minItem ? leftAry.push(cur) : rightAry.push(cur);
        }
        return quickSort(leftAry).concat(minItem, quickSort(rightAry));
    }
    var ary3 = [111, 99, 12, 32, 78, 88, 34];
    console.log(quickSort(ary3));

欢迎分享本文,转载请保留出处:前端ABC » JavaScript冒泡、插入、快速排序

赞 (0)
分享到:更多 ()

发表评论 0