4.js三种数组排序方法

快速排序

• 在数组中间找到一个数，作为基准，然后用剩下的数，和基准点进行比较，比它小的放到左边数组，比它大的放到右边数组；
• 左边和右边数组再按照上述思想进行比较，一直到左右两边数组都只剩下一项为止；最后将比完后的数组和基准点拼接在一起

var arr=[18,62,7,9,94,5,4,54,23];
console.log(arr);
function quickSort(ary){
    if(ary.length<=1){      //如果数组只有一项，就不再进行比较，直接返回
        return ary;
    }

    var ind=Math.floor(ary.length/2); //取数组中间的某项当作基准点  9/2=4.5
    var midNum=ary.splice(ind,1)[0]; //把基准点从数组中删除，并得到它;原数组已经改变了
    var left=[];
    var right=[];

    for(var i=0;i<ary.length;i++){
        var cur=ary[i];
        if(cur<midNum){
            left.push(cur);   //比基准点小的放左边数组
        } else{
            right.push(cur);  //比基准点大的放右边数组
        }
    }
    //left和right也需要以上比较操作，直到左边和右边都排好序，在进行最后的拼接
    return quickSort(left).concat([midNum],quickSort(right));
}
console.log(quickSort(arr));

插入排序

• 插入排序，左手先有一张牌，然后右手再去依次抓牌，
• 当新抓到的一张牌，比开始左手边的牌要小的话，继续和前边牌进行比较
• 一直遇到比它小的牌时，就把这张牌放到这张牌的后面
• 如果新抓的这张牌，左手边都比较完，发现没有遇到比他小的牌，直接将这张牌放到左手边最开头

var arr=[11,5,6,3,7,10,17,4,2,15];
function insertSort(ary){
var left=ary.splice(0,1);  //获取元素组的第一项，且是一个数组
 for(var i=0;i<ary.length;i++){
    var cur=ary[i];
    for(var j=left.length-1;j>=0;){
        if(cur<left[j]){   //当前抓的牌比左手边的牌要小的时候
            j--;           //继续和左手边的牌进行比较
            if(j===-1){       //如果左手边所有的牌都比它大，那么就放在最左边
                left.unshift(cur);
            }
        } else{   //如果当前的牌比左手边的某张牌大的时候，就将这张牌放在左手中比较的这张牌后
            left.splice(j+1,0,cur);
            break;
        }
    }
 }
    return left;
}
console.log(insertSort(arr));

冒泡排序

• 当前项与后一项进行比较，如果当前项大于后一项，则交换位置；
• 比较轮数为arr.length-1;
• 第n轮比较的次数：arr.length-n;

var arr=[11,1,12,34,6,5];
var temp;
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]){     //交换数据
      temp=arr[j];
      arr[j]=arr[j+1];
      arr[j+1]=temp;
    }
  }
}
temp=null;
console.log(arr);   Array [ 1, 5, 6, 11, 12, 34 ]