C++快速排序（递归）算法详解

快速排序是由 C.A.R.Hoare 于 1962 年发明的递归排序算法。它非常高效，通常用于对存储在数组中的项目列表进行排序。

快速排序通常写成一个包含 3 个形参的递归函数，这 3 个形参可以定义要排序的数组的一部分，它们分别是，一个包含项目列表的数组 arr，以及两个下标 start 和 end，表示要排序的 arr 数组段的开始和结束。可以将这 3 个形参写作 arr[start .. end]。要对整个数组进行排序，可以调用快速排序，将 start 设置为 0，并将 end 设置为数组大小减 1。

快速排序的工作原理如下，如果 start 大于或等于 end，那么被排序的 arr 段最多有一个元素，因此已经排序，在这种情况下，快速排序立即返回。否则，快速排序将通过选择 arr[start .. end] 中的一个元素作为一个基准元素，来对 arr[start .. end] 进行分区，然后重新排列 arr[start .. end]，以便所有小于基准的条目都在基准的左侧，所有大于或等于基准的条目都在基准的右侧。

实际上，分区步骤重新排列了 arr[start..end]，以使它由子列表 1、基准元素和子列表 2 组成，如图 1 所示。