时间复杂度排序

O(1)<O(logn)<O(n)<O(nlogn)<O(n的2次方) <O(n的3次方)<O(2的n次方) <O(n的阶乘)<O(n的n次方)

冒泡排序

选择第一个数字和第二个数字,如果第一个>第二个,两者交换位置(假设为升序排序).之后选择第二个和第三个,类似处理直到最后一位.然后忽略已经排好的数字,对剩下的数字在排序.

相邻交换,时间复杂度为O(n^2)

function bubleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length-i; j++){
      if(arr[j]>arr[j+1]){
        [arr[j],arr[j+1]] = [arr[j+1],arr[j]]
      }
    }
  }
}

选择排序

第一轮从数组中找到最小的数组和第一个数组交换

第二轮从第二个数字开始,找到最小的数字,和第二个数字交换位置,之后不断这样.

选择交换,时间复杂度为O(n^2)

function sectionSort(arr) {
  let minIdx
  for (let i = 0; i < arr.length; i++) {
    minIdx = i
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[minIdx] > arr[j]) {
        minIdx = j
      }
    }
    [arr[minIdx], arr[i]] = [arr[i], arr[minIdx]]
  }
}

插入排序

• 从第一个元素开始，该元素可以认为已经被排序
• 取出下一个元素，在已经排序的元素序列中从后向前扫描
• 把取出的元素放到已排序的元素中间的合适位置
• 重复步骤2~3

未排插已排,时间复杂度为O(n^2)

function insertSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    for (let j = 0; j < i; j++) {
      if (arr[i] < arr[j]) {
        arr.splice(j, 0, arr[i])
        arr.splice(i + 1, 1)
        break
      }
    }
  }
}

快速排序

步骤为:

1. 从数组中挑出一个元素,称为"基准"
2. 重新排序数列,所有比基准值小的元素放在基准前面,所有比基准值大的元素放在后面,(相同的数可以放到任意一边).
3. 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序
4. 递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代中，它至少会把一个元素摆到它最后的位置去。

时间复杂度为O(nlogn)

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr
  }
  let leftArr = []
  let rightArr = []
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] <= arr[0]) {
      leftArr.push(arr[i])
    } else {
      rightArr.push(arr[i])
    }
  }
  return quickSort(leftArr).concat(arr[0]).concat(quickSort(rightArr))
}