js 排序

冒泡排序

原理：数组中的数据前后两两进行对比，如果后面一个数据小于前面一个则进行交换。

/**
 * 冒泡排序
 * @param {array} arr 
 */
function bubbleSort ( arr = [] ) {
  const length = arr.length
  for ( let i = 0; i < length; i++ ) {
    for ( let j = 0; j < length - i; j++ ) {
      if ( arr[ j ] > arr[ j + 1 ] ) {
        [ arr[ j ], arr[ j + 1 ] ] = [ arr[ j + 1 ], arr[ j ] ]
      }
    }
  }
}

推荐视频：JS冒泡排序

选择排序

原理：将未排序的数据的第一个数据作为对比基准，在除了已排序和基准数据以外的数据里找到最小的数据，将该数据和基准数据进行交换。

/**
 * 选择排序
 * @param {array} arr 
 */
function choseSort ( arr = [] ) {
  const length = arr.length
  for ( let i = 0; i < length; i++ ) {
    let minIndex = i // 假设当前元素为最小值
    for ( j = i + 1; j < length; j++ ) {
      if ( arr[ j ] < arr[ minIndex ] ) {
        minIndex = j
      }
    }
    [ arr[ i ], arr[ minIndex ] ] = [ arr[ minIndex ], arr[ i ] ]
  }
}

 推荐视频：小伙教你，5分钟学会 JS中的选择排序

快速排序

原理：取数组的中间值为基准数据，把数组中剩余的小于基准数据的数据放在基准数据的左边的新数组中，大于的放在右边的新数组中，再分别将这两个新数组按照原数组取中间值，划分左右新数组的方法进行递归，最后即可得到排序好的数组。

/**
 * 快速排序
 * @param {array} arr 
 * @returns {array} newArray
 */
function quickFun ( arr ) {
  if ( arr.length <= 1 ) return arr
  let middleIndex = Math.floor( arr.length / 2 ) //获取基准数据的下标
  let middleItem = arr.splice( middleIndex, 1 )[ 0 ] //截取基准数据
  let leftArr = []
  let rightArr = []
  for ( let i = 0; i < arr.length; i++ ) {
    if ( arr[ i ] > middleItem ) {
      rightArr.push( arr[ i ] )
    } else {
      leftArr.push( arr[ i ] )
    }
  }
  //将左边数组，基准数据和右边数组进行拼接成一个完整的数组
  return quickFun( leftArr ).concat( middleItem, quickFun( rightArr ) )
}

插入排序

原理：以数组的第一个数据为基准，想象成一个只有一个数据的数组，将剩下的数据依次插入基准数据所在的数组中合适的位置。

/**
 * 插入排序
 * @param {array} arr 
 */
function pickFun ( arr ) {
  let preIndex = 0 // 进行大小对比的基准数据的下标
  let current = 0 // 进行大小对比的当前选中的剩余数量值
  for ( let g = 1; g < arr.length; g++ ) {
    preIndex = g - 1 // 进行基准数据赋值
    current = arr[ g ] // 获取当前进行对比的剩余数量值
    while ( preIndex >= 0 && arr[ preIndex ] > current ) {
      arr[ preIndex + 1 ] = arr[ preIndex ]
      preIndex--
    }
    arr[ preIndex + 1 ] = current
  }
  return arr
}

推荐视频：插入排序

希尔排序

原理：基于插入排序进行的优化，先将整个数组按照数组长度的一半进行分组使用插入排序，完成后，再将整个数组按照数组长度的1/4进行分组使用插入排序，重复以上步骤，直到分组长度为1为止。

/**
 * 希尔排序
 * @param {array} arr 
 * @returns {array} newArr
 */
function hillFun ( arr ) {
  //第一层循环，确定间隔数
  // 这里的 gap 相当于插入排序中的 1 ，所以在第二层循环中 preIndex = i-gap; 相当于插入排序中的 preIndex = g - 1;
  for ( let gap = parseInt( arr.length / 2 ); gap > 0; gap = parseInt( gap / 2 ) ) {
    //第二层循环，使用插入排序
    for ( let i = gap; i < arr.length; i++ ) {
      let preIndex = i - gap
      let current = arr[ i ]
      while ( preIndex >= 0 && current < arr[ preIndex ] ) {
        arr[ preIndex + gap ] = arr[ preIndex ]
        preIndex -= gap
      }
      arr[ preIndex + gap ] = current
    }
  }
  return arr
}

推荐视频：[算法]六分钟彻底弄懂希尔排序，简单易懂

参考js数组排序的六种方法