chaihongjun.me

【算法】javascript冒泡排序和快速排序

1.冒泡排序

相邻的两个元素比较,如果前面一个比后面的大,就交换一下位置。

    function bubbleSort(array) {
        for (var i = 0; i < array.length - 1; i++) {
            for (var j = 0; j < array.length - 1 - i; j++) {
                var cur = array[j], next = array[j + 1];
                if (cur > next) {
                    var temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        } 
    }
    var array = [99, 22, 45, 11, 36, 76, 56, 89];  
    console.log(array);  //  [99, 22, 45, 11, 36, 76, 56, 89]
    bubbleSort(array);   //  冒泡排序处理
    console.log(array)   //  [11, 22, 36, 45, 56, 76, 89, 99]

2.快速排序

快速排序是对冒泡排序的改进,第一轮排序时将数据分成两部分,一部分的数据比另外一部分的都小。然后递归调用,两边都实行快速排序。

 function quickSort(array) {
        //只有一个元素直接返回
        if (array.length <= 1) {
            return array;
        }
        //获取原始数组‘中间数’的索引
        var pivotIndex = Math.floor(array.length / 2);
        console.log('中间数索引是:' + pivotIndex);
        //获取原始数组的‘中间数'',并从原始数组中提取这个中间数
        //递归处理,从数组中剔除中间数
        var pivot = array.splice(pivotIndex, 1)[0];
        console.log('中间数是:' + pivot);
        // 保存左边半截数组
        var left = [];
        //保存右边半截数组
        var right = [];
        for (var i = 0; i < array.length; i++) {
            if (array[i] < pivot) { //如果当前元素在左半截
                left.push(array[i]); //将当前放入left
            } else {
                right.push(array[i]); //否则放入right
            }
            console.log(array);
        }
        console.log('左半截是:' + left);
        console.log('右半截是:' + right);
        //将抽离出来的中间数与左半截和有半截数进行连接
        return quickSort(left).concat([pivot], quickSort(right));
    }
    var array = [99, 22, 45, 11, 36, 76, 56, 89, 49];
    console.log('最原始数组:' + array);
    console.log(quickSort(array));

知识共享许可协议本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。作者:chaihongjun»