golang快速排序算法（golang实现快速排序）

## Golang 快速排序算法### 简介快速排序（Quicksort）是一种高效的排序算法，其基本思想是分治法。它选择一个基准元素，将数组分成两个子数组，小于基准元素的元素放在左边，大于基准元素的元素放在右边，然后递归地对子数组进行排序，最终得到有序数组。 ### 算法步骤1.

选择基准元素：

可以选择数组的第一个元素、最后一个元素、中间元素或者随机选择一个元素作为基准元素。2.

分区：

将数组分成两个子数组，小于基准元素的元素放在左边，大于基准元素的元素放在右边。3.

递归排序：

对左右两个子数组分别递归地进行快速排序。### Golang 实现```go package mainimport "fmt"func quickSort(arr []int, low, high int) {if low < high {// 分区pivotIndex := partition(arr, low, high)// 递归排序左右子数组quickSort(arr, low, pivotIndex-1)quickSort(arr, pivotIndex+1, high)} }func partition(arr []int, low, high int) int {// 选择最后一个元素作为基准元素pivot := arr[high]i := low - 1for 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{10, 7, 8, 9, 1, 5}fmt.Println("排序前：", arr)quickSort(arr, 0, len(arr)-1)fmt.Println("排序后：", arr) } ```### 代码解释

`quickSort()` 函数：

- 接收三个参数：待排序数组 `arr`，起始索引 `low`，结束索引 `high`。- 使用 `partition()` 函数进行分区，并获取基准元素的索引 `pivotIndex`。- 递归调用 `quickSort()` 函数对左右子数组进行排序。

`partition()` 函数：

- 选择最后一个元素作为基准元素 `pivot`。- 使用两个指针 `i` 和 `j`，`i` 指向小于等于基准元素的最后一个元素的位置，`j` 遍历数组。- 如果 `arr[j] <= pivot`，则将 `i` 加一，并将 `arr[i]` 和 `arr[j]` 交换位置，保证小于等于基准元素的元素都在左边。- 最后将基准元素 `pivot` 放到正确的位置，即 `i+1` 处。- 返回基准元素的索引 `i+1`。### 复杂度分析

时间复杂度：

- 最佳情况：O(n log n)，每次分区都将数组分成大小相等的两个子数组。- 平均情况：O(n log n)- 最坏情况：O(n^2)，当数组已经有序或逆序时，每次分区都会将数组分成一个大小为 n-1 的子数组和一个大小为 1 的子数组。

空间复杂度：

O(log n)，递归调用栈的空间。### 总结快速排序是一种高效的排序算法，平均时间复杂度为 O(n log n)，但最坏情况下时间复杂度为 O(n^2)。在实际应用中，快速排序的性能通常优于其他 O(n log n) 复杂度的排序算法，例如归并排序和堆排序。

Golang 快速排序算法

简介快速排序（Quicksort）是一种高效的排序算法，其基本思想是分治法。它选择一个基准元素，将数组分成两个子数组，小于基准元素的元素放在左边，大于基准元素的元素放在右边，然后递归地对子数组进行排序，最终得到有序数组。

算法步骤1. **选择基准元素：** 可以选择数组的第一个元素、最后一个元素、中间元素或者随机选择一个元素作为基准元素。2. **分区：** 将数组分成两个子数组，小于基准元素的元素放在左边，大于基准元素的元素放在右边。3. **递归排序：** 对左右两个子数组分别递归地进行快速排序。

Golang 实现```go package mainimport "fmt"func quickSort(arr []int, low, high int) {if low < high {// 分区pivotIndex := partition(arr, low, high)// 递归排序左右子数组quickSort(arr, low, pivotIndex-1)quickSort(arr, pivotIndex+1, high)} }func partition(arr []int, low, high int) int {// 选择最后一个元素作为基准元素pivot := arr[high]i := low - 1for 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{10, 7, 8, 9, 1, 5}fmt.Println("排序前：", arr)quickSort(arr, 0, len(arr)-1)fmt.Println("排序后：", arr) } ```

代码解释* **`quickSort()` 函数：** - 接收三个参数：待排序数组 `arr`，起始索引 `low`，结束索引 `high`。- 使用 `partition()` 函数进行分区，并获取基准元素的索引 `pivotIndex`。- 递归调用 `quickSort()` 函数对左右子数组进行排序。* **`partition()` 函数：** - 选择最后一个元素作为基准元素 `pivot`。- 使用两个指针 `i` 和 `j`，`i` 指向小于等于基准元素的最后一个元素的位置，`j` 遍历数组。- 如果 `arr[j] <= pivot`，则将 `i` 加一，并将 `arr[i]` 和 `arr[j]` 交换位置，保证小于等于基准元素的元素都在左边。- 最后将基准元素 `pivot` 放到正确的位置，即 `i+1` 处。- 返回基准元素的索引 `i+1`。

复杂度分析* **时间复杂度：** - 最佳情况：O(n log n)，每次分区都将数组分成大小相等的两个子数组。- 平均情况：O(n log n)- 最坏情况：O(n^2)，当数组已经有序或逆序时，每次分区都会将数组分成一个大小为 n-1 的子数组和一个大小为 1 的子数组。 * **空间复杂度：** O(log n)，递归调用栈的空间。

总结快速排序是一种高效的排序算法，平均时间复杂度为 O(n log n)，但最坏情况下时间复杂度为 O(n^2)。在实际应用中，快速排序的性能通常优于其他 O(n log n) 复杂度的排序算法，例如归并排序和堆排序。