冒泡排序&直接插入排序&快速排序

一、冒泡排序

  0       1      2      3      4      5  

假设有一个6个数的数组，0,1,2,3,4,5是索引，冒泡排序就是相邻两个对比，比如5和4比，如果满足条件就互换位置，然后4和3比，3和2比，2和1比，1和0比。第一趟循环下来，把最大或最小的数放到0，第二趟循环，把0-4中最大或最小的数放到1。。。

冒泡排序有两层循环，外层循环控制需要几趟循环，1趟循环可以将最大或最小的数放到0的位置，第2次循环可以将次最大或次最小的数放到1的位置，以此类推，需要length-1趟循环。所以外层为for(var i=1;i<length;i++)

再看里层循环，对比时会用到a[j]和a[j-1]对比，那么第一趟循环中，j-1最小的位置为0（i=1）；第二趟循环中j-1最小的位置为1(i=2);所以在第i趟循环中，j-1的位置为i-1;那么j的位置为i;因此里层循环为for(var j=length-1;j>=i;j--)

所以冒泡排序法为

function Bubble(arr){
    var flag=true;
    var len=arr.length;
    for(var i=1;i<len&&flag;i++){
        flag=false;  // 初始化flag为false，如果有交换位置就将它置换为true，否则终止循环，因为已经有序了
        for(var j=len-1;j>=i;j--){
            if(arr[j]<arr[j-1]){
                // 交换位置
                flag=true;
            }
        }
    }
    return arr;
}

 时间复杂度O(n²)，冒泡排序是稳定的排序算法。

二、选择排序

选择排序就是每一次选出数组中最小或者最大的数字的下标，然后和第一个数组元素交换，然后选出次大或次小的数字下标，和第二个数组元素交换。

function selectSort(arr){
    var len=arr.length;
    for(var i=1;i<len;i++){
        min=i-1;
        for(var j=i;j<len;j++){
           if(arr[min]>arr[j]){
               min=j;
           }
        }
        if(min!=i-1){
            var temp=arr[min];
             arr[min]=arr[i-1];
             arr[i-1]=temp;
        }
    }
    return arr;
}

时间复杂度为O(n²), 但是性能上优于冒泡排序。是不稳定的排序算法。

三、直接插入排序

  0       1      2      3      4      5  

假设有一个6个数的数组，0,1,2,3,4,5是索引

假设0 1都是排序好的数，那么现在要把2插入到0 和1 中，按升序排列，2先和1比，如果2比1大那么2保持位置不变，不再继续比较。如果2比1小，那么2和1位置互换，然后2再和0比

同样的两层循环，第一层循环，先是插入1，然后插入2，然后是插入3.。。。最后插入5，因此需要length-1次插入，外层循环就为for(var i=1;i<arr.length;i++)

第二层循环是用要插入的数假设是i，和0到i-1比较，因此for(var j=i-1;j>=0;j--)

for(var i=1;i<arr.length;i++){
　　var temp=arr[i];  //temp保存要插入的数
   var position=i;
　　for(var j=i-1;j>=0;j--){
　　　　if(temp<arr[j]){// 如果要插入的数比它之前的数小，那么互换位置
　　　　　　arr[j+1]=arr[j];
　　　　　　position--;
　　　　}else{
　　　　　　break; //如果要插入的数比它前一个数大，那么跳出里层循环。因为前面的数都是升序排列的，如果比相邻的前一个数大，那么也肯定大于之前的其他数
　　　　}
　　}

}

四、快速排序

快速排序主要分三步

　　（1）在数据集之中，选择一个元素作为"基准"（pivot）。

　　（2）所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。

　　（3）对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

function quickSort(arr){
　if(arr.length<=1)return arr;
  var midIdx=Math.floor(arr.length/2);
  var mid=arr.splice(midIdx,1)[0];
  var left=[];
  var right=[];
  for(var i=0;i<arr.length;i++){
      if(arr[i]<mid){
          left.push(arr[i]);  
        }else{
          right.push(arr[i]);
        }      
    }
  return quickSort(left).concat(mid,quickSort(right));        
}