Laravel
话题列表 社区 Wiki 优质外文 招聘求职 Laravel 实战教程 社区文档
登录
注册

卷算法——排序

悲剧不上演 的个人博客 / 140 / 2 / 创建于 2年前 / 更新于 2年前

系列文章：
卷算法——时间复杂度 卷算法——排序

排序

  • 原地排序：特指空间复杂度为 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 次 即可实现数据排序

  • 过程详解

    file

  • 代码段

    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. 重复上述过程，直到数据取完

  • 过程图

    file

  • 代码

      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. 重复上述过程，直到数据取完

  • 过程图

    file

  • 代码

    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 中只有一个元素的时候，我们就可以将其带入上面的表达式层层计算

  • 过程图解

    file

  • 代码段

    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. 完成

  • 过程图

    file

  • 原地 partition 过程图

    file

  • 代码

    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. 数据在各个桶之间分布均匀

  • 过程图

    file

  • 代码段

  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. 数据范围不大

  • 过程图

    ​ file

  • 代码段

    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)

排序对比

排序算法 原地排序 稳定排序 (最好，最坏，平均）时间复杂度 说明
冒泡排序 Y Y O(n) , O(n^2), O(n^2) 效率不高，适用数据量少
插入排序 Y Y O(n) , O(n^2), `O(n^2) 效率不高，适用数据量少
选择排序 Y N O(n^2) 效率不高，适用数据量少
归并排序 N Y O(n log n) 适用与数据量多，但是由于不是原地排序，不常用
快速排序 Y N O(n log n) , O(n^2), O(n log n) 快速排序的效率几乎都接近于 O(n log n)
桶排序 N Y看桶内算法 O(n) 使用限制非常多
计数排序 N Y O(n+k) k是数据范围 数据范围不能大，数值都可以用标下表示。如 年龄k=0-100
基数排序 N Y O(dn) d是维度 如手机号例子中d时表示11位

优化排序

优化快速排序

优化分区点

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

  1. 三数取中

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

  2. 随机法

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

递归小心堆栈溢出

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

排序
本作品采用《CC 协议》，转载必须注明作者和本文链接
悲剧不上演
课程读者 276 声望
一个拍黄片的开发仔
《L05 电商实战》
《L05 电商实战》
从零开发一个电商项目，功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
《G01 Go 实战入门》
《G01 Go 实战入门》
从零开始带你一步步开发一个 Go 博客项目，让你在最短的时间内学会使用 Go 进行编码。项目结构很大程度上参考了 Laravel。
讨论数量: 2
排序：
时间 投票
悲剧不上演
课程读者 276 声望

图片建议大家打开一个新的窗口看图片。非常清晰 :smile:

2年前 评论
九霄道长
课程读者 200 声望 / 全干工程师 @ 家里蹲

牛啊

2年前 评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容，与人为善，比聪明更重要！
支持 MD 帮助
悲剧不上演
未填写
文章
14
粉丝
30
喜欢
361
收藏
277
排名：148
访问：6.6 万
私信
所有博文
文章归档
1 篇 2022 年 12 月 1 篇 2022 年 1 月 1 篇 2021 年 12 月 1 篇 2021 年 11 月 1 篇 2020 年 2 月 2 篇 2019 年 3 月 1 篇 2019 年 2 月 1 篇 2018 年 12 月 1 篇 2018 年 7 月 1 篇 2018 年 6 月 2 篇 2018 年 1 月 1 篇 2017 年 11 月
最新文章 最受欢迎
1年前 透视内存中数据 2年前 卷算法——排序 2年前 感觉PHP-FPM进程数不够？ 2年前 卷算法——时间复杂度 4年前 队列顺序性引发的思考
113 用了那么多 LNMP, 你真的了解 N 与 P 交互吗？ 51 你生产环境的 Composer 是这样吗？ 47 感觉PHP-FPM进程数不够？ 46 闭包匿名函数，还在傻傻搞不清楚吗？ 26 延迟静态绑定——static
博客标签
composer
2
 laravel
1
 queue
1
 closure
1
 php-fpm
1
 Sessiones
1
 排序
1
 自动加载
1
 三次握手
1
 systemcall
1
社区赞助商
成为赞助商

关于 LearnKu

LearnKu 是终身编程者的修道场
做最专业、严肃的技术论坛
LearnKu 诞生的故事

资源推荐

  • 《社区使用指南》
  • 《文档撰写指南》
  • 《LearnKu 社区规范》
  • 《提问的智慧》

    • 服务提供商

    其他信息

  • 成为版主
  • 所有测验
  • 联系站长（反馈建议）

    • 粤ICP备18099781号-6 | 粤公网安备 44030502004330号 | 违法和不良信息举报

    由 Summer 设计和编码 ❤

    请登录

    内容举报
    匿名举报，为防止滥用，仅管理员可见举报者。

    我要举报该，理由是：

    取消