算法 - (排序)

2020-10-17 5296 words 11 minutes

Contents

Warning

本文最后更新于 July 31, 2022，文中内容可能已过时，请谨慎使用。

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

冒泡排序

代码实现

package main

import "fmt"

// BubbleSort 实现冒泡排序算法
func BubbleSort(arr []int) {
    n := len(arr)
    if n <= 1 {
        return // 数组为空或只有一个元素，无需排序
    }

    // 外层循环：控制排序的轮次
    // 每一轮将当前未排序部分的最大元素“冒泡”到末尾
    for i := 0; i < n-1; i++ {
        // 优化：设置一个标志位，如果在这一轮中没有发生交换，说明数组已经有序
        swapped := false

        // 内层循环：进行相邻元素的比较和交换
        // arr[n-1-i] 是每轮冒泡后已就位的最大元素，所以无需再次比较
        for j := 0; j < n-1-i; j++ {
            // 如果前一个元素比后一个元素大，则交换它们
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = true // 发生了交换
            }
        }

        // 如果在这一轮中没有发生任何交换，说明数组已经有序，提前退出
        if !swapped {
            break
        }
    }
}

func main() {
    // 示例用法
    data1 := []int{64, 34, 25, 12, 22, 11, 90}
    fmt.Println("Original:", data1)
    BubbleSort(data1)
    fmt.Println("Sorted:", data1) // Output: [11 12 22 25 34 64 90]

    data2 := []int{5, 1, 4, 2, 8}
    fmt.Println("Original:", data2)
    BubbleSort(data2)
    fmt.Println("Sorted:", data2) // Output: [1 2 4 5 8]

    data3 := []int{1, 2, 3, 4, 5} // 已经有序的数组
    fmt.Println("Original:", data3)
    BubbleSort(data3)
    fmt.Println("Sorted:", data3) // Output: [1 2 3 4 5] (会很快退出)

    data4 := []int{5, 4, 3, 2, 1} // 逆序数组
    fmt.Println("Original:", data4)
    BubbleSort(data4)
    fmt.Println("Sorted:", data4) // Output: [1 2 3 4 5]

    data5 := []int{} // 空数组
    fmt.Println("Original:", data5)
    BubbleSort(data5)
    fmt.Println("Sorted:", data5) // Output: []

    data6 := []int{7} // 单个元素数组
    fmt.Println("Original:", data6)
    BubbleSort(data6)
    fmt.Println("Sorted:", data6) // Output: [7]
}

冒泡排序是一种简单的交换排序算法。它的基本思想是：重复地遍历待排序的列表，一次比较两个相邻的元素，如果它们的顺序错误就将它们交换过来。重复地执行这个过程，直到没有再需要交换的元素，这表示列表已经排序完成。

排序原理

想象一下，你有一串数字：[5, 1, 4, 2, 8]。冒泡排序会这样操作：

从头开始，比较第一个和第二个元素，如果第一个比第二个大，就交换它们。
然后比较第二个和第三个元素，如果第二个比第三个大，就交换。
依此类推，直到比较到列表的末尾。

完成一次完整的遍历后，列表中最大的元素就会“冒泡”到它最终的位置（列表的末尾）。然后，对剩余未排序的部分重复这个过程，直到所有元素都归位。

快速排序

代码实现

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 分区方案。

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

高层思路：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)
核心思路：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)$，这是快速排序的最坏情况。
- 由于这个明显的缺点，在实际生产环境中，通常会使用随机选择枢轴或三数取中法来选择枢轴，以提高快速排序的平均性能并降低遇到最坏情况的概率。

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

归并排序

代码实现

package main

import "fmt"

// MergeSort 是归并排序的主函数
func MergeSort(arr []int) {
    if len(arr) <= 1 {
        return // 数组为空或只有一个元素，无需排序
    }
    // 调用递归辅助函数
    mergeSortRecursive(arr, 0, len(arr)-1)
}

// mergeSortRecursive 是归并排序的递归实现
// low: 子数组的起始索引
// high: 子数组的结束索引
func mergeSortRecursive(arr []int, low, high int) {
    if low < high { // 如果子数组至少有两个元素，就继续分解
        mid := low + (high - low) / 2 // 计算中点索引，避免 (low+high) 溢出

        // 递归地对左半部分和右半部分进行排序
        mergeSortRecursive(arr, low, mid)
        mergeSortRecursive(arr, mid+1, high)

        // 当左右两部分都排好序后，合并它们
        merge(arr, low, mid, high)
    }
}

// merge 函数将两个有序子数组合并成一个大的有序数组
// arr: 原始数组
// low: 第一个子数组的起始索引
// mid: 第一个子数组的结束索引 / 第二个子数组的前一个索引
// high: 第二个子数组的结束索引
func merge(arr []int, low, mid, high int) {
    // 创建一个临时数组，用于存放合并后的有序元素
    // 注意：temp 数组的大小是 high - low + 1
    temp := make([]int, high-low+1)

    // 设置三个指针
    i := low      // 指向第一个子数组的起始位置
    j := mid + 1  // 指向第二个子数组的起始位置
    k := 0        // 指向临时数组的起始位置

    // 比较两个子数组的元素，将较小的放入临时数组
    for i <= mid && j <= high {
        if arr[i] <= arr[j] { // 注意这里使用 <= 保证稳定性
            temp[k] = arr[i]
            i++
        } else {
            temp[k] = arr[j]
            j++
        }
        k++
    }

    // 将第一个子数组中剩余的元素（如果有的话）全部放入临时数组
    for i <= mid {
        temp[k] = arr[i]
        i++
        k++
    }

    // 将第二个子数组中剩余的元素（如果有的话）全部放入临时数组
    for j <= high {
        temp[k] = arr[j]
        j++
        k++
    }

    // 将临时数组中的有序元素复制回原始数组的相应位置
    for k := 0; k < len(temp); k++ {
        arr[low+k] = temp[k]
    }
}

func main() {
    // 示例用法
    data1 := []int{9, 2, 7, 5, 1, 8, 3, 6, 4}
    fmt.Println("Original:", data1)
    MergeSort(data1)
    fmt.Println("Sorted:", data1) // Output: [1 2 3 4 5 6 7 8 9]

    data2 := []int{5, 4, 3, 2, 1}
    fmt.Println("Original:", data2)
    MergeSort(data2)
    fmt.Println("Sorted:", data2) // Output: [1 2 3 4 5]

    data3 := []int{1, 2, 3, 4, 5}
    fmt.Println("Original:", data3)
    MergeSort(data3)
    fmt.Println("Sorted:", data3) // Output: [1 2 3 4 5]

    data4 := []int{3, 1, 4, 1, 5, 9, 2, 6}
    fmt.Println("Original:", data4)
    MergeSort(data4)
    fmt.Println("Sorted:", data4) // Output: [1 1 2 3 4 5 6 9]

    data5 := []int{}
    fmt.Println("Original:", data5)
    MergeSort(data5)
    fmt.Println("Sorted:", data5) // Output: []

    data6 := []int{7}
    fmt.Println("Original:", data6)
    MergeSort(data6)
    fmt.Println("Sorted:", data6) // Output: [7]
}

归并排序是一种基于 分治（Divide and Conquer） 思想的排序算法。它的核心理念是将一个大的复杂问题，分解成两个或多个相同类型的较小问题，然后解决这些小问题，最后将小问题的解合并起来，从而得到原问题的解。

想象你有一堆散乱的扑克牌，要按顺序整理好。

分解（Divide）： 你先把这堆牌分成两半。如果每半还是太多，就继续分，直到你手上的每一堆牌都只剩下一张牌（一张牌肯定是排好序的）。
治理（Conquer）： 既然每堆只有一张牌，那它们都已经是“有序”的了。
合并（Combine/Merge）： 现在，你把两堆相邻的、已经排好序的牌拿起来，然后像玩牌一样，从两堆中轮流取出最小的那张牌，放到一个新的牌堆里。这样，你就能得到一个更大的、排好序的牌堆。重复这个合并过程，直到所有的小牌堆都合并成了一个完整的、排好序的大牌堆。

归并排序的思路与步骤

归并排序主要分为两个核心步骤：分解和合并。

1. 分解（Divide）

这个步骤相对简单，就是不断地将当前数组从中间一分为二。

初始状态： 拿到一个待排序的数组 arr 和它的起始索引 low、结束索引 high。
判断条件： 如果 low < high（即数组中至少有两个元素，还有分下去的必要），就继续分解。
找到中点： 计算 mid = low + (high - low) / 2。
递归分解：
- 对左半部分进行递归分解：mergeSort(arr, low, mid)
- 对右半部分进行递归分解：mergeSort(arr, mid+1, high)
终止条件： 当子数组只剩下一个元素（low == high）时，递归停止。因为一个元素的数组天然就是有序的。

2. 合并（Merge）

这是归并排序最巧妙和核心的部分。当递归分解到只剩单个元素后，就开始逐层向上合并。

想象一下，你现在已经完成了“分解”步骤，手上不是一堆散乱的牌了，而是有两小堆已经各自整理好顺序的牌。

左手一堆牌： [1, 5, 8] （已经从小到大排好了）
右手一堆牌： [2, 3, 9] （也已经从小到大排好了）

现在，你的任务是把这两堆牌合并成一堆完整的、有序的牌：[1, 2, 3, 5, 8, 9]。

输入： 两个相邻的、已经有序的子数组。它们分别是 arr[low...mid] 和 arr[mid+1...high]。
目标： 将这两个有序子数组合并成一个更大的有序数组，并放回原数组 arr 的相应位置 arr[low...high]。
实现步骤（通常需要一个临时数组）：
1. 创建临时数组： 准备一个与待合并区域大小相同的临时数组 temp。
2. 设置指针：
  - 一个指针 i 指向左子数组的起始位置 (low)。
  - 一个指针 j 指向右子数组的起始位置 (mid + 1)。
  - 一个指针 k 指向临时数组的起始位置 (0)。
3. 比较并合并：
  - 在 i <= mid 且 j <= high的条件下循环：
    - 比较 arr[i] 和 arr[j]。
    - 将两者中较小的那个元素放入 temp[k]。
    - 相应地移动较小元素的指针（i 或 j）和 k。
4. 处理剩余元素：
  - 循环结束后，如果左子数组还有剩余元素（i <= mid），将它们全部复制到 temp 中。
  - 如果右子数组还有剩余元素（j <= high），将它们全部复制到 temp 中。
5. 复制回原数组： 将临时数组 temp 中的所有元素，按顺序复制回原数组 arr 从 low 到 high 的位置。