Javascript算法 — 数组排序

function sort1 (arr) {
  var len = arr.length
  for (var i = 0; i < arr.length; i++) {
    for (var j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j+1]) {
        var temp = arr[j+1]
        arr[j+1] = arr[j]
        arr[j] = temp
      }
    }
  }
  return arr
}
console.log(sort1([2,4,32,4,6,9,8])) // [2, 4, 4, 6, 8, 9, 32]

function sort2 (arr) {
  for (var i = 0; i < arr.length - 1; i++) {
    var minIndex = i
    for (var j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j
      }
    }
    if (minIndex !== i) {
      var temp = arr[i]
      arr[i] = arr[minIndex]
      arr[minIndex] = temp
    }
  }
  return arr
}
console.log(sort2([2,4,32,4,6,9,8])) // [2, 4, 4, 6, 8, 9, 32]

function sort3 (arr) {        
  if (arr.length <= 1) {            
    return arr
  } 
  var num = Math.floor(arr.length / 2)
  var centerVal = arr.splice(num, 1)
  var left = []  
  var right = []
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < centerVal[0]) {
      left.push(arr[i])
    }else{
      right.push(arr[i])
    }
  }
  return sort3(left).concat(centerVal, sort3(right)) 
}
console.log(sort3([2,4,32,4,6,9,8])) // [2, 4, 4, 6, 8, 9, 32]

function sort4 (arr) {
  for (var i = 1; i < arr.length; i++) {
    var preIndex = i - 1
    var current = arr[i]
    while (preIndex >= 0 && arr[preIndex] > current) {
      arr[preIndex + 1] = arr[preIndex]
      preIndex--
    }
    arr[preIndex + 1] = current
  }
  return arr
}
console.log(sort4([2,4,32,4,6,9,8])) // [2, 4, 4, 6, 8, 9, 32]

function sort5 (arr) {
  var gap = 1
  while (gap < arr.length / 5) {
    gap = gap * 5 + 1
  }
  for (; gap > 0; gap = Math.floor(gap / 5)) {
    for (var i = gap; i < arr.length; i++) {
      var temp = arr[i]
      for (var j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
        arr[j + gap] = arr[j]
      }
      arr[j + gap] = temp
    }
  }
  return arr
}
console.log(sort5([2,4,32,4,6,9,8])) // [2, 4, 4, 6, 8, 9, 32]

function sort6 (arr) {
  // 初始化大顶堆，从第一个非叶子结点开始
  for (let i = Math.floor(arr.length / 2 - 1); i >= 0; i--) {
    adjustHeap(arr, i, arr.length)
  }
  // 排序，每一次for循环找出一个当前最大值，数组长度减一
  for(let i = Math.floor(arr.length - 1); i > 0; i--) {
    // 根节点与最后一个节点交换
    swap(arr, 0, i)
    // 从根节点开始调整，并且最后一个结点已经为当前最大值，不需要再参与比较，所以第三个参数为 i，即比较到最后一个结点前一个即可
    adjustHeap(arr, 0, i)
  }
  return arr
}

// 交换两个节点
function swap(arr, i, j) {
  let temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

// 将 i 结点以下的堆整理为大顶堆，注意这一步实现的基础实际上是：
// 假设 结点 i 以下的子堆已经是一个大顶堆，adjustheap 函数实现的
// 功能是实际上是：找到 结点 i 在包括结点 i 的堆中的正确位置。后面
// 将写一个 for 循环，从第一个非叶子结点开始，对每一个非叶子结点
// 都执行 adjustheap 操作，所以就满足了结点 i 以下的子堆已经是一大
// 顶堆
function adjustHeap(arr, i, length) {
  // 当前父节点
  let temp = arr[i] 
  // j<length 的目的是对结点 i 以下的结点全部做顺序调整
  for(let j = 2 * i + 1; j < length; j = 2 * j + 1) {
    // 将 arr[i] 取出，整个过程相当于找到 arr[i] 应处于的位置
    temp = arr[i] 
    if(j+1 < length && arr[j] < arr[j+1]) {
      // 找到两个孩子中较大的一个，再与父节点比较
      j++
    }
    // 如果父节点小于子节点:交换；否则跳出
    if(temp < arr[j]) {
      swap(arr, i, j)
      // 交换后，temp 的下标变为 j
      i = j
    } else {
      break
    }
  }
}
console.log(sort6([2,4,32,4,6,9,8])) // [2, 4, 4, 6, 8, 9, 32]

function sort7 (arr) {
  return arr.sort((a, b) => a - b)
}
console.log(sort7([2,4,32,4,6,9,8])) // [2, 4, 4, 6, 8, 9, 32]