Go语言排序算法｜青训营笔记

2023-06-09 14:43| 来源: 网络整理| 查看: 265

插入排序

基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增 1 的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

时间复杂度：

最差和平均：O(n^2) 最好：O(n) 快速排序

分治思想

基本思想：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止

时间复杂度：

最坏：O(n^2) 最好：O(nlogn) 堆排序

基本思想：

将待排序的序列构造成一个大堆，根据大堆的性质，当前堆的根节点（堆顶）就是序列中最大的元素；将堆顶元素和最后一个元素交换，然后将剩下的节点重新构造成一个大堆；重复步骤2，如此反复，从第一次构建大堆开始，每一次构建，我们都能获得一个序列的最大值，然后把它放到大堆的尾部。最后，就得到一个有序的序列了。

时间复杂度：O(nlogn)

Benchmark

插入排序在短序列中速度最快

快速排序在其他情况下速度最快

堆排序速度于最快算法差距不大

插入排序在序列已有序的情况下速度最快

结论.png

【本文地址】

今日新闻