排序

• 原地排序：特指空间复杂度为 O(1) 的排序算法。

• 稳定性：如果待排序的数据中存在相同的数据，如 [{"name":"cx", "age": 18}, {"name":"cx3", "age":18}], 我们根据年龄排序这两个数据都等于 18。 如果排序之后的这两个数据顺序没有发生变化则称为该算法具有稳定性。

• 有序度：一组数据有中有多少对能满足 i<j ; a[i] < a[j]。如 2,3,4,1 这样一组数据中，有序度分别为 2,3, 2,4, 3,4 。

• 满有序度：所有的数据都是有序的。如 1,2,3,4，值为 n*(n-1)/2

  (n-1)+(n-2)+(n-3)+...+1+0 = \\ \frac { n \times(n-1)}2

• 逆序度：与有序度相反，组数据有中有多少对能满足 i< j ; a[i] > a[j]。逆有序度 = 满有序度 - 有序度

1. 冒泡排序（Bubble Sort）

冒泡排序只会操作相邻的两个数据，每次冒泡操作都会对相邻的两个元素比较。看是否满足大小关系要求。如果不能满足则交换。一次冒泡至少让一个数据放到它该放到位置。重复 n 次 即可实现数据排序

• 过程详解

  

• 代码段

  package main
  
  import "fmt"
  
  func main() {
      data := [...]int{4, 5, 6, 3, 2, 1}
      BubbleSort(&data)
      fmt.Println(data)
      data2 := [...]int{1, 2, 3, 4, 5, 6}
      BubbleSort(&data2)
      fmt.Println(data2)
  }
  
  func BubbleSort(data *[6]int)  {
      for j := 0; j < len(data); j++ {
          // 为啥是 len(data)-j-1
          //    因为后面有的数据已经拍好序了
          // 比如说第一次冒泡后 a[5] = 6 这个已经确定了。所以循环比较的时候就不用比较a[5]
          flag := false
          for i := 0; i < len(data)-j-1; i++ {
              if data[i] > data[i+1] {
                  data[i+1], data[i] = data[i], data[i+1]
                  flag = true
              } else {
                  flag = false
              }
          }
  
          fmt.Printf("第%d次冒泡排序后的数据:%v\n", j+1, data)
          if !flag {
              break
          }
      }
  }
  

• 是否是原地排序

  是，空间复杂度为 O(1)

• 是否是稳定排序

  是。因为想两个数据相等时候没有发生交换。

• 时间复杂度

  • 最好时间复杂度 O(n), 因为已经排好序了

  • 最坏时间复杂度O(n^2), 需要进行 n 次冒泡

  • 平均时间复杂度 O(n^2)，推导公式

    \\ 满有虚度 = \frac { n \times(n-1)}2 \\ 初始有序度：[0,\frac { n \times(n-1)}2]，取中间值 \frac { n \times(n-1)}4

    交换次数 = 逆序度 = 满有序度 - 初始有序度 \\ = \frac { n \times(n-1)}2 - \frac { n \times(n-1)}4 \\ = \frac { n \times(n-1)}4 \\ = O(n^2)

---

2. 插入排序(Insert Sort)

• 思路

  1. 将数组分为两个区间。已排序区和未排序区，已排序区初始只有第一个元素。
  2. 取未排序数组区间中的元素，在已排序区间中找到合适的位置插入，并保证一直有序
  3. 重复上述过程，直到数据取完

• 过程图

  

• 代码

    package main
  
    import "fmt"
  
    func main() {
        data := [...]int{4, 5, 6, 3, 2, 1}
        InsertSort(&data)
        fmt.Println(data)
    }
  
    func InsertSort(data *[6]int) {
        for i := 1; i < len(data); i++ {
            t := data[i]
            j := i - 1
            for ; j >= 0; j-- {
                // 大于这个数了,证明找到了这个数的正确插入位置
                if t > data[j] {
                    data[j+1] = t
                    break
                } else {
                    // 复制数据
                    // 比如将a[5] = a[4], 因为最后一个元素是没有用的
                    data[j+1] = data[j]
                }
            }
  
            // 即使没有找到，j = -1，这个时候就应该给 data[0] 赋值
            data[j+1] = t
  
        }
    }
  

• 是否是原地排序

  是，空间复杂度为 O(1)

• 是否是稳定排序

  是。假设有相同的数据，我们可以将其插入到上一个元素前面，因为我们是顺序遍历。

• 时间复杂度

  • 最好时间复杂度 O(n), 因为已经排好序了
  • 最坏时间复杂度O(n^2), 数据完全是逆序
  • 平均时间复杂度 O(n^2)，往数组中插入一个元素平均复杂度 O(n), 我们需要插入 n 次。就是 n^2

---

3. 选择排序(Select Sort)

• 思路

  1. 将数组分为两个区间。已排序区和未排序区
  2. 选择排序每次从未排序的区间找到最小的元素，将其放到有序区间的末尾
  3. 重复上述过程，直到数据取完

• 过程图

  

• 代码

  package main
  
  import "fmt"
  
  func main() {
      data := [...]int{4, 5, 6, 3, 2, 1}
      SelectSort(&data)
      fmt.Println(data)
  }
  
  func SelectSort(data *[6]int) {
      // i 表示有序集合的指针
      for i := 0; i < len(data) - 1; i++ {
          min := i
          // j 表示无序集合的指针
          for j := i + 1; j < len(data); j++ {
              if data[min] > data[j] {
                  min = j
              }
          }
  
          // 交换数据
          data[min], data[i] = data[i], data[min]
          fmt.Printf("第%d交换排序后的数据%v\n", i+1, data)
      }
  }
  

• 是否是原地排序

  是，空间复杂度为 O(1)

• 是否是稳定排序

  否。假设有相同的数据，我们在交换的过程中就会导致其位置发生了变化

• 时间复杂度

  复杂度 O(n^2)

---

4. 归并排序(Merge Sort)

• 思路

  思想就是分治思想。就是把一组数据分为两部分，然后在对这两部分进行归并排序。再将排好序的两部分合为一个，然后进行合并。这样整个数据就有序了。公式如下：

  tmp = \frac {(start - end)} {2} \\ result = merge(S(0,tmp),S(tmp+1,end)) \\ S(0,tmp) = merge(S(0,\frac {tmp}2),S(\frac {tmp}2+1,tmp)) \\ S(0,\frac {tmp}2) = merge(S(0,\frac {tmp}4),S(\frac {tmp}4+1,{tmp}2)) \\ ... \\ 直到 S 中只有一个元素的时候，我们就可以将其带入上面的表达式层层计算

• 过程图解

  

• 代码段

  package main
  
  import (
      "fmt"
  )
  
  func main() {
      data := []int{6, 5, 10, 3, 2, 1}
      mergeSort(0, len(data)-1, data)
      fmt.Println(data)
  }
  
  func mergeSort(start, end int, data []int) {
      if start >= end {
          return
      }
  
      mid := (start + end) / 2
      mergeSort(start, mid, data)
      mergeSort(mid+1, end, data)
      merge(data, start, mid, end)
  
  }
  
  func merge(data []int, start, mid, end int) {
      i, j, k := start, mid+1, 0
      result := make([]int, end-start+1)
      for ; i <= mid && j <= end; k++ {
          if data[i] > data[j] {
              result[k] = data[j]
              j++
          } else {
              result[k] = data[i]
              i++
          }
      }
  
      for ; i <= mid; i++ {
          result[k] = data[i]
          k++
      }
  
      for ; j <= end; j++ {
          result[k] = data[j]
          k++
      }
  
      copy(data[start:end+1], result)
  
  }
  

• 是否是原地排序

  否，空间复杂度为 O(n)

• 是否是稳定排序

  是。因为当数据相同的时候 merge 可以保证前后顺序不变

• 时间复杂度O(nlog n)

  已知：C是常量:T_{(1)} = C \\ 递归的公式为: T_{(n)} = T_{(a)} + T_{(b)} + K \\ 在归并排序中 k = merge 函数时间复杂度 = O_{(n)} \\ 带入到递归公式： \\ T_{(n)} = 2 \times T_{(\frac n 2)} + n \\ = 2 \times (2 \times T_{(\frac n 4)} + \frac n 2) + n =4 \times T_{(\frac n 4)} + 2n \\ = 4 \times (2 \times T_{(\frac n 8)} + \frac n 4) + 2n = 8 \times T_{(\frac n 8)} + 3n \\ = 8 \times ( 2 \times T_{(\frac n {16})} + \frac n 8) + 3n = 16 \times T_{(\frac n {16})} +4n \\ = ... \\ = 2^k \times T_{(\frac n {2^k})} + kn \\ \because T_{(1)} = C \\ \therefore T_{(1)} = T_{(\frac n {2^k})} \\ \therefore k = log_2 n \\ 带入上面公式 T_{(n)} = 2^k \times T_{(\frac n {2^k})} + kn \\ T_{(n)} = n \times C + log_2 n \times n \\ \therefore 时间复杂度为 O_{(nlog n)}

---

5. 快速排序(Quick Sort)

• 思路

  ​ 利用的也是分治思想。

  1. 如果要排序的数组中下标P到R之间的一组数据，任意选择一个数据作为 pivot(分区点)
  2. 遍历P到R，小于 pivot 在左边，大于 pivot 在右边。
  3. 递归左边区域继续执行1-2，递归右边区域执行1-2。直到数据取完
  4. 完成

• 过程图

  

• 原地 partition 过程图

  

• 代码

  package main
  
  import "fmt"
  
  func main() {
      data := []int{8, 10, 2, 3, 6, 1, 5}
      QuickSort(data, 0, len(data)-1)
      fmt.Println(data)
  }
  
  func QuickSort(data []int, p, r int) {
      if p >= r {
          return
      }
  
      index := partitionV2(data, p, r)
      if index > 0 {
          QuickSort(data, p, index-1)
  
      }
  
      if index < len(data)-1 {
          QuickSort(data, index+1, r)
      }
  }
  
  // 分区函数，通过分区点，将[p,r] 之间的数据排列为 [<pivot, pivot, > pivot]
  // 原地函数
  func partitionV2(data []int, p int, r int) int {
      pivot := data[r]
      i := p
      for j := p; j < r; j++ {
          if data[j] < pivot {
              // 交换 I J
              data[i], data[j] = data[j], data[i]
              i++
          }
      }
  
      // 交换分区点
      data[i], data[r] = data[r], data[i]
      fmt.Printf("分区[%d,%d]完成,分区点为%d\n", p, r, i)
      return i
  }
  
  // 分区函数，通过分区点，将[p,r] 之间的数据排列为 [<pivot, pivot, > pivot]
  // 创建两个临时变量来满足
  func partition(data []int, p, r int) int{
      pivot := data[r]
      a := make([]int, 0, r-p+1)
      b := make([]int, 0, r-p+1)
  
      for i := p; i <= r-1; i++ {
          if data[i] < pivot {
              a = append(a, data[i])
          } else {
              b = append(b, data[i])
          }
      }
  
      i := p
      for ; i < len(a)+p; i++ {
          data[i] = a[i-p]
      }
  
      data[i] = pivot
      for j := r; j > r-len(b); j-- {
          data[j] = b[r-j]
      }
  
      fmt.Printf("分区[%d,%d]完成,分区点为%d\n", p, r, i)
  
      return i
  }
  

• 是否是原地排序

  是，partitionV2 为原地函数

• 是否是稳定排序

  否。

• 时间复杂度

  • 最好时间复杂度 O(nlog n)， 推导公式如归并排序。我们每次选择的分区点将其一分为二
  • 最坏时间复杂度O(n^2), 当数据完全有序的时候，每次都选择最后一个分区点
  • 平均时间复杂度O(nlog n)

---

6. 桶排序(Bucket Sort)

• 思路

  ​ 将要排序的数据分到几个有序的桶里。每个桶里的数据在进行快速排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出。组装的序列就是有序的。（如果桶内分布不可将大桶在进行分解）

• 使用场景

  1. 要排序的数据很容易划分到 m 桶里
  2. 桶与桶之间有着天然的的大小顺序（如下图）
  3. 数据在各个桶之间分布均匀

• 过程图

  

• 代码段

  package main

  import "fmt"

  func main() {
      data := []int{7, 8, 9, 25, 20, 29, 40, 49, 48, 47, 42, 44, 35, 15, 13, 19}
      BucketSort(data)
      fmt.Println(data)
  }

  // 获取待排序数组中的最大值
  func getMax(a []int) int {
      max := a[0]
      for i := 1; i < len(a); i++ {
          if a[i] > max {
              max = a[i]
          }
      }
      return max
  }

  // 获取待排序数组中的最小值
  func getMin(a []int) int {
      min := a[0]
      for i := 1; i < len(a); i++ {
          if a[i] < min {
              min = a[i]
          }
      }
      return min
  }

  // 桶排序
  func BucketSort(data []int) {
      max := getMax(data)
      min := getMin(data)
      // 桶数量等于数据长度
      bucketNum := len(data)


      // 1. 创建 bucketNum 个桶
      bucket := make([][]int, bucketNum)

      // 2. 将数据放入桶中
      for i := 0; i < len(data); i++ {
          // 桶下标
          // 桶与桶之间区间跨度 d 公式 (最大数-最小数)/(桶数量 - 1)
          // 桶数量 - 1 是因为最大数占了一个桶
          // 所有下标等于每个元素的偏移量(data[i] - min) / (d) = (data[i] - min) / ((最大数-最小数)/(桶数量 - 1)) = (data[i] - min) * (桶数量 - 1) / (最大数-最小数)
          index := (data[i] - min) * (bucketNum - 1) / (max - min)
          bucket[index] = append(bucket[index], data[i])
      }

      // 3. 桶内排序，这里我们采用快排
      for i := 0; i < bucketNum; i++ {
          quitSortByArray(bucket[i])
      }

      // 4. 取出桶内数据然后进行输出
      result := make([]int, 0, len(data))
      for i := 0; i < bucketNum; i++ {
          result = append(result, bucket[i]...)
      }

      copy(data, result)
  }

  func quitSortByArray(data []int) {
      QuickSort(data, 0, len(data) - 1)
  }

  func QuickSort(data []int, p, r int) {
      if p >= r {
          return
      }

      index := partition(data, p, r)
      if index > 0 {
          QuickSort(data, p, index-1)

      }

      if index < len(data)-1 {
          QuickSort(data, index+1, r)
      }
  }

  // 分区函数，通过分区点，将[p,r] 之间的数据排列为 [<pivot, pivot, > pivot]
  // 原地函数
  func partition(data []int, p int, r int) int {
      pivot := data[r]
      i := p
      for j := p; j < r; j++ {
          if data[j] < pivot {
              // 交换 I J
              data[i], data[j] = data[j], data[i]
              i++
          }
      }

      // 交换分区点
      data[i], data[r] = data[r], data[i]
      fmt.Printf("分区[%d,%d]完成,分区点为%d\n", p, r, i)
      return i
  }

• 时间复杂度 O(n)

  已知：n 个元素， m个桶,每个桶的元素 k \\ \therefore k = \frac n m \\ \therefore T_{(n)} = m \times (k \times \log k) \\ = m \times (\frac n m \times \log {\frac n m}) \\ =n \times \log {\frac n m} \\ \because 当 桶的个数与元素 n 无限接近的时候 ，\frac n m 等于常量 \\ \therefore T_{(n)} = n \\ \therefore 时间复杂度:O(n)

参考链接

漫画：什么是桶排序？

---

7. 计数排序(Count Sort)

• 思路

  1. 将所有的数值设置为每一个独立的桶，一个桶存的就是等于这个数据的人数，eg： 桶 n 存的就是小于等于 n 的值的数量
  2. 然后遍历原始数据，给该桶填充数据。
  3. 然后在遍历原始数据，每一个元素都对应一个桶，桶中的值就是该元素在结果集中的位置，然后减一

• 应用场景

  1. 数据范围不大

• 过程图

  ​

• 代码段

  package main
  
  import "fmt"
  
  func main() {
      data := []int{2, 5, 3, 0, 2, 3, 0, 3}
      countSort(data)
      fmt.Println(data)
  }
  
  func countSort(data []int) {
      // 1. 寻找最大元素
      max := data[0]
      for i := 1; i < len(data); i++ {
          if data[i] > max {
              max = data[i]
          }
      }
  
      // 2. 组装桶数据
      countBucket := make([]int, max+1)
      for i := 0; i < len(data); i++ {
          countBucket[data[i]]++
      }
      for i := 1; i < len(countBucket); i++ {
          countBucket[i] += countBucket[i-1]
      }
  
      // 3.计算结果数据
      result := make([]int, len(data))
      for i := 0; i < len(data); i++ {
          countBucket[data[i]]--
          result[countBucket[data[i]]] = data[i]
      }
  
      copy(data, result)
  }
  

• 时间复杂度 O(n)

---

8. 基数排序（Radix Sort）

• 思路

  ​ 对要排序的数据是要求，要求可以分割出独立的”位“来比较，而且位之间有递进关系，如果数据a的高位比b大，那么剩下的位就不用比较了。而且，为每一位的数据范围不能太大，要可以用线性排序算法来排序（必须是稳定排序算法）。这样时间复杂度就可以做到 O(n)

• 应用场景

  1. 可以按位比较（如手机号）
  2. 位内的数据范围不大可使用线性排序

• 过程图

• 代码

• 时间复杂度 O(n)

---

排序对比

---

优化排序

优化快速排序

优化分区点

​ 我们知道快排的时间复杂度有可能退化到 O(n^2)， 就是数据近乎有序的时候，我们选择分区点还是选择第一位、或者是最后一位这种思路。要想保证快排的时间复杂度不会退化太差，因此我们需要合理的选择分区点

1. 三数取中

   从区间的首尾中三部分取出三个数据比较大小，中间的数据作为分区点。这样只比单纯取一个数要好。当数据量多的时候我们可以 五数取中、时数取中

2. 随机法

   每次要排序的数据中随机选择一个元素作为分区点，从概率上来看，不太可能出现分区点都很差的情况

递归小心堆栈溢出

​ 这也是我们在递归中描述的方案：设置最大递归层数。

本作品采用《CC 协议》，转载必须注明作者和本文链接