go 快速排序算法

218次阅读

共计 832 个字符,预计需要花费 3 分钟才能阅读完成。

概念
快速排序的基本思想是从待排序序列中选择一个元素作为枢轴,然后将数组分成两部分,一部分包含小于枢轴的所有元素,另一部分包含大于枢轴的所有元素。接下来,将两个子数组递归地进行排序,直到整个数组都被排序。

让我们看一下 Go 语言中的快速排序实现。

代码实现
package main

import "fmt"

func quickSort(arr []int) {
if len(arr) <= 1 {
return
}
lt, i, gt := 0, 0, len(arr)-1
pivot := arr[0]
for i <= gt {
if arr[i] < pivot {
arr[i], arr[lt] = arr[lt], arr[i]
i++
lt++
} else if arr[i] > pivot {
arr[i], arr[gt] = arr[gt], arr[i]
gt--
} else {
i++
}
}
quickSort(arr[:lt])
quickSort(arr[gt+1:])
}

func main() {
arr := []int{5, 4, 7, 8, 9, 2}
quickSort(arr)
fmt.Println(arr)
}

在上面的代码中,我们首先检查数组的长度是否小于等于 1。如果是,我们直接返回。否则,我们使用指针 lt、i 和 gt 来遍历数组,并将数组划分为小于、等于和大于枢轴的三个部分。最后,我们递归地对小于枢轴和大于枢轴的两个子数组进行排序。

算法分析
时间复杂度分析
在最坏的情况下,每次我们将数组分成两部分时,其中一部分的大小为 0,而另一部分的大小为原始数组的大小减 1。因此,在这种情况下,快速排序的时间复杂度为 O(n^2)。然而,在平均情况下,每次我们将数组分成两部分时,它们的大小大致相等。因此,快速排序的时间复杂度为 O(nlogn)。

空间复杂度分析
这个实现使用了递归来排序数组,因此在堆栈中会有多个函数调用。每次递归调用会产生新的堆栈帧,因此空间复杂度为 O(logn)。然而,在这个实现中,我们使用了原地交换来减少递归调用的深度,因此实际上的空间复杂度为 O(1)。

正文完
 
dkp
版权声明:本站原创文章,由 dkp 2023-04-10发表,共计832字。
转载说明:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。