快速排序算法，重庆邮电大学数据结构实验8

快速排序（Quicksort）是一种高效的排序算法，采用分治法（Divide and Conquer）策略。其基本思想是通过一个枢轴（pivot）元素将待排序数组分成两部分，其中一部分的所有元素都小于枢轴元素，另一部分的所有元素都大于枢轴元素，然后递归地对这两部分进行排序。

快速排序的主要步骤如下：

1. **选择枢轴元素**：通常可以选择数组的第一个元素、最后一个元素或中间元素作为枢轴。
2. **分区操作**：将数组分成两部分，使得左边的元素都小于枢轴元素，右边的元素都大于枢轴元素。
3. **递归排序**：对左右两部分分别递归地应用快速排序。

以下是快速排序的伪代码：

快速排序(array, low, high)
    if low < high
        pivotIndex = 分区(array, low, high)
        快速排序(array, low, pivotIndex - 1)
        快速排序(array, pivotIndex + 1, high)

分区(array, low, high)
    pivot = array[high]
    i = low - 1
    for j = low to high - 1
        if array[j] < pivot
            i = i + 1
            交换 array[i] 和 array[j]
    交换 array[i + 1] 和 array[high]
    return i + 1

快速排序的时间复杂度平均情况下为O(n log n)，最坏情况下为O(n^2)，但通过随机选择枢轴或使用其他优化方法，可以有效避免最坏情况的发生。