使用JavaScript实现几种常用的排序算法

冒泡排序

function BubbleSort(arr){
    if(arr.length<=1){return arr};

    for(let i =0;i<arr.length;i++){
        for(j=i+1;j<arr.length;j++){
            if(arr[i]>arr[j]){
                [arr[i],arr[j]] = [arr[j],arr[i]];
            }
        }
    }

    return arr;
}

快速排序

function quickSort(arr){
  //如果数组<=1,则直接返回
  if(arr.length<=1){return arr;}

  //找基准，并把基准从原数组删除
  let pivotIndex=Math.floor(arr.length/2);
  let pivot=arr.splice(pivotIndex,1)[0];
  
  //定义左右数组
  let left=[];
  let right=[];

  //比基准小的放在left，比基准大的放在right
  for(let i=0;i<arr.length;i++){
      if(arr[i]<=pivot){
          left.push(arr[i]);
      }
      else{
          right.push(arr[i]);
      }
  }
  //递归
  //return quickSort(left).concat([pivot],quickSort(right));
  return [...quickSort(left),pivot,...quickSort(right)];
}

归并排序

function merge(left,right){
    //"治"阶段，合并数组
    let result = [];
    while(left.length>=1&&right.length>=1){
        if(left[0]<right[0]){
            result.push(left.shift());
        }else{
            result.push(right.shift());
        }
    }
    //将左右数组剩下的也合并
    return result.concat(left).concat(right);
}
function mergeSort(arr){
    //"分"阶段，分离数组
    //递归出口，数组长度为1时，就到了“分”阶段的最底层
    if(arr.length ==1){
        return arr;
    }
    //找出基准点
    let pivot = Math.floor(arr.length/2);
    //分出左右数组(右数组包括基准点)
    let left = arr.slice(0,pivot);
    let right = arr.slice(pivot);
    return merge((mergeSort(left)),mergeSort(right));
}

插入排序

function insertionSort(iArr) {
    var oArr = [iArr[0]];
    var n = iArr.length;
    // 从左边开始，每次拿一个与已排列好的数组进行比较
    for (var i = 1; i < n; i++) {
        for (var j = 0; j < i; j++) {
            if (iArr[i] <= oArr[j]) {
            // 若介于小于该元素，则插入其前方
            oArr.splice(j, 0, iArr[i]);
            break;
            } else if (j === i - 1) {
                // 若比最后一个还大，则排在最右侧
                oArr.push(iArr[i]);
                }
        }
    }
    return oArr;
}

选择排序

function selectSort(arr){
    var len= arr.length,
        minIndex,nu;
    for(var i = 0; i < len-1; i++){
        minIndex = i;//记录每次循环的第一个数为该次循环的最小值索引
        for(var j = i+1; j < len; j++){
            if(arr[j]<arr[minIndex]){
                minIndex = j;//找到每次循环到的最小值，
            }
        }
        nu = arr[i];
        arr[i] = arr[minIndex];//将找到的最小值放在每次循环的最开始的地方；
        arr[minIndex] = nu;

    }
    return arr;
}

希尔排序

function shellSort(arr) {
    for(let gap = Math.floor(arr.length/2); gap > 0; gap = Math.floor(gap/2)) {
      // 内层循环与插入排序的写法基本一致，只是每次移动的步长变为 gap
      for(let i = gap; i < arr.length; i++) {
        let j = i;
        let temp = arr[j];
        for(; j> 0; j -= gap) {
          if(temp >= arr[j-gap]) {
            break;
          }
          arr[j] = arr[j-gap];
        }
        arr[j] = temp;
      }
    }
    return arr;
}