排序算法

对于前端，常用的是五中排序算法冒泡排序 选择排序 插入排序 归并排序 快速排序。其中归并排序和快速排序可以用到工作中，其他三个排序算法由于时间复杂度较高，一般只出现在面试中，不建议用在工作中。

冒泡排序

冒泡排序的时间复杂度O(n^2)

思路：比较所有相邻元素，如果第一个比第二个大，则交换它们。一轮下来，可以保证数组最后一个数字最大。执行n-1轮，就可以完成排序

function bubbleSort (arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - 1- i; j++) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
      }
    }
  }
  return arr
}

选择排序

选择排序的时间复杂度O(n^2)

思路：找到数组中最小值，并把他放到第一位。除去第一个剩下的数组，找到它最小值，放入地二位。以此类推，执行n-1轮。

function selectionSort (arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = i
    for (let j = i; j < arr.length; j++) {
      if (arr[minIndex] > arr[j]) {
        minIndex = j
      }
    }
    if (minIndex !== i) {
      const temp = arr[i]
      arr[i] = arr[minIndex]
      arr[minIndex] = temp
    }
  }
}

插入排序

插入排序的时间复杂度O(n^2)

思路：从第二个数往前比，比它大往后排。以此类推，到最后一个数。

function insertSort (arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    const temp = arr[i + 1]
    for (let j = 0; j < i + 1; j++) {
      if (arr[i - j] < 0) {
        break
      }
      if (arr[i + 1 - j] < arr[i - j]) {
        arr[i + 1 - j] = arr[i - j]
        arr[i - j] = temp
      } else {
        continue
      }
    }
  }
}

归并排序

归并排序的时间复杂度是O(N*logN)。其中，分的时间复杂度是O(logN)；合时间复杂度是O(N)

思路：先拆分，在排序。把一个大问题拆分成多个小问题；先把数组分成一个一个单独数，然后把两个数合并成有序数组，再对有序数组进行合并，直到把所有有序子数组合并成一个数组。

function mergeSort(arr) {
  if (arr.length === 1) {
    return arr
  }
  const mid = Math.floor(arr.length/2)
  const left = arr.slice(0, mid)
  const right = arr.slice(mid)
  return mergeArr(mergeSort(left), mergeSort(right))
}

function mergeArr(arr1, arr2) {
  let res = []
  while (arr1.length || arr2.length) {
    if (arr1.length && arr2.length) {
      res.push(arr1[0] > arr2[0] ? arr2.shift() : arr1.shift())
    } else if (arr1.length) {
      res.push(arr1.shift())
    } else if (arr2.length) {
      res.push(arr2.shift())
    }
  }
  return res
}

快速排序

快速排序的时间复杂度是O(N*logN)。其中，递归的时间复杂度是O(logN)；分区时间复杂度是O(N)

思路：从数组任意选择一个数字作为基准，所有比基准小数字放到基准前面，比基准大的放到基准后面。然后递归对基准前后数组进行相同操作。直到基准前后数组长度都是1，那么排序完成。

function quickSort (arr) {
  if (arr.length < 2) {
    return arr
  }
  let first = arr[0]
  let left = []
  let right = []
  for (let index = 1; index < arr.length; index++) {
    const element = arr[index];
    if (element < first) {
      left.push(element)
    } else {
      right.push(element)
    }
  }
  return [...quickSort(left), first, ...quickSort(right)]
}