常见排序算法
1. 衡量排序算法的效率
效率分析：
最好情况、最坏情况、平均情况时间复杂度
对于要排序的数据，有的接近有序，有的完全无序。有序度不同，对于排序的执行时间会有影响。所以需要知道排序算法在不用数据规模下的性能表现。
时间复杂度的系数、常数、低阶
实际开发中，待排序数据规模可能很小。所以进行算法分析时，就得把系数、常数、低阶考虑进来。
比较次数和交换次数
分析效率时，还应该把比较和交换次数考虑进来。
原地排序：
空间复杂度是O(1)的算法。
稳定性：
排序之后，相等元素之间原有的先后顺序不变，则为稳定。
2. 冒泡排序
比较相邻元素，如果不满足大小关系，就互换。
分析：
时间复杂度为
O(1)，是原地排序算法。相同大小的数据，在排序后不会改变顺序，是稳定的排序算法。
最好情况时间复杂度
O(n)，最坏情况时间复杂度O(n^2)，平均情况时间复杂度O(n^2)冒泡排序交换次数等于逆序度，也就是
n*(n - 1)/2 - 初始有序度。
示例代码：
func Bubble(nums []int) []int {
lastEnd := len(nums) - 1
for i := 0; i < len(nums)-1; i++ {
exchange := false
curEnd := 0
for j := 0; j < lastEnd; j++ {
if nums[j] > nums[j+1] {
exchange = true
curEnd = j
nums[j], nums[j+1] = nums[j+1], nums[j]
}
}
if !exchange {
break
}
lastEnd = curEnd
}
return nums
}3. 插入排序
将数组分为两个区间，已排序区间和未排序区间。
初始已排序区间只有一个元素，是数组第一个元素。
取未排序区间元素，在已排序区间找到合适的插入位置，插入元素，重复这个过程。
未排序区间为空，算法结束。
分析：
是原地排序算法
是稳定的排序算法
最好情况时间复杂度
O(n)，最坏情况时间复杂度O(n^2)，平均情况时间复杂度O(n^2)。移动的次数是固定的，等于逆序度。
示例代码：
func Insertion(nums []int) []int {
for i := 1; i < len(nums); i++ {
j := i
cur := nums[j]
for j > 0 && cur < nums[j-1] {
nums[j] = nums[j-1]
j--
}
nums[j] = cur
}
return nums
}4. 选择排序
从未排序区间选择最小的元素，放到已排序区间的末尾。
分析：
是原地排序算法
不稳定的排序算法
最好、最坏、平均情况时间复杂度
O(n^2)
示例代码：
func Selection(nums []int) []int {
for i := 0; i < len(nums)-1; i++ {
minIdx := i
for j := i; j < len(nums); j++ {
if nums[j] < nums[minIdx] {
minIdx = j
}
}
nums[i], nums[minIdx] = nums[minIdx], nums[i]
}
return nums
}5. 冒泡排序 vs 插入排序
冒泡排序的数据交换要比插入排序的数据移动复杂，冒泡排序需要3个赋值操作，而插入排序只需要1个。
6. 归并排序
归并使用的是分治思想。
归并排序的地推公式为：
# 递推公式
merge_sort(p...r) = merge( merge_sort(p...q), merge_sort(q+1...r) )
# 终止条件
p >= r 不再继续分解性能分析：
是稳定的排序算法
最好情况、最坏情况、平均情况时间复杂度都是
O(nlogn)空间复杂度是
O(n)
func Merge(nums []int) []int {
n := len(nums)
if n <= 1 {
return nums
}
mid := (n - 1) >> 1
left := append([]int(nil), nums[:mid+1]...)
right := append([]int(nil), nums[mid+1:]...)
left, right = Merge(left), Merge(right)
i, j, k := 0, 0, 0
for i < len(left) || j < len(right) {
if i < len(left) && (j >= len(right) || left[i] < right[j]) {
nums[k] = left[i]
i++
} else {
nums[k] = right[j]
j++
}
k++
}
return nums
}7. 快速排序
思想：
选择任意一个数据作为分区点
pivot，遍历整个数据，将小于pivot的放在左边，将大于pivot的放在右边，将pivot放在中间。然后递归排序左边区间，和右边区间的数据，直到区间缩小为1。
递推公式：
# 递推公式 quick_sort(p...r) = quick_sort(p...q-1) + quick_sort(q+1...r) # 终止条件 p >= r性能分析：
是原地、不稳定的排序算法
最坏情况下的时间复杂度为
O(n^2)，最好情况、平均情况下的时间复杂度都是O(nlogn)。时间复杂度退化到O(n^2)的概率非常小。
代码示例：
func Quick(nums []int) []int {
if len(nums) <= 1 {
return nums
}
p := partition(nums)
Quick(nums[:p])
Quick(nums[p+1:])
return nums
}
func partition(nums []int) int {
n := len(nums)
pivot := nums[n-1]
i := 0
for j := 0; j < n-1; j++ {
if nums[j] < pivot {
nums[i], nums[j] = nums[j], nums[i]
i++
}
}
nums[i], nums[n-1] = nums[n-1], nums[i]
return i
}8. 桶排序
思想：
将要排序的数据分到几个有序的桶里，每个桶的数据再进行单独排序，一般是快速排序。
桶内排完序后，再把桶内的数据按照顺序依次取出，组成的序列就是有序的。
适用场景：
待排序数据需要很容易就能划分成
m个桶，并且，桶与桶之间有着天然的大小顺序。数据在各个桶之间的分布是比较均匀的。
桶排序比较适合用在外部排序中。外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。
性能分析：
时间复杂度：
O(n)
9. 计数排序
思想：
计数排序其实就是桶排序的一种特殊情况。当要排序的数据所处范围并不大时，比如最大值是
K，就可以将数据划分成K个桶，每个桶内的数据值都是相同的。适用场景：
数据范围并不大，如果数据范围比要排序数据大很多，就不适用计数排序了。
只能给非负整数排序，如果待排序数据是其他类型，要将其在不改变相对大小的情况下，转化为非负整数。
性能分析：
是非原地，稳定的排序算法。
时间复杂度：
O(n)
代码实现
func CountSort(nums []int) []int { n := len(nums) if n <= 1 { return nums } max := nums[0] min := nums[0] for _, cur := range nums { if cur > max { max = cur } if cur < min { min = cur } } count := make([]int, max-min+1) for _, cur := range nums { count[cur-min]++ } for i := 1; i < len(count); i++ { count[i] += count[i-1] } ans := make([]int, n) for i := n - 1; i >= 0; i-- { idx := nums[i] - min count[idx]-- ans[count[idx]] = nums[i] } return ans }
9. 基数排序
适用场景：
数据需要可以分割出独立的“位”来比较，并且位之间有递进的关系。
每一位的数据范围不能太大，要可以用线性排序算法来排序，且每一位的排序算法要是稳定的。
性能分析：
是非原地、稳定的排序算法。
时间复杂度：
O(dn), d是每一位数据的数据集大小空间复杂度：
O(d)
算法总结
时间复杂度
是稳定排序
是原地排序
冒泡排序
O(n^2)
yes
yes
插入排序
O(n^2)
yes
yes
选择排序
O(n^2)
no
yes
快速排序
O(nlogn)
no
yes
归并排序
O(nlogn)
yes
no
计数排序
O(n+k)，k是数据范围
yes
no
桶排序
O(n)
yes
no
基数排序
O(dn) d是维度
yes
no
Last updated
Was this helpful?