我很难理解快速排序，大多数演示和解释都忽略了实际发生的事情(例如 http://me.dt.in.th/page/Quicksort/)。
维基百科说:
Pick an element, called a pivot, from the array. Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation. Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.
如何处理 9,1,7,8,8 的数组，例如以 7 为基准？ 9 需要移动到主元的右侧，所有快速排序实现似乎都是就地操作，所以我们不能在 8,8 之后添加它，所以唯一的选择是将 9 与 7 交换。
现在数组是 7,1,9,8,8。快速排序背后的想法是，现在我们必须递归地对枢轴左侧和右侧的部分进行排序。枢轴现在位于数组的位置 0，这意味着没有左边的部分，所以我们只能对右边的部分进行排序。这是没有用的，因为 7>1 所以枢轴最终在错误的位置。
在这张图片中 4 是轴心，那么为什么 5 几乎一直向左移动？比4还大!经过大量交换后，它最终被排序，但我不明白这是怎么发生的。
最佳答案
快速排序
Quicksort 步骤是:
- 从列表中选择一个称为枢轴的元素。
- 重新排序列表，使值小于基准的所有元素都在基准之前，而值大于基准的所有元素都在基准之后(相等的值可以任意排列)。在此分区之后，枢轴位于其最终位置。这称为分区操作。
- 递归排序较小元素的子列表和较大元素的子列表。 递归的基本情况是大小为零或一的列表，它们永远不需要排序。
Lomuto分区方案
- 这个方案选择一个枢轴，它通常是中的最后一个元素 阵列。
- 算法维护索引以将主元放在变量 i 中，并且每次它找到一个小于或等于主元的元素时，这个 索引递增，该元素将被放置在 枢。
- 由于此方案更紧凑且易于理解，因此在介绍性 Material 中经常使用。
- 效率低于 Hoare 的原始方案。
分区算法(使用Lomuto分区方案)
algorithm partition(A, lo, hi) is
pivot := A[hi]
i := lo // place for swapping
for j := lo to hi – 1 do
if A[j] ≤ pivot then
swap A[i] with A[j]
i := i + 1
swap A[i] with A[hi]
return i
Quicksort 算法(使用 Lomuto 分区方案)
algorithm quicksort(A, lo, hi) is
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p – 1)
quicksort(A, p + 1, hi)
霍尔分区方案
使用从数组末尾开始的两个索引 分区，然后向对方移动，直到他们检测到 反转:一对元素，一个大于主元，一个 较小的，相对于彼此的顺序错误。这 然后交换反转的元素。
此算法有许多变体，例如，从 A[hi] 而不是 A[lo]
分区算法(使用霍尔分区方案)
algorithm partition(A, lo, hi) is
pivot := A[lo]
i := lo – 1
j := hi + 1
loop forever
do
i := i + 1
while A[i] < pivot
do
j := j – 1
while A[j] > pivot
if i >= j then
return j
swap A[i] with A[j]
快速排序算法(使用 Hoare 分区方案)
algorithm quicksort(A, lo, hi) is
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p)
quicksort(A, p + 1, hi)
Hoare partition scheme vs Lomuto partition scheme
枢轴选择
算法的执行速度在很大程度上取决于该机制的实现方式，实现不佳可以假设算法运行速度较慢。
主元的选择决定了数据列表的分区，因此，这是Quicksort算法实现中最关键的部分。重要的是尽量选择大小相同的左右分区。
最好和最坏的情况
最坏情况
最不平衡的划分发生在主元将列表分成大小为 _0 和 n − 1 的两个子列表时。如果基准恰好是列表中的最小或最大元素，或者在某些实现中所有元素都相等时，可能会发生这种情况。
最佳案例 在最平衡的情况下，每次我们执行分区时，我们将列表分成两个几乎相等的部分。这意味着每个递归调用都会处理一半大小的列表。
形式分析
- 最坏情况分析 = O(n²)
- 最佳案例分析 = O(n) 因素
- 平均案例分析 = O(n log n)
示例 source
使用额外内存
def quicksort(array):
less = []
equal = []
greater = []
if len(array) > 1:
pivot = array[0]
for x in array:
if x < pivot:
less.append(x)
if x == pivot:
equal.append(x)
if x > pivot:
greater.append(x)
return sort(less)+equal+sort(greater)
else:
return array
用法:
quicksort([12,4,5,6,7,3,1,15])
无需额外内存
def partition(array, begin, end):
pivot = begin
for i in xrange(begin+1, end+1):
if array[i] <= array[begin]:
pivot += 1
array[i], array[pivot] = array[pivot], array[i]
array[pivot], array[begin] = array[begin], array[pivot]
return pivot
def quicksort(array, begin=0, end=None):
if end is None:
end = len(array) - 1
if begin >= end:
return
pivot = partition(array, begin, end)
quicksort(array, begin, pivot-1)
quicksort(array, pivot+1, end)
用法:
quicksort([97, 200, 100, 101, 211, 107])
在你的例子中
调试 Lomuto 分区
关于algorithm - 理解快速排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/39665299/