排序

排序

程序中经典的问题，在此列举三个排序方式

冒泡排序

冒泡排序的逻辑是两两交换，最大的逐渐浮出到最右侧

function bubbleSorting(arr){
  if(!Array.isArray(arr)){
    return 'not array'
  }
  for(let i =0;i<arr.length-1;i++){
    let ranked = false
    for(let j = 1;j<i -1;j++){
      if(arr[j-1] > arr[j]){
        let storeNum = arr[j]
        arr[j] = arr[j-1]
        arr[j-1] = storeNum
        ranked = true
      }
    }
    // 如果本轮未发生交换，说明数组已有序，提前结束，可以作为优化手段
    if(ranked === false){
      break
    }
  }
}

选择排序

选择排序，选择出最大的数，一直放到最右侧

交换次数仅 O(n)，优于冒泡排序

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

选择排序优化

同时选出最大值和最小值，分别放在左侧和右侧

快速排序

二分法排序

基数排序