排序算法，简单排序、高级排序(实现)

1. 大O表示法2. 排序算法的总类3. 冒泡排序实现4. 选择排序实现5. 插入排序实现6. 希尔排序实现7. 快速排序实现

在计算机中，大O表示法的度量是粗略的，只保留最高项，比如：

n ^ 2 + 2n + 18 --> 大O表示法为 n ^ 2log(n) + n + 9 --> 大O表示法为 log(n)2n + 3n + 991–> 大O表示法为 n12 + 14 + 222 --> 大O表示法为 1

简单排序：

冒泡排序、选择排序、插入排序

高级排序：

希尔排序、快速排序

冒泡排序：比较次数O(n ^ 2) 交换次数O(n ^ 2)选择排序：比较次数O(n ^ 2)，交换次数O(n)插入排序：比较次数O(n ^ 2)，复制次数O(n ^ 2)[复制效率要比交换高]，并且相对于冒泡来说，插入的比较和复制都比冒泡快一倍，但是用大O表示法不能准确的表示，插入排序是简单排序中效率最高的归并排序计数排序基数排序堆排序桶排序希尔排序：时间复杂度为O(n * log(n))，一般情况下它比快速排序要慢，特殊情况下比快速快快速排序：时间复杂度为O(n * log(n))，在特殊的情况下快速排序可能会和冒泡的时间一样长，快速排序的效率一般情况下要大于其他的高级排序

冒泡排序的每一次遍历，把最大的放在了最后面，每循环一次(循环的次数是数组的长度 - 1，因为不用和自己比较)，下一次遍历数组，就会少遍历一位

let arr = [2, 9, 3, 5, 8, 4, 6, 1, 7]

// 冒泡排序的每一次遍历，把最大的放在了最后面
for (let i = 0; i < arr.length - 1; i++) {
  // 遍历数组
  for (let j = 1; j < arr.length - i; j++) {
    // 前面的数大于后面的数，就交换
    if (arr[j - 1] > arr[j]) {
      let temp = arr[j]
      arr[j] = arr[j - 1]
      arr[j - 1] = temp
    }
  }
}

console.log(arr);

选择排序选择最小的和第一位交换，第二位、第三位以此类推，也是每次循环一次，就少遍历一位

let arr = [2, 9, 3, 5, 8, 4, 6, 1, 7]

// 选择排序选择最小的和第一位交换，第二位、第三位以此类推
for (let i = 0; i < arr.length - 1; i++) {
  let index = i
  for (let j = i + 1; j < arr.length; j++) {
    if (arr[index] > arr[j]) {
      index = j
    }
  }
  // 小的放前面
  let temp = arr[i]
  arr[i] = arr[index]
  arr[index] = temp
}

console.log(arr);

插入排序的核心思想是局部有序保存当前值并向前找，大于它的依次向后复制，直到找到小于它的数据，在复制到小于它的数据的后一位

let arr = [2, 9, 3, 5, 8, 4, 6, 1, 7]

// 外层循环
for (let i = 1; i < arr.length; i++) {
  // 保存当前位的数据
  let temp = arr[i]
  let j = i
  // 当前位前面的数据大于它的话，进行复制操作
  while (arr[j - 1] > temp && j > 0) {
    arr[j] = arr[j - 1]
    j--
  }
  // 只要找到小于它的值，就复制到j当前的位置(因为j--)
  arr[j] = temp
}

console.log(arr);

希尔排序是对插入排序的优化(分层有序)[增量一般为数组长度的一半]比如数组的长度为100，那么就需要先分成两份1-51、2-52、3-53依次进行比较(这里的增量就为50)然后在分成四份1-26-51-76…进行比较(这里的增量就为25，每次除以2)依次二分，采用的是插入的原理，但是分层比较效率要比插入快很多，不需要一个数据跨很多其他的数据去交换位置，解决了插入排序的弊端

let arr = [2, 9, 3, 5, 8, 4, 6, 1, 7]

// 希尔排序是对插入排序的优化(分层有序)
// 比如数组的长度为100，那么就需要先分成两份0-50、1-51、2-52依次进行比较
// 然后在分成四份0-25-50-75..进行比较
// 依次二分，采用的是插入的原理，但是分层比较效率要比插入快很多
let gap = Math.floor(arr.length / 2)
while (gap >= 1) {
  for (let i = gap; i < arr.length; i++) {
    let temp = arr[i]
    let j = i
    // 按层进行复制操作
    // 在这层循环里面大多数只会操作一次
    while (arr[j - gap] > temp && j > gap - 1) {
      arr[j] = arr[j - gap]
      j -= gap
    }
    arr[j] = temp
  }
  // 分层依次查找
  gap = Math.floor(gap / 2)
}

console.log(arr);

快速排序的最重要的思想是分而治之在快速排序中有一个很重要的步骤就是选取枢纽，枢纽的左边要小于它右边要大于它，枢纽的位置确定好(这里的确定好是指，左右边分别符合小于它或大于它的条件)是不会变的(使用的递归)，然后再在左边和右边分别选择枢纽，依次类推枢纽的选择一般是一组数据中头、中、尾的中位数，例如8、12、3的中位数就是8，一般来说这种情况效率是最优的枢纽在选择头、中、尾，头要放在最前，尾要放在最后，枢纽和尾的前面一个元素交换位置，然后在查找

// 两数交换
function swap(before, after) {
  let temp = arr[before]
  arr[before] = arr[after]
  arr[after] = temp
}

// 寻找枢纽(头、尾、中间位的中位数)
function median(first, end) {
  // 中位数
  let center = Math.floor((first + end) / 2)
  if (arr[first] > arr[center]) {
    swap(first, center)
  }
  if (arr[center] > arr[end]) {
    swap(center, end)
  }
  if (arr[first] > arr[center]) {
    swap(first, center)
  }
  // 这个枢纽就是中位数，并且在数组的倒数第二的位置
  swap(center, end - 1)
  return arr[end - 1]
}

// 快速排序
function quickSort(arr) {
  quick(0, arr.length - 1)
}

// 快速排序递归函数
function quick(left, right) {
  // 结束条件
  if (left >= right) return
  // 获取枢纽
  let pivot = median(left, right)
  let i = left
  let j = right - 2
  while (true) {
    // 左边一直查找直到大于枢纽停止
    while (arr[i] < pivot) { i++ }
    // 右边一直查找直到小于枢纽停止
    while (arr[j] > pivot) { j-- }
    // 交换两个暂停元素的位置
    if (i < j) {
      swap(i, j)
      // 两值针走完后停止循环
    } else {
      break
    }
  }
  // 枢纽和左指针停止的位置交换，这样他的左边都小于它，右边都大于它(它指的枢纽)
  swap(i, right - 1)

  // 递归，分而治之
  quick(left, i - 1)
  quick(i + 1, right)
}

let arr = [2, 9, 3, 5, 8, 4, 6, 1, 7]

quickSort(arr)

console.log(arr);