使用go语言实现快速排序、归并排序、插入排序、冒泡排序、选择排序

1. 冒泡排序（Bubble Sort）：

• 原理：比较相邻的元素，如果前一个比后一个大，就交换它们。这个过程会使得每一轮最大的元素“冒泡”到数组的末尾。
• 时间复杂度：O(n^2)
• 稳定性：稳定

// BubbleSort 函数使用冒泡排序算法对数组进行排序
func BubbleSort(arr []int) {
	n := len(arr)
	for i := 0; i < n; i++ {
		for j := 0; j < n-i-1; j++ {
			if arr[j] > arr[j+1] {
				// 交换 arr[j] 和 arr[j+1]
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
	}
}

2. 选择排序（Selection Sort）：

• 原理：从未排序的部分中选出最小的元素，将其放在已排序部分的末尾。
• 时间复杂度：O(n^2)
• 稳定性：不稳定

// SelectionSort 函数使用选择排序算法对数组进行排序
func SelectionSort(arr []int) {
   n := len(arr)
   for i := 0; i < n-1; i++ {
      // 找到未排序部分中最小的元素
      minIdx := i
      for j := i + 1; j < n; j++ {
         if arr[j] < arr[minIdx] {
            minIdx = j
         }
      }
      // 将找到的最小元素与未排序部分的第一个元素交换
      arr[i], arr[minIdx] = arr[minIdx], arr[i]
   }
}

3. 插入排序（Insertion Sort）：

• 原理：每次将一个新的元素插入到已排序部分的正确位置。
• 时间复杂度：O(n^2)
• 稳定性：稳定

// InsertionSort 函数使用插入排序算法对数组进行排序
func InsertionSort(arr []int) {
	n := len(arr)
	for i := 1; i < n; i++ {
		key := arr[i]
		j := i - 1

        // 移动 arr[0..i-1] 中大于 key 的元素到当前元素的下一个位置
		for j >= 0 && arr[j] > key {
			arr[j+1] = arr[j]
			j = j - 1
		}
		arr[j+1] = key
	}
}

4. 快速排序（Quick Sort）：

• 原理：选择一个基准元素，将数组划分为两个子数组，使得一个子数组中的所有元素都比基准元素小，另一个子数组中的所有元素都比基准元素大，然后递归地排序这两个子数组。
• 时间复杂度：平均O(n log n)，最坏O(n^2)
• 稳定性：不稳定

// QuickSort 函数使用快速排序算法对数组进行排序
func QuickSort(arr []int, low, high int) {
	if low < high {
		// pi 是分区索引，arr[pi] 现在位于正确的位置
		pi := partition(arr, low, high)

		// 递归地对分区索引前后的元素进行排序
		QuickSort(arr, low, pi-1)
		QuickSort(arr, pi+1, high)
	}
}

// partition 函数以最后一个元素为基准，将基准元素放置在其正确的位置，
// 并将所有小于基准的元素移到基准的左边，大于基准的元素移到基准的右边
func partition(arr []int, low, high int) int {
	pivot := arr[high] // 选择最后一个元素作为基准
	i := low - 1       // 较小元素的索引

	for j := low; j < high; j++ {
		// 如果当前元素小于或等于基准
		if arr[j] <= pivot {
			i++ // 增加较小元素的索引
			// 交换 arr[i] 和 arr[j]
			arr[i], arr[j] = arr[j], arr[i]
		}
	}
	// 交换 arr[i+1] 和 arr[high] (基准)
	arr[i+1], arr[high] = arr[high], arr[i+1]

	return i + 1
}

5. 归并排序（Merge Sort）：

• 原理：将数组分成两个子数组，分别排序后再合并。
• 时间复杂度：O(n log n)
• 稳定性：稳定

// MergeSort 函数使用归并排序算法对数组进行排序
func MergeSort(arr []int) []int {
	if len(arr) <= 1 {
		return arr
	}

	// 将数组分成两半
	mid := len(arr) / 2
	left := MergeSort(arr[:mid])
	right := MergeSort(arr[mid:])

	// 合并两个有序的子数组
	return merge(left, right)
}

// merge 函数合并两个有序的子数组
func merge(left, right []int) []int {
	var result []int
	i, j := 0, 0

	// 合并两个子数组
	for i < len(left) && j < len(right) {
		if left[i] < right[j] {
			result = append(result, left[i])
			i++
		} else {
			result = append(result, right[j])
			j++
		}
	}

	// 将剩余的元素添加到结果数组中
	for i < len(left) {
		result = append(result, left[i])
		i++
	}
	for j < len(right) {
		result = append(result, right[j])
		j++
	}

	return result
}