20240110_golang排序
Golang排序
排序算法可以分为内部排序和外部排序。
其中：内部排序是指在内存中对数据进行排序，而外部排序是因为数据量较大，无法一次性放入内存，因此需要访问外部存储。
以下是十种常见的排序算法，具有不同的特点、时间复杂度和稳定性：
1. 冒泡排序（Bubble Sort）：
通过多次比较和交换相邻元素，将最大的元素逐步“冒泡”到数组末尾。
1package main
2
3import "fmt"
4
5func bubbleSort(arr []int) []int {
6 length := len(arr)
7 if length <= 1 {
8 return arr
9 }
10
11 for i := 0; i < length-1; i++ {
12 for j := 0; j < length-i-1; j++ {
13 if arr[j+1] > arr[j] {
14 arr[j], arr[j+1] = arr[j+1], arr[j]
15 }
16 }
17 }
18
19 return arr
20}
21
22func main() {
23 arr := []int{11, 8, 2, 5, 7, 10, 3, 6}
24 fmt.Println(bubbleSort(arr))
25}
冒泡排序的核心思想是通过多次比较和交换相邻元素，将最大的元素逐步“冒泡”到数组末尾。
2. 选择排序（Selection Sort）：
每次从未排序部分选择最小（或最大）的元素，放到已排序部分的末尾。
1package main
2
3import "fmt"
4
5func selectionSort(arr []int) []int {
6 length := len(arr)
7 if length <= 1 {
8 return arr
9 }
10
11 for i := 0; i < length-1; i++ {
12 minIndex := i
13 for j := i + 1; j < length; j++ {
14 if arr[j] < arr[minIndex] {
15 minIndex = j
16 }
17 }
18 arr[i], arr[minIndex] = arr[minIndex], arr[i]
19 }
20
21 return arr
22}
23
24func main() {
25 arr := []int{11, 8, 2, 5, 7, 10, 3, 6}
26 fmt.Println(selectionSort(arr))
27}
选择排序的核心思想是从未排序部分中找到最小（或最大）的元素，将其放到已排序部分的末尾。
3. 插入排序（Insertion Sort）：
将未排序部分的元素逐个插入到已排序部分的合适位置。
1package main
2
3import (
4 "fmt"
5 "math/rand"
6 "time"
7)
8
9func InsertSort(arr []int) []int {
10 if len(arr) <= 1 {
11 return arr
12 }
13
14 for i := 1; i < len(arr); i++ {
15 back := arr[i]
16 j := i - 1
17 for j >= 0 && back < arr[j] {
18 arr[j+1] = arr[j]
19 j--
20 }
21 arr[j+1] = back
22 }
23
24 return arr
25}
26
27func main() {
28 r := rand.New(rand.NewSource(time.Now().UnixNano()))
29 var list []int
30 for i := 0; i < 100; i++ {
31 list = append(list, r.Intn(100))
32 }
33 fmt.Println(InsertSort(list))
34}
插入排序的基本思想是将一个记录插入到已排序好的有序表中，从而得到一个新且记录数增1的有序表。即，先将序列的第一个记录看成是一个有序的子序列，然后从第二个记录逐个进行插入，直至整个序列有序为止。这段代码中，使用了哨兵来作为临时存储和判断数组边界的工具。
4. 希尔排序（Shell Sort）：
基于插入排序，通过分组比较和交换来提高效率。希尔排序是一种改进后的插入排序，通过分组插入的方式来提高效率。
1package main
2
3import "fmt"
4
5func shellSort(arr []int) []int {
6 length := len(arr)
7 if length <= 1 {
8 return arr
9 }
10
11 // 使用希尔增量序列，这里取gap为数组长度的一半
12 for gap := length / 2; gap > 0; gap /= 2 {
13 for i := gap; i < length; i++ {
14 temp := arr[i]
15 j := i
16 for j >= gap && arr[j-gap] > temp {
17 arr[j] = arr[j-gap]
18 j -= gap
19 }
20 arr[j] = temp
21 }
22 }
23
24 return arr
25}
26
27func main() {
28 arr := []int{11, 8, 2, 5, 7, 10, 3, 6}
29 fmt.Println(shellSort(arr))
30}
希尔排序的核心思想是先将整个待排元素序列分割成若干个子序列，然后分别进行直接插入排序，最后再对全体元素进行一次直接插入排序。
5. 归并排序（Merge Sort）：
采用“分治”策略，将数组分成两半，分别排序后再合并。归并排序是一种有效的稳定排序算法，它可以对无序或相对有序的数列进行排序。
1package main
2
3import "fmt"
4
5func mergeSort(arr []int) []int {
6 if len(arr) < 2 {
7 return arr
8 }
9
10 mid := len(arr) / 2
11 left := mergeSort(arr[:mid])
12 right := mergeSort(arr[mid:])
13
14 return merge(left, right)
15}
16
17func merge(left, right []int) []int {
18 result := make([]int, 0, len(left)+len(right))
19 i, j := 0, 0
20
21 for i < len(left) && j < len(right) {
22 if left[i] < right[j] {
23 result = append(result, left[i])
24 i++
25 } else {
26 result = append(result, right[j])
27 j++
28 }
29 }
30
31 result = append(result, left[i:]...)
32 result = append(result, right[j:]...)
33
34 return result
35}
36
37func main() {
38 unsorted := []int{10, 6, 2, 1, 5, 8, 3, 4, 7, 9}
39 sorted := mergeSort(unsorted)
40 fmt.Println(sorted) // 输出：[1 2 3 4 5 6 7 8 9 10]
41}
归并排序的核心思想是先分割，再递归排序，最后合并。
6. 快速排序（Quick Sort）：
选择一个基准元素，将比它小的放在左边，比它大的放在右边，然后递归地对左右子数组排序。
1package main
2
3import "fmt"
4
5func quickSort(nums []int, p int, r int) {
6 if p >= r {
7 return
8 }
9
10 q := partition(nums, p, r)
11 quickSort(nums, p, q-1)
12 quickSort(nums, q+1, r)
13}
14
15func partition(nums []int, p int, r int) int {
16 pivot := nums[r]
17 i := p
18
19 for j := p; j < r; j++ {
20 if nums[j] < pivot {
21 nums[i], nums[j] = nums[j], nums[i]
22 i++
23 }
24 }
25
26 nums[i], nums[r] = pivot, nums[i]
27 return i
28}
29
30func main() {
31 nums := []int{4, 5, 6, 7, 8, 3, 2, 1}
32 quickSort(nums, 0, len(nums)-1)
33 fmt.Println(nums)
34}
快速排序的核心思想是选择一个基准元素，将比它小的放在左边，比它大的放在右边，然后递归地对左右子数组排序。快速排序是原地排序算法，时间复杂度为O(nlogn)，但是在某些情况下可能会退化为O(n^2)。尽管如此，它在工程实践中应用广泛，因为它的性能通常很好。
7. 堆排序（Heap Sort）：
利用二叉堆的性质，将数组构建成最大堆，然后逐步取出最大元素。
堆排序是一种高效的排序算法，它使用一个最大堆（或最小堆）对一系列数字或其他具有定义好的顺序关系的元素进行排序。
基本思想：
- 首先，构建一个最大堆（或最小堆）。
- 然后，从堆中依次弹出最大（或最小）的元素，放到输出数组中。
1package main
2
3import "fmt"
4
5// 调整堆，使其满足堆特性
6func siftDown(arr []int, root, length int) {
7 child := 2*root + 1
8 for child < length {
9 if child+1 < length && arr[child] < arr[child+1] {
10 child++
11 }
12 if arr[root] >= arr[child] {
13 break
14 }
15 arr[root], arr[child] = arr[child], arr[root]
16 root = child
17 child = 2*root + 1
18 }
19}
20
21// 堆排序
22func heapSort(arr []int) {
23 length := len(arr)
24
25 // 构建最大堆
26 for i := length/2 - 1; i >= 0; i-- {
27 siftDown(arr, i, length)
28 }
29
30 // 从堆中弹出元素放到输出数组中
31 for i := length - 1; i > 0; i-- {
32 arr[0], arr[i] = arr[i], arr[0]
33 siftDown(arr, 0, i)
34 }
35}
36
37func main() {
38 arr := []int{11, 8, 2, 5, 7, 10, 3, 6}
39 heapSort(arr)
40 fmt.Println(arr)
41}
堆排序的时间复杂度为O(nlogn)，它是原地排序算法，适用于大规模数据的排序。
8. 计数排序（Counting Sort）：
适用于非负整数的排序，统计每个元素的出现次数，然后按顺序输出。计数排序是一种稳定的线性时间排序算法，适用于有确定范围的整数数据。
基本思想：
- 首先，找出待排序数组中的最大和最小元素。
- 创建一个额外的数组
count，长度为max - min + 1，用于存储每个值出现的次数。 - 遍历待排序数组，统计每个元素出现的频率，将结果存储在
count数组中。 - 对
count数组进行累加，确保每个元素表示小于等于该元素值的元素个数。 - 创建一个与待排序数组大小相同的结果数组
sorted。 - 第二次遍历待排序数组，根据元素的值在累加计数数组中找到其在结果数组中的位置，将元素放置在正确的位置上。
1package main
2
3import (
4 "fmt"
5 "math/rand"
6 "time"
7)
8
9func countingSort(arr []int) []int {
10 if len(arr) <= 1 {
11 return arr
12 }
13
14 // 找出最大和最小元素
15 minValue, maxValue := arr[0], arr[0]
16 for _, v := range arr {
17 if v < minValue {
18 minValue = v
19 }
20 if v > maxValue {
21 maxValue = v
22 }
23 }
24
25 // 创建计数数组
26 count := make([]int, maxValue-minValue+1)
27
28 // 统计每个值出现的频率
29 for _, v := range arr {
30 count[v-minValue]++
31 }
32
33 // 累加计数数组
34 for i := 1; i < len(count); i++ {
35 count[i] += count[i-1]
36 }
37
38 // 整理结果数组
39 sorted := make([]int, len(arr))
40 for j := len(arr) - 1; j >= 0; j-- {
41 sorted[count[arr[j]-minValue]-1] = arr[j]
42 count[arr[j]-minValue]--
43 }
44
45 return sorted
46}
47
48func main() {
49 arr := []int{11, 8, 2, 5, 7, 10, 3, 6}
50 fmt.Println(countingSort(arr))
51}
9. 桶排序（Bucket Sort）：
将元素分配到不同的桶中，对每个桶内的元素进行排序，再合并。
1package main
2
3import (
4 "fmt"
5 "math/rand"
6 "time"
7)
8
9func bucketSort(arr []int) []int {
10 if len(arr) <= 1 {
11 return arr
12 }
13
14 // 找出最大和最小元素
15 minValue, maxValue := arr[0], arr[0]
16 for _, v := range arr {
17 if v < minValue {
18 minValue = v
19 }
20 if v > maxValue {
21 maxValue = v
22 }
23 }
24
25 // 创建桶
26 bucketCount := maxValue - minValue + 1
27 buckets := make([]int, bucketCount)
28
29 // 将元素放入对应的桶中
30 for _, v := range arr {
31 buckets[v-minValue]++
32 }
33
34 // 整理结果数组
35 sorted := make([]int, 0, len(arr))
36 for i, count := range buckets {
37 for j := 0; j < count; j++ {
38 sorted = append(sorted, i+minValue)
39 }
40 }
41
42 return sorted
43}
44
45func main() {
46 r := rand.New(rand.NewSource(time.Now().UnixNano()))
47 var list []int
48 for i := 0; i < 100; i++ {
49 list = append(list, r.Intn(100))
50 }
51 fmt.Println(bucketSort(list))
52}
桶排序的核心思想是将待排序的一组数均匀独立地分布在一个范围中，并将这一范围划分成几个子范围（桶）。然后基于某种映射函数，将待排序列的关键字映射到对应的桶中，最后将各个桶中的数据有序地合并起来。
10. 基数排序（Radix Sort）：
按照位数从低到高依次排序，通常用于整数排序。基数排序是一种非比较型整数排序算法，它根据数字的每一位来对元素进行排序。
基本思想：
- 首先，将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。
- 从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
1package main
2
3import (
4 "fmt"
5 "math"
6)
7
8func radixSort(nums []int) []int {
9 maxValue := maximum(nums)
10 maxLength := howManyDigits(maxValue)
11
12 for i := 0; i < maxLength; i++ {
13 buckets := make([][]int, 10)
14 for _, num := range nums {
15 digit := (num / int(math.Pow(10, float64(i)))) % 10
16 buckets[digit] = append(buckets[digit], num)
17 }
18
19 numsCopy := make([]int, 0)
20 for j := 0; j < 10; j++ {
21 numsCopy = append(numsCopy, buckets[j]...)
22 }
23 nums = numsCopy
24 }
25
26 return nums
27}
28
29func maximum(list []int) int {
30 max := 0
31 for _, num := range list {
32 if num > max {
33 max = num
34 }
35 }
36 return max
37}
38
39func howManyDigits(number int) int {
40 count := 0
41 for number != 0 {
42 number /= 10
43 count++
44 }
45 return count
46}
47
48func main() {
49 arr := []int{121, 432, 564, 23, 1, 45, 788}
50 fmt.Println(radixSort(arr))
51}
基数排序的时间复杂度为 O(nk)，其中 n 是待排序数组的长度，k 是最大元素的位数。基数排序是一种稳定的排序算法，适用于整数排序或固定长度的字符串排序。
- 原文作者：Kid
- 原文链接：https://shuanglu.life/post/20240110_golang%E6%8E%92%E5%BA%8F/
- 版权声明：本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可，非商业转载请注明出处（作者，原文链接），商业转载请联系作者获得授权。
