js手写系列-- 数组排序算法

冒泡排序

原理

var arr = [12, 13, 23, 14, 16, 11];
        // 第一轮
        // 12 13 => [12, 13, 23, 14, 16, 11]
        // 13 23 => [12, 13, 23, 14, 16, 11]
        // 23 14 => [12, 13, 14, 23, 16, 11]
        // 23 16 => [12, 13, 14, 16, 23, 11]
        // 23 11 => [12, 13, 14, 16, 11, 23]
        // 第二轮
        // 13 14 => [12, 13, 14, 16, 11, 23]
        // 14 16 => [12, 13, 14, 16, 11, 23]
        // 16 11 => [12, 13, 14, 11, 16, 23]
        // 16 23 => [12, 13, 14, 11, 16, 23]
        //第三轮
        // 14 11 => [12, 13, 11, 14, 16, 23]
        // 14 16 => [12, 13, 11, 14, 16, 23]
        // 16 23 => [12, 13, 11, 14, 16, 23]
        //第四轮
        // 14 16 => [12, 13, 11, 14, 16, 23]
        // 16 23 => [12, 13, 11, 14, 16, 23]
        //第五轮
        // 16 23 => [12, 13, 11, 14, 16, 23]

实现

/*
                bobble: 排序,升序
                @arr: [] 要排序的数组
                @return [] 排序后的数组
                */
        function bobble(arr) {
            //数组的长度为6,不用跟 自己比较,所以外层循环5遍,循环第一次,数组最后一位就是最大,依次累加
            for (var i = 0; i < arr.length - 1; i++) {
                // 不用跟自己比较,也不用跟已经排序后,放在数组尾的值比较
                for (var j = 0; j < arr.length - 1 - i; j++) {
                    if (arr[j] > arr[j + 1]) {
                        var nullArr;
                        nullArr = arr[j]
                        arr[j] = arr[j + 1]
                        arr[j + 1] = nullArr
                    }
                }
            }
            return arr
        }
        console.log(bobble(arr));

快速排序

原理

js手写系列-- 数组排序算法

实现

/*
                // quick(): 快速排序
                // @param
                // arr:[] 要排序的数组
                // @return 
                //arr:[] 排序后的数组,升序
                */
        function quick(arr) {
            if (arr.length <= 1) {
                return arr;
            }
            var rightArr = []
            var leftArr = []
            var centerIndex = Math.floor((arr.length) / 2)
            var centerValue = arr.splice(centerIndex, 1)[0]

            for (var i = 0; i < arr.length; i++) {
                if (arr[i] < centerValue) {
                    leftArr.push(arr[i])
                } else {
                    rightArr.push(arr[i])
                }
            }
            var result = quick(leftArr).concat(centerValue).concat(quick(rightArr))
            return result;
        }
        console.log(quick(arr));

插入排序

原理

js手写系列-- 数组排序算法

实现

var ary = [12, 15, 14, 13, 16, 11]

        function insert(ary) {
            var handAry = [];
            handAry.push(ary[0])
            for (var i = 1; i < ary.length; i++) {
                var item = ary[i];
                for (var j = handAry.length - 1; j >= 0; j--) {
                    if (item > handAry[j]) {
                        handAry.splice(j + 1, 0, item);
                        break;
                    }
                    if (j === 0) {
                        handAry.unshift(item)
                    }
                }
            }
            return handAry;
        }
        console.log(insert(ary));

相关推荐