快速排序伪代码示例

快速排序是一种高效的排序算法，由C. A. R. Hoare在1960年提出。它采用分治法策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。

伪代码示例

基本思想

1. 选择一个基准元素（pivot）。
2. 将数组分成两部分：一部分包含所有比基准小的元素，另一部分包含所有比基准大的元素。
3. 对这两部分递归地进行上述操作，直到整个数组有序。

伪代码

快速排序(arr, low, high)
    如果 low < high
        p = 分区(arr, low, high) // 获取分区点p
        快速排序(arr, low, p - 1) // 对左半部分递归排序
        快速排序(arr, p + 1, high) // 对右半部分递归排序

分区(arr, low, high)
    pivot = arr[high] // 基准元素设为数组最后一个元素
    i = (low - 1) // i是较小值的索引位置
    从 j = low 到 j < high 循环
        如果 arr[j] <= pivot
            i += 1
            交换 arr[i] 和 arr[j]
    交换 arr[i + 1] 和 arr[high]
    返回 (i + 1) // 返回分区点p

交换(arr, i, j)
    临时变量 temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp

解释

• 快速排序 函数接收一个数组 arr 和两个整数参数 low 和 high，分别表示待排序区间的起始和结束位置。
• 分区 函数用于将数组划分为两部分，并返回基准元素的新位置。
• 在主函数中，通过递归调用 快速排序 对左右子区间进行排序。

实际示例

假设我们有一个数组 [10, 7, 8, 9, 1, 5] 需要对其进行快速排序：

初始状态: [10, 7, 8, 9, 1, 5]
选择pivot=5（arr[high]），进行分区操作后:
[1, 7, 8, 9, 10, 5]，新的基准位置为2（即索引1）

递归调用快速排序：
左子数组 [10, 7, 8, 9, 10, 5] (从low=0到p-1=2)
右子数组 [10, 7, 8, 9, 10, 5] (从p+1=3到high=len(arr)-1)

继续递归直至所有元素有序。

这个伪代码和示例展示了快速排序的基本流程。通过选择合适的基准值，可以显著提高算法的效率。