排序算法

2021-10-27

几种算法的可视化网址

冒泡排序

 var arr = [12, 9, 5, 20, 1, 0, -9, 5]
 var len = arr.length
 //1. 冒泡排序
 //外层for循环控制比较的轮数   内层for循环两两比较 交换位置
 for(var i = 0; i < len; i++) {
     for(var j = 0; j < len - i -1; j++) {
         if(arr[j] > arr[j+1]) {
             [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
         }
     }
 }
console.log(arr)  // [-9, 0, 1, 5, 5, 9, 12, 20]

选择排序

var arr = [12, 9, 5, 20, 1, 0, -9, 5]
var len = arr.length
var minIndex
// 2. 选择排序  外层for循环记录用了每一次交换最新元素  内层for循环用了找到最小元素
for (var i = 0; i < len; i++) {
    //初始化minindex为第一个
    minIndex = i
    // 遍历循环比较 有没有比这个更小的 如果有 把修改minindex的值
    for (var j = i + 1; j < len; j++) {
        if (arr[minIndex] > arr[j]) {
            minIndex = j
        }
    }
    // 交换本轮选出的最小元素到前面
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
}

插入排序

for(var i = 1; i < len; i++) {
    var j = i
    var current = arr[i]
    while(j > 0 && current < arr[j-1]) {
        arr[j] = arr[j-1]
        j--
    }
    arr[j] = current
}

归并排序(归并排序递归把数组一半一半的分，最终分成一个元素成为一个数组然后合并排序最终返回arr)

//分离
function fen(arr) {
    const len = arr.length
    if(len <= 1) {
        return arr
    }
    let mid = Math.floor(len/2)
    let leftarr = fen(arr.slice(0,mid))
    let rightarr = fen(arr.slice(mid,len))
    arr = mergearr(leftarr, rightarr)
    console.log(arr);
    return arr
}
//合并
function mergearr(arr1, arr2) {
    const res = [...arr1,...arr2]
    const _res = res.sort((a, b) => a - b)
    return _res
}
fen(arr)

快速排序()

// 快速排序入口
function quickSort(arr, left = 0, right = arr.length - 1) {
  // 定义递归边界，若数组只有一个元素，则没有排序必要
  if(arr.length > 1) {
      // lineIndex表示下一次划分左右子数组的索引位
      const lineIndex = partition(arr, left, right)
      // 如果左边子数组的长度不小于1，则递归快排这个子数组
      if(left < lineIndex-1) {
        // 左子数组以 lineIndex-1 为右边界
        quickSort(arr, left, lineIndex-1)
      }
      // 如果右边子数组的长度不小于1，则递归快排这个子数组
      if(lineIndex<right) {
        // 右子数组以 lineIndex 为左边界
        quickSort(arr, lineIndex, right)
      }
  }
  return arr
}
// 以基准值为轴心，划分左右子数组的过程
function partition(arr, left, right) {
  // 基准值默认取中间位置的元素
  let pivotValue = arr[Math.floor(left + (right-left)/2)]
  // 初始化左右指针
  let i = left
  let j = right
  // 当左右指针不越界时，循环执行以下逻辑
  while(i<=j) {
      // 左指针所指元素若小于基准值，则右移左指针
      while(arr[i] < pivotValue) {
          i++
      }
      // 右指针所指元素大于基准值，则左移右指针
      while(arr[j] > pivotValue) {
          j--
      }

      // 若i<=j，则意味着基准值左边存在较大元素或右边存在较小元素，交换两个元素确保左右两侧有序
      if(i<=j) {
          swap(arr, i, j)
          i++
          j--
      }

  }
  // 返回左指针索引作为下一次划分左右子数组的依据
  return i
}

function swap(arr, i, j) {
  [arr[i], arr[j]] = [arr[j], arr[i]]
}

学习地址1

学习地址2