排序算法

参考

1. 冒泡排序 bubble sort

描述

1. 比较相邻元素,如果第一个比第二个大,交换位置
2. 对每一对相邻元素执行同样的工作,从开始第一对到结尾最后一对,这样最后的元素越来越大
3. 对所有元素重复,除了最后一个
4. 重复 1-3,直到排序完成

动图

代码实现

function bubbleSort(arr: number[]): number[] {
  for (let i = 0; i < arr.length - 1; i++) {
    console.log('index', i)
    let hasChange = false
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        hasChange = true
        arr[j] = arr[j] + arr[j + 1]
        arr[j + 1] = arr[j] - arr[j + 1]
        arr[j] = arr[j] - arr[j + 1]
      }
    }
    if (!hasChange) {
      break
    }
  }
  return arr
}

复杂度

• 空间复杂度 O(1): n 元素数组,整个过程中,直接在给定的数组内两两交换

• 时间复杂度 O(n^2) :

  • 1. 给定数组顺序已经排好,只需要进行 n-1 次比较,两两交换次数为 0,时间复杂度为 O(n)
  • 2. 给定数组逆序,需要 n(n-1)/2 次比较,时间复杂度是 O(n^2)
  • 3. 综合平均时间复杂度是 O(n^2)

2. 插入排序 Insertion Sort

原理

对未排序的数据,在已排序的序列中从后向前扫描,找到相应的位置插入

描述

1. 从第一个元素开始,该元素认为已经被排序
2. 取出下一个元素,在已经排序的序列中从后向前扫描
3. 如果取出的元素小于当前扫描的元素,将该扫描元素移动到下一位
4. 知道找到大于等于的情况,插入该元素
5. 重复 2-5

动图

代码实现

function insertionSort(arr: number[]): number[] {
  let preIndex, current
  for (let i = 1; i < arr.length; i++) {
    preIndex = i - 1
    current = arr[i]
    while (preIndex >= 0 && arr[preIndex] > current) {
      arr[preIndex + 1] = arr[preIndex]
      preIndex--
    }
    arr[preIndex + 1] = current
  }
  return arr
}

复杂度

• 空间复杂度:O(1)
• 时间复杂度:O(n^2)
  • 1. 给定元素已经排好,只需要进行 n-1 次比较,时间复杂度是 O(n)
  • 2. 给定数组是逆序排列,需要进行 n(n-1)/2 次比较,复杂度是 O(n^2)
  • 3. 所以平均复杂度是 O(n^2)

leetcode

147

3. 归并排序 Merge Sort

采用分治法(Divide and Conquer),将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,成为2-路归并

描述

• 1. 把长度为 n 的输入序列分成两个长度为 n/2 的子序列
• 2. 对这两个子序列分别归并排序
• 3. 将两个顺序排好的子序列合并成一个最终的排序序列

动图

代码实现

function mergeSort(arr: number[]): number[] {
  function merge(left: number[], right: number[]): number[] {
    let result = []
    while (left.length > 0 && right.length > 0) {
      if (left[0] < right[0]) {
        result.push(left.shift())
      } else {
        result.push(right.shift())
      }
    }
    while (left.length) {
      result.push(left.shift())
    }
    while (right.length) {
      result.push(right.shift())
    }
    return result
  }
  let len = arr.length
  if (len < 2) {
    return arr
  }
  let mid = Math.floor(len / 2),
    left = arr.slice(0, mid),
    right = arr.slice(mid)
  return merge(mergeSort(left), mergeSort(right))
}

复杂度

• 时间复杂度: T(n)

  • 时间复杂度函数 T(n)= 2 * T(n/2)+ 合并时间(n)
  • 整体复杂度 O(nlogn)
  • 推到过程

• 空间复杂度: O(n)

4. 快速排序

也采用了分治的思想,把原始数组,分成两个子数组,然后递归排序两个子数组

描述

采用分治法来把一个串(list)分成两个子串(sub-list).

• 从数列中挑出一个元素,称为"基准"(pivot)
• 重新排序数列,所有币基准值小的防止基准前面,大的放后面.这个分区退出之后,该基准就处在数列的中间位置.这个称 为分区(partition)操作
• 递归的( recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序

动图说明

代码实现

如果从小到大,就从大的指针移动;若果从大到小排序,就从小指针开始.

function quickSort(arr: number[], begin: number, end: number) {
  if (begin > end) return
  const pivot = arr[begin] //设置基准值
  let i = begin + 1
  let j = end
  while (i != j) {
    while (arr[j] >= pivot && j > i) {
      j--
    }
    while (arr[i] <= pivot && j > i) {
      i++
    }
    if (j > i) {
      swap(arr, i, j)
    }
  }
  swap(arr, begin, i)
  quickSort(arr, begin, i - 1)
  quickSort(arr, i + 1, end)
}

复杂度

• 时间复杂度:
  • 最优,每次选择的都是中间值,T(n)=2*T(n/2)+O(n), 所以是 O(nlogn)
  • 最差,每次选择的值都是最大或者最小的,O(n^2)
• 空间复杂度:只需要 O(1)的存储空间来完成交换,递归次数是 logn,==O(n)

5. 选择排序

function selectionSort(arr) {
  let tempIndex
  for (let i = 0; i < arr.length; i++) {
    tempIndex = i
    for (let j = i; j < arr.length; j++) {
      if (arr[tempIndex] > arr[j]) {
        tempIndex = j
      }
    }
    if (tempIndex !== i) {
      ;[arr[tempIndex], arr[i]] = [arr[i], arr[tempIndex]]
    }
  }
  console.log(arr)
  return arr
}