快秋招了，面试的时候算法也是必备的。本文介绍几种常见的排序算法，建议背下来，面试的时候提前手写一遍快排(快速排序)可以提高手感，事半功倍。

1. 冒泡排序

冒泡排序是通过比较两个相邻元素的大小实现排序，如果前一个元素大于后一个元素，就交换这两个元素。这样就会让每一趟冒泡都能找到最大一个元素并放到最后。

func bubbleSort(nums []int) {
  for i := 0; i < len(nums)-1; i++ {
    for j := 0; j < len(nums)-1-i; j++ {
      if nums[j] > nums[j+1] {
        nums[j], nums[j+1] = nums[j+1], nums[j]
      }
    }
  }
}

稳定性：它是指对同样的数据进行排序，会不会改变它的相对位置。比如 [ 1, 3, 2, 4, 2 ] 经过排序后，两个相同的元素 2 位置会不会被交换。冒泡排序是比较相邻两个元素的大小，显然不会破坏稳定性。

空间复杂度：由于整个排序过程是在原数据上进行操作，故为 O(1);

时间复杂度：由于嵌套了 2 层循环，故为 O(n*n);

2. 选择排序

选择排序是每次循环选择最大值，在该次循环结束时将最大值同数组最后的数进行交换

func selectSort(nums []int) {
  for i := 0; i < len(nums)-1; i++ {
    var idx int
    var m = nums[0]
    for j := 1; j < len(nums)-i; j++ {
      if nums[j] > m {
        m = nums[j]
        idx = j
      }
    }
    nums[len(nums)-i-1], nums[idx] = nums[idx], nums[len(nums)-i-1]
  }
}

稳定性：它是从后往前遍历已排序好的序列，相同元素不会改变位置，故为稳定排序；

空间复杂度：它是在原序列进行排序，故为 O ( 1 );

时间复杂度：排序的过程中，首先要遍历所有的元素，然后在已排序序列中找到合适的位置并插入。共需要 2 层循环，故为 O ( n * n );

3. 希尔排序

它的核心思想是把一个序列分组，对分组后的内容进行插入排序，这里的分组只是逻辑上的分组，不会重新开辟存储空间。它其实是插入排序的优化版，插入排序对基本有序的序列性能好，希尔排序利用这一特性把原序列分组，对每个分组进行排序，逐步完成排序。

func shellSort(nums []int) {
  // l = 9
  l := len(nums)
  for gap := l / 2; gap > 0; gap = gap / 2 {
    // i = 4; i < 9; i ++
    for i := gap; i < l; i++ {
      // j=0,1,2,3,4
      // [0]-[4] [1]-[5] [2]-[6] [3]-[7] [4]-[8]
      for j := i - gap; j >= 0; j = j - gap {
        if nums[j] > nums[j+gap] {
          nums[j], nums[j+gap] = nums[j+gap], nums[j]
        }
      }
    }
  }
}

稳定性：它可能会把相同元素分到不同的组中，那么两个相同的元素就有可能调换相对位置，故不稳定。

空间复杂度：由于整个排序过程是在原数据上进行操作，故为 O(1);

时间复杂度：希尔排序的时间复杂度与增量序列的选取有关，例如希尔增量时间复杂度为O(n2)，而Hibbard增量的希尔排序的时间复杂度为O(log n的3/2)，希尔排序时间复杂度的下界是n*log2n

4. 快速排序

首先选择一个点作为base，通过从左侧和从右侧遍历，把小于base的数放在左侧，把大于base的数放在右侧，中间是base；接下来以base为中心，分为两部分，每部分再进行快速排序。

func fastSort(nums []int, start, end int) {
  if end == start {
    return
  }
  base := nums[start]
  left := start
  right := end

  for left < right {
    for left < right && nums[right] > base {
      right--
    }
    nums[left] = nums[right]
    for left < right && nums[left] <= base {
      left++
    }
    nums[right] = nums[left]
  }
  nums[left] = base
  fastSort(nums, start, left-1)
  fastSort(nums, left+1, end)
}

稳定性：不稳定

空间复杂度：不使用额外空间，O(1)

时间复杂度：需要使用递归，时间复杂度nlgn

5. 归并排序

采用分治的思想，把数组分为一个一个子序列，直到子序列只有一个元素停止拆分，然后对每个子序列进行边排序边合并。

func mergeSort(nums []int, start, end int) {
  if end == start {
    return
  }
  mid := start + (end-start)/2
  mergeSort(nums, start, mid)
  mergeSort(nums, mid+1, end)
  merge(nums, start, mid, end)
}
func merge(nums []int, start, mid, end int) {
  for i := mid + 1; i <= end; i++ {
    base := nums[i]
    j := i - 1
    for j >= 0 && nums[j] > base {
      nums[j+1] = nums[j]
      j--
    }
    nums[j+1] = base
  }
}

稳定性：在元素拆分的时候，虽然相同元素可能被分到不同的组中，但是合并的时候相同元素相对位置不会发生变化，故稳定。

空间复杂度：需要用到一个数组保存排序结果，也就是合并的时候，需要开辟空间来存储排序结果，故为 O ( n );

时间复杂度：最好最坏都为 O(nlogn);

6. 计数排序

使用和需排序数组的最大最小值相关的下标数组进行计数，最后根据计数得出排序后的数组。比如nums[8,1,4,6,2,3,5,4]，那么下标数组为atr[1,1,1,2,1,1,0,1]

func countSort(nums []int) {
  if len(nums) == 0 {
    return
  }
  big := nums[0]
  small := nums[0]
  for i := 1; i < len(nums); i++ {
    big = max(nums[i], big)
    small = min(nums[i], small)
  }
  atr := make([]int, big-small+1)
  for _, n := range nums {
    atr[n-small]++
  }
  i := 0
  for j, n := range atr {
    if n > 0 {
      for k := 0; k < n; k++ {
        nums[i] = j + small
        i++
      }
    }
  }
}
func max(a, b int) int {
  if a > b {
    return a
  }
  return b
}
func min(a, b int) int {
  return a + b - max(a, b)
}

稳定性：在元素往 countArr 中记录时按顺序遍历，从 countArr 中取出元素也是按顺序取出，相同元素相对位置不会发生变化，故稳定。

空间复杂度：需要额外申请空间，复杂度为“桶”的个数，故为 O ( k )， k 为“桶”的个数，也就是 countArr 的长度;

时间复杂度：最好最坏都为 O(n+k)， k 为“桶”的个数，也就是 countArr 的长度;