算法 - (排序)

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析。

快速排序

package main

import (
	"fmt"
)

// quickSort 是快速排序的主函数
// arr: 待排序的整数切片
// low: 当前子切片的起始索引
// high: 当前子切片的结束索引
func quickSort(arr []int, low, high int) {
	// 递归终止条件：如果子切片的起始索引大于或等于结束索引，说明只有一个元素或空切片，无需排序
	if low < high {
		// partition 函数返回枢轴元素最终的索引
		pivotIndex := partition(arr, low, high)

		// 递归地对枢轴左边的子切片进行快速排序
		quickSort(arr, low, pivotIndex-1)
		// 递归地对枢轴右边的子切片进行快速排序
		quickSort(arr, pivotIndex+1, high)
	}
}

// partition 是快速排序的核心辅助函数，用于将切片划分为两部分
// 以第一个元素为枢轴，将小于枢轴的元素放到左边，大于枢轴的元素放到右边
// arr: 待排序的整数切片
// low: 当前子切片的起始索引
// high: 当前子切片的结束索引
// 返回值: 枢轴元素最终的索引
func partition(arr []int, low, high int) int {
	// 枢轴元素，选择子切片的第一个元素作为枢轴
	pivot := arr[low]
	// storeIndex 指针用于标记小于枢轴区域的最后一个元素的下一个位置
	// 初始时，所有元素都认为大于或等于枢轴，所以 storeIndex 指向 low
	// 它将是枢轴最终放置的位置的前一个位置
	storeIndex := low

	// 遍历从 low + 1 到 high 的所有元素
	for i := low + 1; i <= high; i++ {
		// 如果当前元素 arr[i] 小于枢轴
		if arr[i] < pivot {
			storeIndex++ // 移动 storeIndex 指针，扩展小于枢轴的区域
			// 将 arr[i] 交换到小于枢轴区域的下一个位置 (由 storeIndex 指向)
			arr[storeIndex], arr[i] = arr[i], arr[storeIndex]
		}
	}

	// 循环结束后，storeIndex 指针指向的是最后一个小于枢轴的元素的位置
	// 将枢轴元素 (它当前在 low 位置) 交换到 storeIndex 指针的位置
	// 这样枢轴元素就位于其最终的排序位置
	arr[low], arr[storeIndex] = arr[storeIndex], arr[low]

	// 返回枢轴元素最终的索引
	return storeIndex
}

func main() {
	numbers := []int{10, 7, 8, 9, 1, 5, 2, 4, 3, 6}
	fmt.Println("原始切片:", numbers)

	quickSort(numbers, 0, len(numbers)-1)
	fmt.Println("排序后切片:", numbers)

	fmt.Println("\n--- 测试另一个切片 ---")
	anotherNumbers := []int{3, 1, 4, 1, 5, 9, 2, 6}
	fmt.Println("原始切片:", anotherNumbers)
	quickSort(anotherNumbers, 0, len(anotherNumbers)-1)
	fmt.Println("排序后切片:", anotherNumbers)

	fmt.Println("\n--- 测试已排序切片 (可能触发最坏情况) ---")
	sortedNumbers := []int{1, 2, 3, 4, 5}
	fmt.Println("原始切片:", sortedNumbers)
	quickSort(sortedNumbers, 0, len(sortedNumbers)-1)
	fmt.Println("排序后切片:", sortedNumbers)

	fmt.Println("\n--- 测试逆序切片 (可能触发最坏情况) ---")
	reversedNumbers := []int{5, 4, 3, 2, 1}
	fmt.Println("原始切片:", reversedNumbers)
	quickSort(reversedNumbers, 0, len(reversedNumbers)-1)
	fmt.Println("排序后切片:", reversedNumbers)
}

快速排序原理（固定选择第一个元素为枢轴）

这种选择枢轴的方式是快速排序的经典实现之一，通常被称为 Lomuto 分区方案。

好的，非常乐意为你解释使用固定选择第一个元素作为枢轴的快速排序（Quick Sort）算法的思路。这种分区方法通常被称为 Lomuto 分区方案。

快速排序的核心是“分治”策略。当枢轴固定选择子数组的第一个元素时，整个算法的思路可以分解为以下几个关键步骤：

1. 高层思路：quickSort 函数的职责

   • 入口与递归：quickSort(arr, low, high) 函数负责对 arr 切片中从 low 索引到 high 索引的子数组进行排序。
   • 基线条件：递归必须有终止条件。如果 low >= high，意味着当前子数组为空或者只有一个元素，这种情况下数组自然有序，不需要做任何操作，直接返回。
   • 核心动作：
     1. 调用 partition 函数对当前子数组进行分区操作。
     2. partition 函数会返回枢轴元素在数组中的最终位置（pivotIndex）。
     3. 一旦枢轴归位，它就不再需要移动。所以，我们需要分别对枢轴左边和右边的子数组进行递归排序。
        • 递归左边：quickSort(arr, low, pivotIndex - 1)
        • 递归右边：quickSort(arr, pivotIndex + 1, high)

2. 核心思路：partition 函数的职责

   partition(arr, low, high) 函数是快速排序的心脏。它的目标是：

   • 选择一个枢轴元素（这里固定是 arr[low]）。
   • 重新排列子数组 arr[low...high] 中的元素，使得：
     • 所有小于枢轴的元素都被移动到枢轴的左边。
     • 所有大于或等于枢轴的元素都被移动到枢轴的右边。
   • 返回枢轴元素最终所在的索引。

   以下是 partition 函数的具体思路：

   • 步骤 1：选择枢轴

     • pivot := arr[low]：我们明确地将子数组的第一个元素定为枢轴。这个元素在分区过程中需要被“保护”起来，因为它最终要放到正确的位置。

   • 步骤 2：维护 storeIndex 指针

     • storeIndex := low：我们初始化一个 storeIndex 指针，它最初指向 low。这个指针的含义是：arr[low+1...storeIndex] 区域内的所有元素都小于枢轴。
     • 最初，这个“小于枢轴区域”是空的，所以 storeIndex 指向 low。当我们在 low+1 到 high 之间找到第一个小于枢轴的元素时，它应该被放在 storeIndex+1 的位置，然后 storeIndex 自身会递增。

   • 步骤 3：遍历并分区

     • 我们使用一个 for 循环，用 i 指针从 low + 1 开始遍历到 high（包括 high）。
     • 判断条件：在循环中，对于每个 arr[i]：
       • if arr[i] < pivot：如果当前元素 arr[i] 小于枢轴，这意味着它属于“小于枢轴区域”。
         • storeIndex++：首先，我们将 storeIndex 向右移动一位。这样做是为即将到来的交换操作腾出空间，storeIndex 现在指向“小于枢轴区域”的下一个可用位置。
         • arr[storeIndex], arr[i] = arr[i], arr[storeIndex]：然后，我们将当前元素 arr[i] 交换到 storeIndex 所指向的位置。这样，我们就成功地将一个小于枢轴的元素放置到了正确的分区。
       • else (arr[i] >= pivot)：如果当前元素大于或等于枢轴，则它应该留在“大于或等于枢轴区域”，不做任何操作，继续检查下一个元素。

   • 步骤 4：枢轴归位

     • 当 for 循环结束后，storeIndex 指针所指向的位置就是枢轴最终应该放置的位置。因为 arr[low+1...storeIndex] 是所有小于枢轴的元素。
     • arr[low], arr[storeIndex] = arr[storeIndex], arr[low]：我们将最开始选择的枢轴元素 (arr[low]) 与 arr[storeIndex] 处的元素进行交换。
     • 现在，枢轴元素 pivot 恰好位于 storeIndex 处，其左边都是小于它的元素，右边都是大于或等于它的元素。

   • 步骤 5：返回枢轴索引

     • return storeIndex：返回枢轴最终所在的索引，供 quickSort 函数进行递归调用。

总结这种思路的优缺点：

• 优点：代码逻辑相对清晰和简洁，易于理解和实现。
• 缺点：
  • 性能最坏情况：当输入数组已经部分有序或完全有序（或逆序）时，如果始终选择第一个元素作为枢轴，那么每次分区几乎都不能有效地将数组分成两半，而是会将数组分割成一个很小的部分和一个很大的部分。这会导致递归深度达到 $O(n)$，使得时间复杂度退化到 $O(n^2)$，这是快速排序的最坏情况。
  • 由于这个明显的缺点，在实际生产环境中，通常会使用随机选择枢轴或三数取中法来选择枢轴，以提高快速排序的平均性能并降低遇到最坏情况的概率。

这个版本的快速排序提供了一个基础的理解，但了解其在特定数据分布下的局限性，有助于选择更稳健的枢轴选择策略。