js-排序的那些事儿

可以看大佬的文章：十大经典算法排序总结对比

也有可操作的演示：演示动画

下面是常用的五个排序以及个人比较喜欢的代码逻辑写法：

1.插入排序：从左到右开始，往左边比较，直到符合【两者之间】条件，则插入，重复操作

function insertSort(arr){
  let temp;
  for(let i=1;i < arr.length;i++){
    temp = arr[i];
    for(let j=i;j >= 0;j--){
      if(arr[j-1] > temp){
        arr[j] = arr[j-1];
      }else{
        arr[j] = temp;
        break;
      }
    }
  }
  return arr
}

2.选择排序：从左到右开始，从右边中选择一个最小的，放在左边，重复操作

function selectSort(arr){
  let tempMin,tempMinIndex;
  for(let i=0; i < arr.length;i++){
    tempMin = arr[i];
    tempMinIndex = i;
    for(let j=i;j < arr.length;j++){
      if(arr[j] < tempMin){
        tempMin = arr[j];
        tempMinIndex = j;
      }
    }
    arr[tempMinIndex] = arr[i];
    arr[i] = tempMin;
  }
  return arr;
}

3.归并排序：将数组一直等分至两个元素一组，然比较后合并，递归

function mergeSort(arr){
  function subMerge(left,right){
    let temp = [];
    while(left.length && right.length){
      if(left[0] < right[0]){
        temp.push(left.shift())
      }else{
        temp.push(right.shift())
      }
    }
    return temp.concat(left,right)
  }
  
  function mergeArr(arr){
    if(arr.length < 2){
      return arr
    }
    let tempIndex = Math.floor(arr.length/2);
    let left = arr.slice(0,tempIndex),right = arr.slice(tempIndex);
    return subMerge(mergeArr(left),mergeArr(right));
  }
  return mergeArr(arr);
}

4.快速排序：取一个基准（一般取中间的），然后比较大小，分三个数组，然后合并，重复操作

function quickSort(arr){
  if(arr.length <= 1){
    return arr;
  }
  let left = [],middle = [],right = [];
  let temp = arr[Math.floor(arr.length/2)];
  for(let item of arr){
    if(item > temp){
      right.push(item)
    }else if(item < temp){
      left.push(item)
    }else{
      middle.push(item)
    }
  }
  return [].concat(quickSort(left),middle,quickSort(right))
}

5.冒泡排序：比相邻，若通过比较则交换，重复操作

function bubbleSort(arr){
  for(let i=arr.length-1;i > 0;i--){
    for(let j=0; j < i;i++){
      if(arr[j] > arr[j + 1]){
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr
}

然后复杂度，偷个图

image.png