排序算法

冒泡排序

• 思想：将相邻的元素两两比较，根据大小关系交换位置，每轮循环将最大（或最小）的元素浮动到最后。
• 优点：实现简单，适用于小规模数据。
• 缺点：时间复杂度为O(n^2)，效率较低。

插入排序

• 思想：将数组分为已排序部分和未排序部分，每次取未排序部分的第一个元素插入到已排序部分的合适位置。
• 优点：对部分有序或小规模数据效率较高。
• 缺点：对大规模乱序数据排序效率较低，时间复杂度为O(n^2)。

package main  

import (  
	"fmt"  
)  

// insertionSort 对数组进行插入排序  
func insertionSort(arr []int) {  
	n := len(arr)  
	for i := 1; i < n; i++ {  
		key := arr[i]       // 当前待插入的元素  
		j := i - 1          // 移动范围指针  

		// 向后移动已排序部分，使其为插入留出位置  
		for j >= 0 && arr[j] > key {  
			arr[j+1] = arr[j]  
			j--  
		}  
		arr[j+1] = key // 插入当前元素到正确位置  
	}  
}  

func main() {  
	arr := []int{9, 3, 7, 4, 6, 1, 8, 5, 2}  
	insertionSort(arr)  
	fmt.Println("Sorted array:", arr)  
}

选择排序

• 思想：每次在未排序部分选择最小（或最大）的元素，放到已排序的末尾。
• 优点：实现简单，不占用额外空间。
• 缺点：时间复杂度为O(n^2)，不稳定。不适用于大规模数据。

快速排序

• 思想：选择一个基准元素，将小于基准的元素放在左边，大于基准的元素放在右边，然后递归对左右两部分进行排序。
• 优点：时间复杂度平均为O(nlogn)，效率高，适用于大规模数据。原地排序，空间复杂度O(n)
• 缺点：最坏情况下时间复杂度为O(n^2)。不稳定.

package main  

import (  
	"fmt"  
)  

// quickSort 实现快速排序  
func quickSort(arr []int) []int {  
	if len(arr) < 2 {  
		return arr // 基线条件：长度小于2时直接返回  
	}  
	  
	// 选取基准值  
	pivot := arr[0]  
	var left, right []int  

	// 分区操作  
	for _, v := range arr[1:] {  
		if v < pivot {  
			left = append(left, v) // 小于基准值放入左侧  
		} else {  
			right = append(right, v) // 大于或等于基准值放入右侧  
		}  
	}  

	// 递归调用并合并结果  
	return append(append(quickSort(left), pivot), quickSort(right)...)  
}  

func main() {  
	arr := []int{9, 3, 7, 4, 6, 1, 8, 5, 2}  
	sortedArr := quickSort(arr)  
	fmt.Println("Sorted array:", sortedArr)  
}

归并排序

• 思想：采用分治法，将数组划分为子数组直到每个子数组只有一个元素，然后合并相邻的子数组并排序。
• 优点：时间复杂度为O(nlogn)，稳定且适用于大规模数据。使用于链表，稳定排序
• 缺点：需要额外的空间来存储临时数组。非原地排序

package main  

import (  
	"fmt"  
)  

// merge 合并两个已排序的切片  
func merge(left, right []int) []int {  
	merged := []int{}  
	i, j := 0, 0  

	// 比较并合并两个切片  
	for i < len(left) && j < len(right) {  
		if left[i] < right[j] {  
			merged = append(merged, left[i])  
			i++  
		} else {  
			merged = append(merged, right[j])  
			j++  
		}  
	}  

	// 将剩余元素添加到合并后的切片  
	for i < len(left) {  
		merged = append(merged, left[i])  
		i++  
	}  
	for j < len(right) {  
		merged = append(merged, right[j])  
		j++  
	}  

	return merged  
}  

// mergeSort 实现归并排序  
func mergeSort(arr []int) []int {  
	if len(arr) < 2 {  
		return arr // 基线条件：长度小于2时直接返回  
	}  

	mid := len(arr) / 2  
	left := mergeSort(arr[:mid])   // 左半部分排序  
	right := mergeSort(arr[mid:]) // 右半部分排序  

	return merge(left, right) // 合并已排序的左半部分和右半部分  
}  

func main() {  
	arr := []int{9, 3, 7, 4, 6, 1, 8, 5, 2}  
	sortedArr := mergeSort(arr)  
	fmt.Println("Sorted array:", sortedArr)  
}

堆排序

• 思想：利用最大堆或最小堆的性质实现排序，首先构建堆，然后逐步将堆顶元素与堆尾元素交换并调整堆。
• 优点：时间复杂度为O(nlogn)，原地排序算法。
• 缺点：不稳定，且实现较为复杂。

package main  

import (  
	"fmt"  
)  

// heapify 将一个子树调整为最大堆  
func heapify(arr []int, n int, i int) {  
	largest := i      // 初始化父节点为最大值  
	left := 2*i + 1   // 左子节点索引  
	right := 2*i + 2  // 右子节点索引  

	// 如果左子节点存在且大于父节点  
	if left < n && arr[left] > arr[largest] {  
		largest = left  
	}  

	// 如果右子节点存在且大于当前最大值  
	if right < n && arr[right] > arr[largest] {  
		largest = right  
	}  

	// 如果最大值不是父节点  
	if largest != i {  
		arr[i], arr[largest] = arr[largest], arr[i] // 交换  

		// 递归将子树调整为最大堆  
		heapify(arr, n, largest)  
	}  
}  

// heapSort 对数组进行堆排序  
func heapSort(arr []int) {  
	n := len(arr)  

	// 建立最大堆  
	for i := n/2 - 1; i >= 0; i-- {  
		heapify(arr, n, i)  
	}  

	// 从根节点（最大值）开始，逐个将较大值放到数组的末尾  
	for i := n - 1; i > 0; i-- {  
		arr[0], arr[i] = arr[i], arr[0] // 交换根节点和当前末尾元素  
		heapify(arr, i, 0)              // 调整堆结构  
	}  
}  

func main() {  
	arr := []int{9, 3, 7, 4, 6, 1, 8, 5, 2}  
	heapSort(arr)  
	fmt.Println("Sorted array:", arr)  
}

桶排序

思想：将原始数据分散到若干个有序的桶中，然后对每个桶中的数据进行排序，最后按照顺序合并所有桶的数据，得到排序好的结果。 优点：

1. 桶排序是一种非比较排序算法，时间复杂度可以优化到线性时间复杂度O(n)。
2. 适用于大量数据且数据分布均匀的情况下，可以获得较好的排序性能。
3. 可以通过调整桶的数量来平衡时间和空间复杂度。

缺点：

1. 如果数据分布不均匀，可能会导致某些桶的数据量很大，需要额外的排序算法进行排序操作，降低了排序效率。
2. 需要额外的空间来存储桶，当数据量很大时，可能会占用较多的内存空间。
3. 对于数据量较小且数据分布不均匀的情况，桶排序的性能可能不如其他排序算法。

计数排序

思想：最大数字，记为 m ，然后创建一个长度为 m+1 的辅助数组 counter, 统计每个数字的出现次数即可 优点：

1. 时间复杂度为O(n+k)，其中n为待排序元素的个数，k为元素的取值范围。可以达到线性时间复杂度。
2. 稳定的排序算法，相同元素的相对位置不会改变。
3. 对于重复元素较多的情况，计数排序可以有效减少比较操作的次数。

缺点：

1. 需要额外的空间来存储计数数组，当元素的取值范围较大时，可能会消耗大量的内存空间。
2. 只适用于数据量大、元素范围较小、非负整数的排序，不适用于包含负数或浮点数的情况。
3. 当元素取值范围较大时，计数排序的时间复杂度会增加，并且可能会导致空间复杂度较高。

基数排序

思想：核心思想与计数排序一致，也通过统计个数来实现排序。在此基础上，基数排序利用数字各位之间的递进关系，依次对每一位进行排序，从而得到最终的排序结果。 优点：与技术排序相比，数排序适用于数值范围较大的情况 缺点：

1. 前提是数据必须可以表示为固定位数的格式，且位数不能过大
2. 当计数排序稳定时，基数排序也稳定；当计数排序不稳定时，基数排序无法保证得到正确的排序结果
3. 非原地排序：与计数排序相同，基数排序需要借助长度为 n 和 d 的数组 res 和 counter 。