排序算法

1、冒泡排序 时间复杂度O(n*n)


从第一个元素开始,把当前元素和下一个索引元素进行比较。如果当前元素大,那么就交换位置,重复操作直到比较到最后一个元素,那么此时最后一个元素就是该数组中最大的数。下一轮重复以上操作,但是此时最后一个元素已经是最大数了,所以不需要再比较最后一个元素,只需要比较到 length - 1 的位置。


var arr = [1,4,2,6,8,5,1,3,4];
    var temp ;
    for (var i = 0; i < arr.length-1; i++){
      for (var j = 0; j < arr.length-i-1 ; j++){
        if (arr[j] > arr[j + 1]){                        
          temp = arr[j + 1];
          arr[j + 1] = arr[j]; 
          arr[j] = temp;
        }
      }
    }
    console.log(arr);


2、选择排序 时间复杂度O(n*n)


遍历数组,设置最小值的索引为 0,如果取出的值比当前最小值小,就替换最小值索引,遍历完成后,将第一个元素和最小值索引上的值交换。如上操作后,第一个元素就是数组中的最小值,下次遍历就可以从索引 1 开始重复上述操作。


var arr = [1,4,2,6,8,5,1,3,4];
  for(var i=0;i<arr.length-1;i++){
    for(var j=i+1;j<arr.length;j++){     
      if(arr[i]>arr[j]){                         
        var temp=arr[i]; 
        arr[i]=arr[j]; 
        arr[j]=temp; 
      } 
    } 
  } 
  console.log(arr);


 var arr=[1,4,2,6,8,5,1,3,4];
    var temp;
    for(var i=0;i<arr.length-1;i++){
      for(var j=arr.length-1;j>i;j--){
        if(arr[j]<arr[i]){
          temp=arr[i];
          arr[i]=arr[j];
          arr[j]=temp;
        }
     }
   }
   console.log(arr);



3、插入排序 时间复杂度O(n*n)


第一个元素默认是已排序元素,取出下一个元素和当前元素比较,如果当前元素大就交换位置。那么此时第一个元素就是当前的最小数,所以下次取出操作从第三个元素开始,向前对比,重复之前的操作。



function insertSort(arr){
   var temp=null;//定义一个临时变量保存要插入元素的值
   for(var i=1; i<arr.length; i++){//从索引位置1开始遍历数组
      if(arr[i]<arr[i-1]){//只有要插入的元素小于已排好序的最大元素的时候才需要进行下面的操作
          temp=arr[i];//把要插入的元素赋给一个临时变量
          var p=i-1;//已排好序的数组的最后一项索引为i-1
          while(temp<arr[p] && p>=0){//如果要插入的元素小于已排好序的元素并且没有到已排好数组的开始位置
              arr[p+1]=arr[p];//把大于要插入元素(temp)的已排好序元素位置往后挪一位
              p--;//从后往前便利已经排好序的元素 
          }
          arr[p+1]=temp;//把要插入的元素插入到已排好序的数组中,索引位置为p+1
      }        
   }
   return arr;//返回已排好序的数组
}


4、快速排序 时间复杂度 O(logN)


随机选取一个数组中的值作为基准值,从左至右取值与基准值对比大小。比基准值小的放数组左边,大的放右边,对比完成后将基准值和第一个比基准值大的值交换位置。然后将数组以基准值的位置分为两部分,继续递归以上操作。


function quickSort(arr){
  var len=arr.length;//获取arr的长度
  if(len<=1){//如果arr的长度小于等于1则直接返回arr
    return arr;
  }
  var pIndex=Math.floor(len/2);//获取基准点
  var pivot=arr.splice(pIndex,1);//用splice方法获取基准点pivot=[arr[pIndex]],此时的arr为去除第pIndex项之后的剩余项;
  var left=[];
  var right=[];
  for(var i=0; i<arr.length; i++){
    if(arr[i]<pivot[0]){//如果小于基准点就放到数组l中
      left.push(arr[i]);
    }else{//如果大于等于基准点就放到右边数组中
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat(pivot,quickSort(right));//递归不断重复整个过程
}


let quickSort = (arr) => {
            if(arr.length <= 1){
                return arr;
            }
            let sortIndex = Math.floor(arr.length/2),
                leftArr = [],
                rightArr = [],
                base = arr[sortIndex];
                arr.splice(sortIndex,1);
                //此处需要去除参照项,否则会出现Maximum call stack size exceeded 递归调用超出限制
                //简单写法 base = arr.splice(sortIndex,1)[0]
            for(let i = 0;i < arr.length;i++){
                if(arr[i] < base){
                    leftArr.push(arr[i])
                }else{
                    rightArr.push(arr[i])
                }
            }
             return quickSort(leftArr).concat(base,quickSort(rightArr))
        }
        
        let testArr = [2,31,1424,12,3445,1,2,3]
        let result = quickSort(testArr);


确认 取消