快速排序算法的原理图解(快速排序法排序过程图解)
快速排序算法的原理图解
简介
快速排序是一种高效的排序算法,它通过分治法将一个无序列表逐渐排序。其平均时间复杂度为 O(n log n),最坏情况下的时间复杂度为 O(n²)。
步骤
快速排序算法主要包含以下步骤:1.
选择一个基准元素:
从列表中选择一个元素作为基准。 2.
分区:
将列表划分为两部分:小于基准元素的部分和大于基准元素的部分。 3.
递归:
对两个分区中的每个部分重复步骤 1 和 2,直到所有部分都排序好。
图解
以下是一个快速排序算法的分步图解:
步骤 1:选择基准元素
![图 1:选择基准元素](https://www.cs.usfca.edu/~galles/visualization/ComparisonSortApplet.html#quicksort)
从列表中选择一个元素作为基准。通常选择列表的中间元素或随机元素。
在本例中,选择 50 作为基准。
步骤 2:分区
![图 2:分区](https://www.cs.usfca.edu/~galles/visualization/ComparisonSortApplet.html#quicksort)
从列表的末尾开始遍历,找到第一个小于基准的元素。
将该元素交换到第一个小于基准的部分。
从列表的开头开始遍历,找到第一个大于基准的元素。
将该元素交换到第二个大于基准的部分。
重复这些步骤,直到遍历完整个列表。
步骤 3:递归
![图 3:递归](https://www.cs.usfca.edu/~galles/visualization/ComparisonSortApplet.html#quicksort)
对小于基准的部分递归应用快速排序算法。
对大于基准的部分递归应用快速排序算法。
重复步骤
重复步骤 1 到 3,直到列表的每个部分都排序好。
伪代码
以下是一个快速排序算法的伪代码:```python def quick_sort(arr):if len(arr) <= 1:return arrpivot = arr[len(arr) // 2]left = [x for x in arr if x < pivot]middle = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return quick_sort(left) + middle + quick_sort(right) ```