常见排序算法

本文介绍: 冒泡排序冒泡排序（BubbleSort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。作为最简单的排序算法之一，冒泡排序给我的感觉就像Abandon在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。冒泡排序还有一种优化算法，就是立一个flag，当在一趟序列遍历中元素没有发生交换，

选择排序
选择排序是一种简单直观的排序算法，无论什么数据进去都是O(n²)的时间复
杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额
外的内存空间了吧。
1.算法步骤
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的
末尾。
重复第二步，直到所有元素均排序完毕。

func selectionSort(arr []int) []int {
    l := len(arr)
    if l == 0 {
        return arr
    }
    for i := 0; i < l; i++ {
        min := i
        for j := i + 1; j < l; j++ {
            if arr[j] < arr[min] {
                min = j
            }
        }
        arr[i], arr[min] = arr[min], arr[i]
    }
    return arr
}

冒泡排序
冒泡排序（BubbleSort）也是一种简单直观的排序算法。它重复地走访过要
排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走
访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完
成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶
端。
作为最简单的排序算法之一，冒泡排序给我的感觉就像Abandon在单词书里
出现的感觉一样，每次都在第一页第一位，所以最熟悉。冒泡排序还有一种优
化算法，就是立一个flag，当在一趟序列遍历中元素没有发生交换，则证明该
序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。
1.算法步骤
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完
后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比
较。

func bubbleSort(arr []int) []int {
    if len(arr) == 0 {
        return arr
    }
    for i := 0; i < len(arr); i++ {
        for j := 0; j < len(arr); j++ {
            if arr[i] > arr[j] {
                arr[j], arr[i] = arr[i], arr[j]
            }
        }
    }
    return arr
}

go 实现二叉树输出每1层右边的节点

为了输出二叉树每一层最右边的节点（右视图），可以使用广度优先搜索（BFS）算法。以下是Go语言实现该功能的代码示例：

1package main
2
3import (
4	"fmt"
5)
6
7// 定义二叉树节点结构体
8type TreeNode struct {
9	Val   int
10	Left  *TreeNode
11	Right *TreeNode
12}
13
14// 新建一个二叉树节点
15func NewTreeNode(val int) *TreeNode {
16	return &TreeNode{Val: val, Left: nil, Right: nil}
17}
18
19// 输出二叉树每层最右边的节点
20func rightView(root *TreeNode) []int {
21	if root == nil {
22		return []int{}
23	}
24
25	queue := []*TreeNode{root}
26	result := []int{}
27
28	for len(queue) > 0 {
29		levelSize := len(queue)
30		lastNodeOfThisLevel := queue[levelSize-1]
31
32		for i := 0; i < levelSize; i++ {
33			node := queue[0]
34			queue = queue[1:]
35
36			// 当遍历到当前层最后一个节点时，将其值添加到结果中
37			if i == levelSize-1 {
38				result = append(result, node.Val)
39			}
40
41			if node.Left != nil {
42				queue = append(queue, node.Left)
43			}
44			if node.Right != nil {
45				queue = append(queue, node.Right)
46			}
47		}
48	}
49
50	return result
51}
52
53func main() {
54	// 创建示例二叉树
55	root := NewTreeNode(1)
56	root.Left = NewTreeNode(2)
57	root.Right = NewTreeNode(3)
58	root.Left.Left = NewTreeNode(4)
59	root.Left.Right = NewTreeNode(5)
60
61	// 输出右视图
62	fmt.Println(rightView(root)) // 应输出：[1, 3, 5]
63}

这段代码首先定义了一个TreeNode结构体表示二叉树节点，并创建了一个辅助函数rightView来实现输出右视图的功能。在该函数中，我们使用队列进行层次遍历，在遍历过程中，每当处理完一层的所有节点后，都将这一层最右侧节点的值存入结果数组中。最后返回的结果数组就是二叉树的右视图。

数据结构：常用排序算法，快排、堆排的原理和实现。 go

快速排序（QuickSort）

快速排序是一种高效的基于分治策略的比较排序算法。在Go语言中，我们可以这样实现快速排序：

1package main
2
3import (
4	"fmt"
5)
6
7func quickSort(arr []int, low int, high int) {
8	if low < high {
9		pivotIndex := partition(arr, low, high)
10		quickSort(arr, low, pivotIndex-1)
11		quickSort(arr, pivotIndex+1, high)
12	}
13}
14
15func partition(arr []int, low int, high int) int {
16	pivot := arr[high]
17	i := (low - 1)
18	for j := low; j < high; j++ {
19		if arr[j] <= pivot {
20			i++
21			arr[i], arr[j] = arr[j], arr[i]
22		}
23	}
24	arr[i+1], arr[high] = arr[high], arr[i+1]
25	return i + 1
26}
27
28func main() {
29	arr := []int{9, 7, 5, 11, 12, 2, 14, 3, 10, 6}
30	n := len(arr)
31	quickSort(arr, 0, n-1)
32	fmt.Println("Sorted array:", arr)
33}

原理：

选择基准元素：选取数组中的一个元素作为基准值，这里我们使用数组末尾的元素。
分区操作：从数组的第一个元素开始遍历，将小于等于基准值的元素与基准值之前的元素交换位置，使得基准值左侧的所有元素都小于它，右侧则可能有大于它的元素。这个过程结束后，基准值会处于最终正确的位置上。
递归排序子数组：对基准值左右两侧的子数组分别进行同样的快速排序。

堆排序（HeapSort）

堆排序是利用了完全二叉树的堆数据结构特性的一种排序方法，在Go语言中可以这样实现：

1package main
2
3import (
4	"fmt"
5)
6
7// 建堆函数
8func heapify(arr []int, n int, i int) {
9	largest := i // 初始化最大值为当前节点i
10	left := 2*i + 1
11	right := 2*i + 2
12
13	// 如果左孩子存在并且比当前节点大，则更新最大值
14	if left < n && arr[left] > arr[largest] {
15		largest = left
16	}
17
18	// 如果右孩子存在并且比当前节点和左孩子都大，则更新最大值
19	if right < n && arr[right] > arr[largest] {
20		largest = right
21	}
22
23	// 如果最大值不是当前节点，交换它们并继续向下调整堆
24	if largest != i {
25		arr[i], arr[largest] = arr[largest], arr[i]
26		heapify(arr, n, largest)
27	}
28}
29
30// 堆排序主函数
31func heapSort(arr []int) {
32	n := len(arr)
33
34	// 构建大顶堆
35	for i := n/2 - 1; i >= 0; i-- {
36		heapify(arr, n, i)
37	}
38
39	// 依次取出堆顶元素（即当前未排序序列的最大值），将其与末尾元素交换，并重新调整堆
40	for i := n - 1; i > 0; i-- {
41		arr[i], arr[0] = arr[0], arr[i] // 交换堆顶元素与末尾元素
42		heapify(arr, i, 0)             // 调整剩余部分为大顶堆
43	}
44}
45
46func main() {
47	arr := []int{9, 7, 5, 11, 12, 2, 14, 3, 10, 6}
48	heapSort(arr)
49	fmt.Println("Sorted array:", arr)
50}

原理：

构建堆：首先将给定无序数组构造成一个大顶堆（或小顶堆），保证父节点的值总是大于（或小于）其子节点的值。
堆调整：每次将堆顶元素（即当前未排序序列的最大值或最小值）与最后一个元素交换位置，然后去掉已排序区，对剩下的元素重新调整为堆结构。
重复步骤2：直到整个序列有序

B树（B-Tree）和B+树（B+Tree）都是平衡多路搜索树，主要用于数据库和文件系统中索引结构的设计。它们有相似之处，但也存在一些关键区别：

B树(B-Tree)：

节点存储数据：每个内部节点除了包含指向子节点的指针外，还存储着键值和关联的数据项。这意味着在非叶子节点也可以查询到部分数据。
键与子节点关系：每个节点可以有多个键，并且这些键将节点划分为多个区间，每个区间对应一个子节点。
数据分布：数据分布在所有节点上，包括根、中间节点以及叶子节点。

B+树(B+Tree)：

节点不直接存储数据：内部节点（非叶子节点）只存储键而不存储实际的数据项，仅起到索引作用；所有的数据都存储在叶子节点上。
叶子节点间链接：所有叶子节点在层次结构的最底层形成一个连续的链表，便于范围查询时能快速遍历。
键与子节点关系：与B树类似，每个节点同样包含多个键和对应的子节点指针，但这里的所有键都在叶子节点上有对应的值。
数据查询效率：对于点查询，虽然需要经过多个内部节点，但由于内部节点是密集索引，通常比B树查找更稳定高效；而由于叶子节点之间通过指针连接，对范围查询尤其高效，只需从左边界叶子节点开始一直遍历到右边界即可。

总结来说，B+树相比B树更适合磁盘等外部存储设备上的大数据量访问场景，原因在于：

综上所述，处理亿级数据的关键在于合理设计底层存储结构、优化索引策略、采取合适的硬件配置以及利用现代数据处理技术进行高效管理和分析。

B+树全量数据集中存储于叶子节点，有利于顺序I/O操作，减少磁盘寻道时间；
叶子节点间的链表使得范围查询无需回溯至父节点，大大提高了查询效率。
如果是亿级数据怎么处理？

处理亿级数据时，传统的内存数据结构和算法往往无法满足性能要求，因为如此大规模的数据不可能全部加载到内存中进行高效处理。此时，B+树等磁盘友好型索引结构就显得至关重要。

对于数据库系统或文件系统中的亿级数据：
使用B+树作为索引结构：由于B+树的高度较低且每个节点可以包含大量键值，能够实现较大的扇出（即一个节点可以有多个子节点），从而使得查找、插入和删除操作在磁盘I/O方面的效率较高。叶子节点的顺序存储特性也特别适合于磁盘预读（一次磁盘读取会获取连续的多个数据块）机制，有利于范围查询。
分区分页管理：将大表物理上分成若干个区或页，只将部分经常访问或即将访问的数据缓存到内存中（如操作系统缓存或数据库缓冲池），通过合理的缓存策略来减少磁盘访问。
分区与分布式存储：将数据进一步水平分割成多个分区，甚至采用分布式数据库架构，在多台服务器上分别存储和管理数据，每台服务器上的数据量相对较小，可以提升整体处理能力，并提供水平扩展性。
列式存储与压缩：针对大数据分析场景，可能还会采用列式存储而非行式存储，这样只需要读取需要分析的那些列，同时配合高效的压缩算法，可以显著降低存储空间占用和I/O负载。
索引优化：对查询频繁的字段建立索引，尤其是选择性高的字段；根据查询模式调整索引结构和类型，比如组合索引、覆盖索引等。
批处理与流处理：对于批量数据处理任务，可以利用批处理框架，例如Hadoop MapReduce或Spark；对于实时或近实时的处理需求，则可考虑流处理框架如Flink或Kafka Streams。