冒泡算法的三种JavaScript表示

冒泡排序 选择排序 快速排序

1 冒泡排序

代码

 let arr=[1,3,21,5,21,31,1,3,4,5,7];
            function mao(arr){
                for(let i=0;i<arr.length-1;i++){
                    for(let j=0;j<arr.length-1-i;j++){
                        if(arr[j]>arr[j+1]){
                            let temp=arr[i];
                            arr[j]=arr[j+1];
                            arr[j+1]=temp;
                        }
                    }
                }
                return arr;
            }
            console.log(mao(arr));// [1, 1, 1, 1, 1, 1, 3, 3, 4, 5, 7]

冒泡排序讲解

• 外层循环-1:外层循环是比较的轮数,最后一轮不需要进行,所以-1
• 内层循环-1-i:外层循环是选出的元素,-1是最后一个元素不需要比较,-i是已经比较过的不需要比较

2 选择排序

代码

function  select(arr){
                for(let i=0;i<arr.length-1;i++){
                    let max=i;//假设第一个最大
                    for(let j=i+1;j<arr.length-1;j++){
                        if(arr[max]>arr[j]){
                            max=j;
                        }
                    }
                    let temp=arr[max];
                    arr[max]=arr[i];
                    arr[i]=temp;
                }
                return arr;
            }
             console.log(select(arr));// [1, 1, 1, 1, 1, 1, 3, 3, 4, 5, 7]

选择排序讲解

• 外层循环控制比较轮数-1
• 原理:打擂台赛,(假设第一个最大,跟后面进行比较,若比当前值大就交换)
• 在内层循环外交换的原因是:减少交换次数,提交效率

3 快速排序

代码

function quick(arr){
                if(arr.length<=1){
                    return arr;
                }
                let middle=parseInt(arr.length/2);
                let value=arr.splice(middle,1);
                let right=[],left=[];
                for(let i=0;i<arr.length;i++){
                    if(arr[i]>value){
                        right.push(arr[i]);
                    }else {
                        left.push(arr[i]);
                    }
                }
                return quick(left).concat(value,quick(right));
            }
            console.log(quick(arr));// [1, 1, 1, 1, 1, 1, 3, 3, 4, 5, 7]

快速排序讲解

• 思想:递归 二分法
• 先判断数组长度,看是否进行
• 找出中间值,比中间值大的右边
• 递归此方法

拓展

  1 判断算法或者函数的效率
        console.time("A")
        console.log(quick(arr));
        console.timeEnd("A");
  2 time这个测试只能参考,跟内存或者其他因素有关
  3 上述算法效率相当