快速排序算法详解：步骤、示例及代码实现

快速排序是一种高效的排序算法，它采用分治策略，将一个序列递归地划分为两个子序列，然后分别对子序列进行排序，最后将排序后的子序列合并。

步骤：

选择基准值： 从序列中选择一个元素作为基准值，通常选择第一个元素或最后一个元素。
划分序列： 将序列分为两部分，小于等于基准值的元素放在左边，大于基准值的元素放在右边。
递归排序： 递归地对左右两部分进行快速排序，直到所有子序列都被排序。

示例：

假设我们有以下序列：[8, 3, 1, 5, 2, 9, 4, 7, 6]。

步骤1：选择基准值

选择序列的第一个元素8作为基准值。

步骤2：划分序列

使用两个指针low和high，分别指向序列的起始位置和结束位置。

从右往左，找到第一个小于等于基准值的元素。在这个例子中，我们找到了元素7，将其与基准值交换位置，序列变为[7, 3, 1, 5, 2, 9, 4, 8, 6]。
从左往右，找到第一个大于基准值的元素。在这个例子中，我们找到了元素9，将其与基准值交换位置，序列变为[7, 3, 1, 5, 2, 8, 4, 9, 6]。
重复上述步骤，直到low和high指针相遇。此时将基准值放在相遇的位置上，序列变为[6, 3, 1, 5, 2, 7, 4, 8, 9]。

步骤3：递归排序

对左边的序列[6, 3, 1, 5, 2, 7, 4]进行快速排序：
- 选择基准值为6。
- 找到第一个小于等于基准值的元素为4，与基准值交换位置，序列变为[4, 3, 1, 5, 2, 7, 6]。
- 找到第一个大于基准值的元素为7，与基准值交换位置，序列变为[4, 3, 1, 5, 2, 6, 7]。
- 将基准值放在相遇的位置上，序列变为[2, 3, 1, 5, 4, 6, 7]。
- 对序列[2, 3, 1, 5, 4]进行快速排序：
  - 选择基准值为2。
  - 找到第一个小于等于基准值的元素为1，与基准值交换位置，序列变为[1, 3, 2, 5, 4]。
  - 找到第一个大于基准值的元素为3，与基准值交换位置，序列变为[1, 2, 3, 5, 4]。
  - 将基准值放在相遇的位置上，序列变为[1, 2, 3, 5, 4]。
- 对序列[5, 4]进行快速排序：
  - 选择基准值为5。
  - 找到第一个小于等于基准值的元素为4，与基准值交换位置，序列变为[4, 5]。
  - 将基准值放在相遇的位置上，序列变为[4, 5]。
- 合并左右两部分的结果，得到[1, 2, 3, 4, 5, 6, 7]。
对右边的序列[8, 9]进行快速排序：
- 选择基准值为8。
- 将基准值放在相遇的位置上，序列变为[8, 9]。
- 对序列[9]进行快速排序，结果为[9]。
- 合并左右两部分的结果，得到[8, 9]。

步骤4：合并结果

最终将左右两部分的结果合并起来，得到最终排序结果为[1, 2, 3, 4, 5, 6, 7, 8, 9]。

代码实现：

def quick_sort(arr):
  if len(arr) <= 1:
    return arr
  pivot = arr[0]
  left = [x for x in arr[1:] if x <= pivot]
  right = [x for x in arr[1:] if x > pivot]
  return quick_sort(left) + [pivot] + quick_sort(right)

# 示例使用
array = [8, 3, 1, 5, 2, 9, 4, 7, 6]
sorted_array = quick_sort(array)
print(sorted_array)  # 输出：[1, 2, 3, 4, 5, 6, 7, 8, 9]

快速排序的优缺点：

优点：

平均时间复杂度为O(n log n)，效率很高。
原地排序，不需要额外的空间。

缺点：

最坏情况下时间复杂度为O(n^2)，例如序列已经排序或逆序排序。
不稳定排序，相同元素的相对顺序可能改变。

总结：

快速排序是一种高效的排序算法，广泛应用于各种场景。但是，在数据已经排序或逆序排序的情况下，其效率会下降。因此，选择合适的排序算法需要根据实际情况进行判断。