gsort

Documentation

Index

• func Sort(sli []int) []int

Functions

func Sort

func Sort(sli []int) []int

双轴快排排序 基本思想： 双轴快排每轮选取两个轴 pivot1、pivot2 (pivot1 < pivot2)，然后以两个轴为分界， 将数组分为左中右三个区域。交换三个区域内的数字，使得三个区域分别属于区间 (-∞, pivot1)、[pivot1, pivot2]、(pivot2, +∞)。然后再对左中右区域不断重复此过程， 直至排序完成。 具体步骤： 通过数组的中间位置往前和往后走两次数组长度的 1/7 步长取出 5个备选轴。 如果 5个备选轴互不相等，取第二个轴和第四个轴进行双轴快排，将数组分成三个区域：

(-∞, pivot1)、[pivot1, pivot2]、(pivot2, +∞)。

分区后，如果中间区域过大（大于数组长度的 4/7），则将中间区域再次分成三个区域：

[pivot1, pivo1]、(pivot1, pivot2)、[pivot2, pivot2]，
只让 (pivot1, pivot2)区间参与下一轮双轴快排。

最后，对左中右三个区域递归进行排序。 具体参见: https://leetcode-cn.com/leetbook/read/sort-algorithms/phs9u1/