排序算法

// 排序算法 [9,2,4,5,3,1]
// 冒泡排序： 第一层for循环：比较轮数 = length - 1，第二层for循环比较次数减少是因为不需要和已经确定排序的数进行比较，相邻比较，把最大的往后冒
/* 
每一轮经过相邻两两比较之后都会确定一个较大的数字放到数组后面的位置
第一轮：[........9]  不需要比较 自己                需要比较 5次
第二轮：[.......5,9] 不需要比较 自己 + 9            需要比较 4次
第三轮：[......4,5,9]不需要比较 自己 + 5 + 9        需要比较 3次
第四轮：[..3,4,5,9]  不需要比较 自己 + 4 + 5 + 9    需要比较 2次
第五轮：[1,2,3,4,5,9] 比较剩余的最后两个数，只需要比较 需要比较 1次
算法复杂度最坏情况 5 + 4 + 3 +2 + 1 = (n-1)+(n-2)+(n-3)+(n-4)+(n-5) = n*(n-1)/2 = O(n^2)
*/
let arr = [9,2,4,5,3,1,3,-1,0]
function bubbbleSort(arr) {
  let n = arr.length - 1
  // 0,1,2,3,4 五轮
  for (let i = 0; i < n; i++) {
    // 每一轮不需要比较自己和比较过确定数量的累计
    for(let j = 0; j < arr.length-1-i; j++) {
      if(arr[j] > arr[j+1]){
        [arr[j],arr[j+1]] = [arr[j+1],arr[j]]
      }
    }
  } 
  return arr
}
// console.log(bubbbleSort(arr))
// 选择排序： [9,2,4,5,3,1],第一层for循环确定比较轮数，第二层j 从i+1开始，是因为每次都把最小的放在最前i的位置
/* 
每一轮 筛选记录最小值的下标，将和每一轮的轮数交换位置
第一轮 假设arr[0] = 9 是最小值，依次和2、4、5、3、1比较。每次比较都令arr[0]是最小值，需要比较 5次（不和自己比较）
第二轮 假设arr[1] = 2 是最小值，依次和9、4、5、3 比较，每次比较都令arr[1]是最小值，需要比较 4次（不和自己 + 9比较）
...
第五轮 剩余两个数 只需要比较 1次
算法复杂度最坏情况 5 + 4 + 3 +2 + 1 = (n-1)+(n-2)+(n-3)+(n-4)+(n-5) = n*(n-1)/2 = O(n^2)
*/
function selectionSort(arr) {
  for(let i = 0; i < arr.length-1; i++){
    // j = i +1 表示每一轮不需要自己和比较过确定数量的累计
    for(let j = i +1; j < arr.length; j++){
      if(arr[j] < arr[i]) {
        [arr[i],arr[j]] = [arr[j],arr[i]]
      }
    }
  }
  return arr
}
// console.log(selectionSort(arr))
// 插入排序：把当前的数插入到之前经过交换已排好序的数组中
// function insertSort(arr) {
//   let a = []
//   a[0] = arr[0];
//   for (let  i = 1;  i < arr.length;  i++) {
//     for(let j = a.length - 1; j >= 0; j--){
//       if(arr[i] >= a[j]) {
//         a.splice(j+1,0,arr[i])
//         break
//       }
//       if(j === 0){
//         a.unshift(arr[i])
//       }
//     }
//   }
//   return a
// }
// 插入排序优化
function insertSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    // 取出待插入的元素
    let insertValue = arr[i];
    let j = i - 1;
    for (; (j >= 0) && (insertValue < arr[j]); j--) {
      arr[j + 1] = arr[j];
    }
    arr[j + 1] = insertValue;
  }
  return arr
}

// console.log(insertSort(arr))

// 希尔排序 建立在插入排序上，因为前面三个排序性能最好的是插入排序，进行分组的插入排序 nlogn
function shellSort(arr) {
  for(let gap = Math.floor(arr.length / 2); gap > 0; gap = Math.floor(gap / 2)){
    //将数组按照一定间隔分组，将分组好的数组分别进行插入排序，直到间隔为1，进行最后一次插入排序
    for(let i = 0; i < arr.length - gap; i++){
      let insertValue = arr[i+gap]
      let j = i
      for(;j >= 0 && arr[j] > insertValue;j = j - gap){
        arr[j + gap] = arr[j]
      }
      arr[j + gap] = insertValue
    }
  }
  return arr
}
 console.log(shellSort(arr))
// 归并排序 递归+合并 把数组分成左右两部分，对左边进行递归排序，对右边进行递归排序，在合并左右排序
function mergeSort(arr) {
if(arr.length === 1) return arr
  let a = []
  let n = Math.floor(arr.length / 2)
  let left = arr.slice(0,n)
  let right = arr.slice(n)
  let kl = mergeSort(left)
  let kr =  mergeSort(right)
  let il = 0;
  let ir = 0
  while (il < kl.length && ir < kr.length) {
    if(kl[il] < kr[ir]){
      a.push(kl[il])
      il++
    }else{
      a.push(kr[ir])
      ir++
    }
  }
  if(il < kl.length){
    let b = kl.slice(il)
    a = a.concat(b)
  }
  if(ir < kr.length){
    let c = kr.slice(ir)
    a = a.concat(c)
  }
  return a
}

console.log(mergeSort(arr))

// 快速排序 找到一个基准点，保证比基准点大的都在基准点右边，比基准点小的都在基准点的左边，最后形成【左，基准点，右】依次递归
function quickSort(arr) {
  if(arr.length <= 1) return arr
  let n = Math.floor(arr.length / 2)
  let pivot = arr.splice(n,1)[0]
  const left = []
  const right = []
  arr.map(item=>{
    if(item < pivot){
      left.push(item)
    }else{
      right.push(item)
    }
  })
 
  return quickSort(left).concat(pivot,quickSort(right))
}
console.log(quickSort(arr))

希尔排序for循环i < arr.lenght - gap过程

image.png