[译] 排序算法入门 — GO 语言实现
排序算法是一种采用列表或数组并以特定顺序对其元素进行重新排序的算法。有几十种不同的排序算法，如果你已经学习了计算机科学，那么你至少熟悉了其中的一些算法。 它们也是很受欢迎的面试问题，所以在重要面试前不要因为它而伤心。
这是一个大多数常见的排序算法的小型引擎，实例采用 Golang 实现。
冒泡排序
冒泡排序是最基本的就地排序算法，几乎每个人都很熟悉。 它具有 O(n²) 最坏情况和平均时间复杂度，这使得它在大型列表中效率低下。它的实现非常简单。
在循环中，从第一个元素到第 n 个（n = len(items)）迭代数组。比较相邻的值，如果它们的顺序错误，交换它们。 您可以通过在每次迭代后将 n 递减 1 来优化算法。
时间复杂度：
- * 最坏情况下：O(n²)
- * 平均情况下：O(n²)
- * 最好情况下：O(n)
空间复杂度：
* 最坏情况下：O(1)
package main
import (
"fmt"
)
func main() {
items := []int{4, 202, 3, 9, 6, 5, 1, 43, 506, 2, 0, 8, 7, 100, 25, 4, 5, 97, 1000, 27}
bubbleSort(items)
fmt.Println(items)
}
func bubbleSort(items []int) {
var (
n = len(items)
swapped = true
)
for swapped {
swapped = false
for i := 0; i < n-1; i++ {
if items[i] > items[i+1] {
items[i+1], items[i] = items[i], items[i+1]
swapped = true
}
}
n = n - 1
}
}
选择排序
选择排序是另一种简单的平均情况 O(n²) 就地分拣算法。该算法将列表分为两个子列表，一个用于已排序的列表，该列表开始为空，并从列表的开头从左到右构建，第二个子列表用于剩余的未排序的元素。
选择排序可以通过两个嵌套 for 循环来实现。外部循环遍历列表 n 次（n = len(items)）。内部循环将始终以外部循环的当前迭代器值开始（因此在每个迭代中，它将从列表中的更右侧的位置开始），并找出子列表的最小值。使用找到的最小值交换子列表的第一项。
时间复杂度：
- * 最坏情况下：O(n²)
- * 平均情况下：O(n²)
- * 最好情况下：O(n²)
空间复杂度：
* 最坏情况下：O(1)
package main
import (
"fmt"
)
func main() {
items := []int{4, 202, 3, 9, 6, 5, 1, 43, 506, 2, 0, 8, 7, 100, 25, 4, 5, 97, 1000, 27}
selectionSort(items)
fmt.Println(items)
}
func selectionSort(items []int) {
var n = len(items)
for i := 0; i < n; i++ {
var minIdx = i
for j := i; j < n; j++ {
if items[j] < items[minIdx] {
minIdx = j
}
}
items[i], items[minIdx] = items[minIdx], items[i]
}
}
插入排序
插入排序是简单的就地 O(n²) 排序算法。同样，它在大型列表中效率较低，但它具有很少有的优点：
* 自适应：时间复杂度随着已经基本排序的列表而减少 – 如果每个元素不超过其最终排序位置的 k 个位置，则 O(nk) * 稳定：相等值的索引的相对位置不变 * 就地：只需要一个常数 O(1) 的额外的内存空间 * 在实践中比泡沫或选择排序更有效
时间复杂度：
- * 最坏情况下：O(n²)
- * 平均情况下：O(n²)
- * 最好情况下：O(n)
空间复杂度：
* 最坏情况下：O(1)
实现是非常自然的，因为它的工作方式类似于你如何排序手中的排，如果你正在玩一个纸牌游戏。
package main
import (
"fmt"
)
func main() {
items := []int{4, 202, 3, 9, 6, 5, 1, 43, 506, 2, 0, 8, 7, 100, 25, 4, 5, 97, 1000, 27}
insertionSort(items)
fmt.Println(items)
}
func insertionSort(items []int) {
var n = len(items)
for i := 1; i < n; i++ {
j := i
for j > 0 {
if items[j-1] > items[j] {
items[j-1], items[j] = items[j], items[j-1]
}
j = j - 1
}
}
}
希尔排序(shell sort)
希尔排序是插入排序的泛化。这是一个有趣的排序算法，通过将列表排列成一组交错排序的子列表来工作。
首先，选择一连串的间隙。有许多不同的公式来产生间隙序列，算法的平均时间复杂度取决于这个变量。例如，我们选择 (2 ^ k ) – 1，前缀为1，这将给我们[1,3,7,15,31,63 …]。 反转顺序：[…，63，31，15，7，3，q]。
现在遍历颠倒的间隙列表，并在每个子列表中使用插入排序。所以在第一次迭代中，每第63个元素都应用插入排序。在第二次迭代中，每31个元素应用插入排序。所以一路下来到1。最后一次迭代将在整个列表中运行插入。
时间复杂度：
- * 最坏情况下：O(n(log(n))²)
- * 平均情况下：依赖于间隙序列
- * 最好情况下：O(n(log(n)))
空间复杂度：
* 最坏情况下：O(1)
package main
import (
"fmt"
)
func main() {
items := []int{4, 202, 3, 9, 6, 5, 1, 43, 506, 2, 0, 8, 7, 100, 25, 4, 5, 97, 1000, 27}
shellshort(items)
fmt.Println(items)
}
func shellshort(items []int) {
var (
n = len(items)
gaps = []int{1}
k = 1
)
for {
gap := pow(2, k) + 1
if gap > n-1 {
break
}
gaps = append([]int{gap}, gaps...)
k++
}
for _, gap := range gaps {
for i := gap; i < n; i += gap {
j := i
for j > 0 {
if items[j-gap] > items[j] {
items[j-gap], items[j] = items[j], items[j-gap]
}
j = j - gap
}
}
}
}
func pow(a, b int) int {
p := 1
for b > 0 {
if b&1 != 0 {
p *= a
}
b >>= 1
a *= a
}
return p
}
梳排序
梳排序是冒泡排序算法的改进。虽然冒泡排序总是比较相邻元素（gap = 1），梳排序以 gap = n/1.3 开始，其中 n = len(items)，并在每次迭代时缩小 1.3 倍。
这种改进背后的想法是消除所谓的海龟（靠近列表末尾的小值）。最后的迭代与 gap = 1 的简单冒泡排序相同。
时间复杂度：
- * 最坏情况下：O(n²)
- * 平均情况下：O(n²/2^p) (p 是增量的数量)
- * 最好情况下：O(n(log(n)))
空间复杂度：
* 最坏情况下：O(1)
package main
import (
"fmt"
)
func main() {
items := []int{4, 202, 3, 9, 6, 5, 1, 43, 506, 2, 0, 8, 7, 100, 25, 4, 5, 97, 1000, 27}
combsort(items)
fmt.Println(items)
}
func combsort(items []int) {
var (
n = len(items)
gap = len(items)
shrink = 1.3
swapped = true
)
for swapped {
swapped = false
gap = int(float64(gap) / shrink)
if gap < 1 {
gap = 1
}
for i := 0; i+gap < n; i++ {
if items[i] > items[i+gap] {
items[i+gap], items[i] = items[i], items[i+gap]
swapped = true
}
}
}
}
归并排序
归并排序是一种非常有效的通用排序算法。这是分治算法的典型应用，这意味着列表被递归地分解成更小的列表，这些列表被排序然后被递归地组合以形成完整的列表。
来自维基百科：在概念上，合并排序的工作方式如下： 1.将未排序的列表划分为n个子列表，每个子列表包含1个元素（1个元素的列表被视为排序）。 2.重复合并子列表以生成新的排序子列表，直到只剩下1个子列表。 这将是排序列表。
时间复杂度：
- * 最坏情况下：O(n(log(n)))
- * 平均情况下：O(n(log(n)))
- * 最好情况下：O(n(log(n)))
空间复杂度：
* 最坏情况下：O(n)
package main
import (
"fmt"
)
func main() {
items := []int{4, 202, 3, 9, 6, 5, 1, 43, 506, 2, 0, 8, 7, 100, 25, 4, 5, 97, 1000, 27}
sortedItems := mergeSort(items)
fmt.Println(sortedItems)
}
func mergeSort(items []int) []int {
var n = len(items)
if n == 1 {
return items
}
middle := int(n / 2)
var (
left = make([]int, middle)
right = make([]int, n-middle)
)
for i := 0; i < n; i++ {
if i < middle {
left[i] = items[i]
} else {
right[i-middle] = items[i]
}
}
return merge(mergeSort(left), mergeSort(right))
}
func merge(left, right []int) (result []int) {
result = make([]int, len(left)+len(right))
i := 0
for len(left) > 0 && len(right) > 0 {
if left[0] < right[0] {
result[i] = left[0]
left = left[1:]
} else {
result[i] = right[0]
right = right[1:]
}
i++
}
// Either left or right may have elements left; consume them.
// (Only one of the following loops will actually be entered.)
for j := 0; j < len(left); j++ {
result[i] = left[j]
i++
}
for j := 0; j < len(right); j++ {
result[i] = right[j]
i++
}
return
}
湘公网安备 43102202000103号