// 从当前元素起，向后依次比较每一对相邻元素，若逆序则交换
// 对所有元素均重复以上步骤，直至最后一个元素
function sort(arr) {
  var temp, l = arr.length - 1
  for (var i = 0; i < l; i++) {        // 外循环为排序趟数，len 个数进行 len - 1 趟
    for (var j = 0; j < l - i; j++) {  // 内循环为每趟比较的次数，第 i 趟比较 len - i 次
      if (arr[j] > arr[j + 1]) {       // 相邻元素比较，若逆序则交换（升序为左大于右，降序反之）
        temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
      }
    }
  }
  return arr
}

sort([2, 3, 5, 6, 4, 7, 8, 1, 9, 0])

function sort(arr) {
  var temp, flag                                // flag 为是否交换的标志
  for (var i = 0; i < arr.length - 1; i++) {
    flag = false                                // 每次遍历标志位都要先置为 false，才能判断后面的元素是否发生了交换
    for (var j = arr.length - 1; j > i; j--) {  // 选出该趟排序的最大值往后移动
      if (arr[j - 1] > arr[j]) {
        temp = arr[j - 1]
        arr[j - 1] = arr[j]
        arr[j] = temp
        flag = true                             // 只要有发生了交换，flag 就置为 true
      }
    }
    if (!flag) break                            // 判断标志位是否为 false，如果为 false，说明后面的元素已经有序，就直接 return
  }
  return arr
}

sort([2, 3, 5, 6, 4, 7, 8, 1, 9, 0])

function sort(arr) {
  var min, temp, l = arr.length
  for (var i = 0; i < l - 1; i++) {
    min = i
    for (var j = i + 1; j < l; j++) {
      if (arr[j] < arr[min]) {
        min = j
      }
    }
    if (min != i) {                   // 第 i 个数与最小的数 arr[i] 交换
      temp = arr[i]
      arr[i] = arr[min]
      arr[min] = temp
    }
  }
  return arr
}

sort([2, 3, 5, 6, 4, 7, 8, 1, 9, 0])

function sort(arr) {
  var temp
  for (var i = 1; i < arr.length; i++) {            
    for (var j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
      temp = arr[j]
      arr[j] = arr[j + 1]
      arr[j + 1] = temp
    }
  }
  return arr
}

sort([2, 3, 5, 6, 4, 7, 8, 1, 9, 0])

function sort(arr) {
  var temp, l = arr.length
  for (var gap = Math.floor(l / 2); gap > 0; gap = Math.floor(gap / 2)) {
    for (var i = gap; i < l; i++) {
      for (var j = i - gap; j >= 0 && arr [j] > arr[gap + j]; j -= gap) {
        temp = arr[j]
        arr[j] = arr[gap + j]
        arr[gap + j] = temp
      }
    }
  }
  return arr
}

sort([2, 3, 5, 6, 4, 7, 8, 1, 9, 0])

function mergeSort(arr) {
  console.log(arr)
  if (arr.length === 1) return arr
  var mid = Math.floor(arr.length / 2)
  var left = arr.slice(0, mid)
  var right = arr.slice(mid)
  // 合并左右两部分
  return merger(mergeSort(left), mergeSort(right))
}

// 实现归并，并将最后的结果存放进数组 c 当中
function merger(a, b) {
  var n = a && a.length
  var m = b && b.length
  var c = []
  var i = 0, j = 0

  while (i < n && j < m) {
    if (a[i] < b[j]) {
      c.push(a[i++])
    } else {
      c.push(b[j++])
    }
  }

  // 如果存放完毕以后还有剩余的元素，就追加进数组
  while (i < n) {
    c.push(a[i++])
  }

  while (j < m) {
    c.push(b[j++])
  }

  console.log('将数组 ', a, '和 ',b ,'合并为 ',c)
  return c
}

mergeSort([2, 3, 5, 6, 4, 7, 8, 1, 9, 0])

function sort(arr) {
  if (arr.length <= 1) return arr
  var pivot = arr[0]
  var left = []
  var right = []
  for (var i = 1; i < arr.length; i++) {
    if (arr[i] <= pivot) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  return sort(left).concat(pivot).concat(sort(right))
}

sort([2, 3, 5, 6, 4, 7, 8, 1, 9, 0])

function sort(arr, left, right) {
  if (left >= right) return arr                     // 退出递归的条件
  var temp, i = left, j = right, pivot = arr[left]
  while (i < j) {
    while (i < j && arr[j] >= pivot) {              // 从右边起，寻找比基数小的数
      j--
    }
    while (i < j && arr[i] <= pivot) {              // 从左边起，寻找比基数大的数
      i++
    }
    if (i < j) {                                    // 如果 i < j 就一直执行我们的查找过程
      temp = arr[i]
      arr[i] = arr[j]
      arr[j] = temp
    }
  }
  arr[left] = arr[i]                                // 此时 i >= j 了，说明我们的第一次的查找过程已经结束了，所以交换基准值
  arr[i] = pivot
  sort(arr, left, i - 1)                            // 对应处理基准值左侧的数据              
  sort(arr, i + 1, right)                           // 对应处理基准值右侧的数据
  return arr
}

var arr = [2, 3, 5, 6, 4, 7, 8, 1, 9, 0]
sort(arr, 0, arr.length - 1)

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

// 将 i 结点以下的堆整理为大顶堆
function heapAdjust(A, i, length) {
  // 当前父节点
  let temp = A[i]
  // j < length 的目的是对结点 i 以下的结点全部做顺序调整
  // 这里需要注意，因为 i 是双亲结点，所以对于二叉树来说， 2 * i 表示的是它的左孩子，2 * i + 1 表示的是右孩子
  // 2 * j 表示指向下一个双亲结点
  for (let j = 2 * i + 1; j < length; j = 2 * j + 1) {
    // 将 A[i] 取出，整个过程相当于找到 A[i] 应处于的位置
    // 也就是待调整的双亲
    temp = A[i]

    // 因为此时 j 是指向双亲的右孩子，所以如果右孩子大于左孩子的话
    // 小于 length 是确定 j + 1 不是最后一个结点
    // 简单来说就是，如果右孩子大于左孩子，j 就指向右孩子
    // 如果左孩子大于右孩子的话，j 还是它自己
    if (j + 1 < length && A[j] < A[j + 1]) {
      // 指向较大的元素，也就是找到两个孩子中较大的一个，再与父节点比较
      j++
    }
    if (temp < A[j]) {
      // 如果父节点小于子节点就执行交换，否则跳出
      swap(A, i, j)
      // 交换后，temp 的下标变为 j
      i = j
    } else {
      break
    }
  }
}

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

const arr = [2, 3, 5, 6, 4, 7, 8, 1, 9, 0]
heapSort(arr)
console.log(arr)

function sort(arr, maxValue) {
  var bucket = new Array(maxValue + 1), sortedIndex = 0
  for (var i = 0; i < arr.length; i++) {
    if (!bucket[arr[i]]) {
      bucket[arr[i]] = 0
    }
    bucket[arr[i]]++
  }
  for (var j = 0; j < maxValue + 1; j++) {
    while (bucket[j] > 0) {
      arr[sortedIndex++] = j
      bucket[j]--
    }
  }
  return arr
}

sort([2, 3, 5, 6, 4, 7, 8, 1, 9, 0], 9)

// 这里使用之前的插入排序
function insertSort(arr) {
  var temp
  for (var i = 1; i < arr.length; i++) {
    for (var j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
      temp = arr[j]
      arr[j] = arr[j + 1]
      arr[j + 1] = temp
    }
  }
  return arr
}

function bucketSort(arr, maxValue) {
  const DEFAULT_BUCKET_SIZE = 5                                           // 设置桶的默认数量
  const buckets = Array.from({ length: DEFAULT_BUCKET_SIZE }, () => [])   // 创建桶
  for (let i = 0; i < arr.length; i++) {                                  // 把元素放入对应桶子
    const idx = ~~(arr[i] / maxValue)                                     // 计算需要放入桶子序号（取整）
    buckets[idx].push(arr[i])
  }
  for (let i = 0; i < buckets.length; i++) {                              // 对每个桶子进行排序
    insertSort(buckets[i])                                                // 此处选取插入排序, 空间消耗少，元素少常数时间消耗短，也可以使用其他的方式
  }
  return [].concat(...buckets)                                            // 把每个桶子数据合并
}

const arr = [2, 3, 5, 6, 4, 7, 8, 1, 9, 0]
bucketSort(arr, 9)

const arr = [10, 200, 13, 12, 7, 88, 91, 24]

const buckets = Array.from({ length: 10 }, () => [])

// const arr = [10, 200, 13, 12, 7, 88, 91, 24]
[0, 0, 3, 2, 7, 8, 1, 4]

buckets = [[10, 200], [91], [12], [13], [24], [], [], [7], [88]]

arr = [10, 200, 91, 12, 13, 24, 7, 88]

// arr = [10, 200, 91, 12, 13, 24, 7, 88]，如果某个元素没有该位就默认为 0
[1, 0, 9, 1, 1, 2, 0, 8]

buckets = [[200, 7], [10, 12, 13], [24], [], [], [], [], [], [88], [91]]

arr = [200, 7, 10, 12, 13, 24, 88, 91]

// 按照百位进行排序
[2, 0, 0, 0, 0, 0, 0, 0, 0, 0]

// 取原数组的每个元素的百位
[[7, 10, 12, 13, 24, 88, 91], [], [200] ... ]

// 完成排序
[7, 10, 12, 13, 24, 88, 91, 200]

function radixSort(arr) {
  const max = Math.max(...arr)                          // 取最大值 最大值的位数就是要循环遍历的次数
  const buckets = Array.from({ length: 10 }, () => [])  // 定义一个桶
  let m = 1                                             // 定义当前要遍历的位数 个位 十位 百位
  while (m < max) {                                     // m < 最大值，下方 m 要 m *= 10 -> 每次遍历增加一位，保证遍历完所有可能的位数
    arr.forEach(number => {                             // 放入桶
      const digit = ~~((number % (m * 10)) / m)         // digit 表示某位数的值，也就是计算出某个数字的某位数的值
      buckets[digit].push(number)                       // 把该位数的值放到桶 buckets 中，通过索引确定顺序 类比计数排序
    })
    let ind = 0                                         // 从桶 buckets 中取值，完成此步后 就完成了一次位数排序
    buckets.forEach(bucket => {
      while (bucket.length > 0) {
        arr[ind++] = bucket.shift()                     // shift 从头部取值，保证按照队列先入先出
      }
    })
    m *= 10                                             // 每次最外层 while 循环后 m 要乘等 10，也就是要判断下一位 比如当前是个位 下次就要判断十位
  }
  return arr
}

radixSort([2, 3, 5, 6, 4, 7, 8, 1, 9, 0])