Go：深入解析快速排序及其实现

运维开发王义杰

发布于 2024-04-25 15:08:15

1240

发布于 2024-04-25 15:08:15

引言

快速排序是由C. A. R. Hoare在1960年提出的一种高效的排序算法，它也是最常用的排序算法之一。快速排序的主要优势在于它的平均时间复杂度为O(n log n)，并且它的分治法本质让它在处理大数据集时表现出色。在本文中，我们将详细探讨快速排序的原理，并使用Go语言实现一个快速排序函数。

快速排序算法原理

快速排序的核心思想是分治法（Divide and Conquer）。具体步骤如下：

选择基准值：从数列中挑出一个元素，称为“基准”（pivot）。
分区操作：重新排列数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
递归排序：递归地（recursive）将小于基准值的子数列和大于基准值的子数列排序。

图解快速排序

为了更好地理解快速排序，我们可以将其分解为以下步骤：

选择基准
分区操作，将比基准小的移至左边，比基准大的移至右边
对左右子序列递归执行上述操作

Go语言实现快速排序

Go语言以其简洁和高效著称，是实现系统级程序的理想选择。下面是一个快速排序的Go语言实现示例：


go
package main

import (
	"fmt"
)

// quickSort 快速排序函数
func quickSort(arr []int) []int {
	if len(arr) < 2 {
		return arr
	}
	left, right := 0, len(arr)-1
	// 选择中间点作为基准
	pivot := arr[(left+right)/2]
	
	// 分区操作
	for left <= right {
		for arr[left] < pivot {
			left++
		}
		for arr[right] > pivot {
			right--
		}
		if left <= right {
			arr[left], arr[right] = arr[right], arr[left]
			left++
			right--
		}
	}
	
	// 递归排序子序列
	if 0 < right {
		arr[:right+1] = quickSort(arr[:right+1])
	}
	if left < len(arr) {
		arr[left:] = quickSort(arr[left:])
	}
	return arr
}

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