正文
快速排序的基本思想是：通过一趟排序将待排的记录划分为独立的两部分，称为前半区和后半区，其中，前半区记录的关键字均不大于后半区的关键字，然后再分别对这两部分记录继续进行快速排序，从而使整个序列有序。
一趟快速排序的具体做法：
- 附设两个位置指示变量 i 和 j，它们的初始值分别指向序列的第一个记录和最后一个记录。
- 设枢轴记录（通常是第一个记录）的关键字为 pivot，则首先从 j 所指位置起向前搜索，找到第一个关键字小于 pivot 的记录时将该记录向前移到 i 指示的位置。
- 然后从 i 所指位置起向后搜索，找到第一个关键字大于 pivot 的记录时将该记录向后移动到 j 所指位置。
- 重复该过程直至 i 与 j 相等位置。
示例代码：
func TestQuickSort(t *testing.T) { input := []int{43, 63, 64, 35, 98, 24, 25, 62, 94, 35} quickSort(input, 0, len(input)-1) t.Log(input) } func quickSort(input []int, start, end int) { if start >= end { return } pivotIndex := partition(input, start, end) quickSort(input, start, pivotIndex-1) quickSort(input, pivotIndex+1, end) } func partition(input []int, start, end int) (pivotIndex int) { pivot := input[start] mark := start for k := start + 1; k <= end; k++ { if input[k] < pivot { mark++ tmp := input[k] input[k] = input[mark] input[mark] = tmp } } input[start] = input[mark] input[mark] = pivot return mark }
执行结果
