快排golang实现

快速排序的实现

快速排序是一种常用的排序算法，其基本思想是选择一个基准元素，通过一趟排序将待排序的元素分割成独立的两部分，其中一部分的所有元素都比基准元素小，另一部分的所有元素都比基准元素大，然后再按照此方法对这两部分分别进行快速排序，整个排序过程可以递归进行。

下面是使用Golang实现快速排序的代码：

```go package main import "fmt" func quickSort(arr []int, low, high int) { if low < high { pivot := partition(arr, low, high) quickSort(arr, low, pivot-1) quickSort(arr, pivot+1, high) } } 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[j], arr[i] } } arr[i+1], arr[high] = arr[high], arr[i+1] return i + 1 } func main() { arr := []int{64, 34, 25, 12, 22, 11, 90} n := len(arr) quickSort(arr, 0, n-1) fmt.Println("排序后的数组：") for i := 0; i < n; i++ { fmt.Printf("%d ", arr[i]) } } ```

上述代码中，`quickSort`函数用来递归地进行快速排序。它接收一个待排序数组`arr`和其实位置`low`、结束位置`high`作为参数。

在`quickSort`函数内部，我们首先通过调用`partition`函数找到基准元素的正确位置，并返回此位置。

`partition`函数使用了双指针法来进行元素的交换。通过遍历数组中的元素，将小于基准元素的元素放到左边，大于基准元素的元素放到右边。最后将基准元素放在正确的位置上。

在`main`函数中，我们定义一个测试数组并调用`quickSort`函数来对其进行排序。最后打印排序后的结果。

由于快速排序采用了分治的思想，因此其时间复杂度为O(nlogn)，是一种高效的排序算法。然而，在最坏的情况下，快速排序的时间复杂度会退化为O(n^2)。因此在实际应用中，我们可以选择随机选择基准元素来避免最坏情况的发生。

总之，快速排序是一种高效的排序算法，适用于各种规模的数据集。通过合理地选择基准元素和优化算法，我们可以进一步提高快速排序的性能。