Golang 双指针快速排序的代码实现

在 Go 语言中，快速排序是一种高效的排序算法。双指针快速排序通过巧妙地运用两个指针，能够在平均情况下实现 O(n log n) 的时间复杂度，在最坏情况下为 O(n^2)。下面我们来详细了解其代码实现。

package main

import "fmt"

// 交换函数
func swap(arr []int, i int, j int) {
	arr[i], arr[j] = arr[j], arr[i]
}

// 划分函数，选择一个基准元素，将小于基准的元素放在左边，大于基准的元素放在右边
func partition(arr []int, low int, high int) int {
	pivot := arr[high]
	i := low - 1

	for j := low; j <= high-1; j++ {
		if arr[j] <= pivot {
			i++
			swap(arr, i, j)
		}
	}
	swap(arr, i+1, high)
	return (i + 1)
}

// 快速排序函数
func quickSort(arr []int, low int, high int) {
	if low < high {
		p := partition(arr, low, high)

		quickSort(arr, low, p-1)
		quickSort(arr, p+1, high)
	}
}

// 打印数组函数
func printArray(arr []int, size int) {
	for i := 0; i < size; i++ {
		fmt.Printf("%d ", arr[i])
	}
	fmt.Println()
}

func main() {
	arr := []int{12, 11, 13, 5, 6}
	n := len(arr)

	fmt.Print("排序前的数组为: ")
	printArray(arr, n)

	quickSort(arr, 0, n-1)

	fmt.Print("排序后的数组为: ")
	printArray(arr, n)
}

在上述代码中，我们首先定义了一个swap函数用于交换数组中的元素。partition函数用于选择基准元素并进行划分操作。quickSort函数则是整个快速排序的核心，通过递归地对划分后的子数组进行排序，最终实现整个数组的排序。

在main函数中，我们创建了一个待排序的数组，并输出排序前后数组的元素。

快速排序的优点在于其平均性能出色，空间复杂度也相对较低。但在最坏情况下，可能会出现性能退化。通过合理地选择基准元素，或者采用随机化的方式，可以有效地避免最坏情况的发生。

双指针快速排序在处理大规模数据时表现出色，是 Go 语言中常用的排序算法之一。熟练掌握其原理和实现，对于提高编程能力和解决实际问题具有重要意义。