关于快速排序:快速排序的简介以及随机三数中值优化

快排的思维是，选取数组中一个数，作为基准(pivot)，而后将数组分成左右两局部。右边局部全副小于基准，左边局部全副大于基准。随后再去递归地对右边局部和左边局部做雷同操作，直至数组被宰割成繁多一个元素，排序实现。网络上大部分快排的实现都是递归实现，这里给出模板。

// 快排模板
func QuickSort(nums []int, leftEnd, rightEnd int) {
    if leftEnd < rightEnd {mid := Partition(nums, leftEnd, rightEnd)
        QuickSort(nums, leftEnd, mid-1)
        QuickSort(nums, mid+1, rightEnd)
    }
}

快排函数接管数组 (nums)、左边界(leftEnd)、右边界(rightEnd)。左边界必须小于右边界。数组传入后，先通过Partition() 函数分区。数组和左右边界被传入 Partition() 后，数组会被辨别左右两局部，右边的元素都小于左边的元素，Partition()会返回一个数值 mid 代表分区左右的基准值的下标。随后通过递归，再对基准数左右两边作出同样操作。

快排的要害算法，在于 Partition() 的设计。优化的要害，大部分在于基准数的选取。

疾速排序是东尼霍尔 (Tony Hoare) 设计的，他设计的算法思路，是选取要排序局部的第一个元素的作为基准。而后有左右两个指针从左右往两头凑近。右指针遇到比基准小的元素，会停下。左指针遇到比基准大的元素，会停下。两个指针进行后，会替换左右指针的元素，随后持续往两头后退，直至两个指针重合。而后再把最右边的基准值插入指针所在位置。

// 霍尔分区，采纳最右边的元素作为基准
func HoarePartition(nums []int, leftEnd, rightEnd int) int {pivot := nums[leftEnd]
    l := leftEnd
    r := rightEnd
    for l < r {for l < r && nums[r] >= pivot {r--}
        for l < r && nums[l] <= pivot {l++}
        nums[l], nums[r] = nums[r], nums[l]
    }
    nums[leftEnd], nums[l] = nums[l], nums[leftEnd]
    return l
}

这个实际上也是大部分人写的版本。

算法的导论的版本，是以最左边的元素作为基准。而后有两个前后指针从前到后扫描。我在代码里依然称其为左指针和右指针，但实际上他们都是从左往右挪动的。首先是右指针，开始扫描，如果遇到比最左边元素小的，则让左指针向右挪动一步，并替换左右指针元素。直到右指针扫描到最左边元素（也就是基准）的前一个元素。随后再将左指针的下一元素于基准元素对换。

这样子看起来如同很难了解。实际上，在左右指针向右挪动的过程中，左指针右边的元素都会比基准小，左指针到右指针的局部都比基准大，右指针到基准的前一个元素，都是还没排序的。当扫描实现后，再将最右方的基准与左指针的下一元素对换。最初的后果依然是基准左方小于基准，基准右方大于基准。倡议看视频了解五点七边:【排序算法精髓 3】疾速排序 (上）

// 算法导论分区，以最右为基准
func IOAPartition(nums []int, leftEnd, rightEnd int) int {pivot := nums[rightEnd]
    l := leftEnd - 1
    r := leftEnd
    for ; r <= rightEnd-1; r++ {if nums[r] <= pivot {
            l++
            nums[l], nums[r] = nums[r], nums[l]
        }
    }
    nums[rightEnd], nums[l+1] = nums[l+1], nums[rightEnd]
    return l + 1
}

这种形式，替换次数会比拟多，在实践中我发现会比霍尔的慢，在 leetcode 上会超时。在 l++ 后加个 if l!=r 的判断能够勉强不超时。

快排的最优工夫复杂度是 O(Nlog(2)N)，最坏状况下是O(N^2)。这个其实能够从递归树和递推公式大略猜想到。快排通常用递归实现，参考自《数据结构与算法剖析 C 语言形容》7.7.5，其工夫复杂度能够形容为T(N)=T(i)+T(N-i-1)+cN。i 是递归时子数组长度，c 是一个常数，与Partition() 函数相干。

若是每次宰割数组都将数组分为大小相等的两组，那工夫简单递推公式可形容为 T(N)=T(N/2)+cN。若是每次宰割为 1 和 N - 1 长度的数组，那工夫复杂度为T(N)=T(1)+T(N-1)+cN。由此能够得出最好T(N)=O(Nlog(2)N) 和最坏T(N)=O(N^2)。

也可也用递归树的想法来推导，若每次平等宰割数组，那快排的递归树深度就为 log(2)N。若每次只分成 1 和 N - 1 长度的，那递归树深度就会变成 N。再对每个节点乘以 Partition 函数所破费的工夫。能够别离得出 O(Nlog(2)N)和 O(N^2)的论断。

因而，优化的一个要害是如何让每次宰割尽可能均匀，获得中位数。

下面形容的取第一和最初一个数的分区办法，在遇到逆序和程序数组时，会进化到最坏状况。因而能够应用随机选取基准的形式，毁坏这一状况。

// 算法导论分区优化 1
// 随机选取基准
func IOAPartition1(nums []int, leftEnd, rightEnd int) int {// rand.Seed(time.Now().Unix()) 将会超时
    random := leftEnd + rand.Intn(rightEnd-leftEnd+1)
    nums[rightEnd], nums[random] = nums[random], nums[rightEnd]
    pivot := nums[rightEnd]
    l := leftEnd - 1
    r := leftEnd
    for ; r <= rightEnd-1; r++ {if nums[r] <= pivot {
            l++
            nums[l], nums[r] = nums[r], nums[l]
        }
    }
    nums[rightEnd], nums[l+1] = nums[l+1], nums[rightEnd]
    return l + 1
}

留神，在 Go 中间接应用 rand.Intn() 产生的只是伪随机数，也就是输出同样的参数，每次调用都返回同样后果，但因为咱们在每层递归时，都设定了不同的上下界，所以取得的随机数也是每次不同的，这个时能够承受的。如果尝试在每层递归都设置随机数种子，将会导致超时，因为这个操作太耗时了。我测试的后果，每次加工夫戳种子的耗时是不加种子的 452 倍左右。

为了尽量将数组平分，应该尽量取中位数，但为了精确取到中位数自身就须要一次排序。所以为了尽可能的获得中位数，咱们抉择数组的第一、最初、以及两头的三个数，求这三个数的中位数，作为对这个子数组中位数的预计。

// 算法导论分区优化 2
// 抉择三个求中位数
func IOAPartition2(nums []int, leftEnd, rightEnd int) int {
    median := rightEnd
    if len(nums) > 2 {half := (leftEnd + rightEnd) / 2
        if nums[leftEnd] <= nums[half] && nums[half] <= nums[rightEnd] {median = half}
        if nums[leftEnd] <= nums[rightEnd] && nums[rightEnd] <= nums[half] {median = rightEnd}
        if nums[half] <= nums[leftEnd] && nums[leftEnd] <= nums[rightEnd] {median = leftEnd}
        if nums[half] <= nums[rightEnd] && nums[rightEnd] <= nums[leftEnd] {median = rightEnd}
        if nums[rightEnd] <= nums[half] && nums[half] <= nums[leftEnd] {median = half}
        if nums[rightEnd] <= nums[leftEnd] && nums[leftEnd] <= nums[half] {median = leftEnd}

    }
    nums[rightEnd], nums[median] = nums[median], nums[rightEnd]
    pivot := nums[rightEnd]
    l := leftEnd - 1
    r := leftEnd
    for ; r <= rightEnd-1; r++ {if nums[r] <= pivot {
            l++
            nums[l], nums[r] = nums[r], nums[l]
        }
    }
    nums[rightEnd], nums[l+1] = nums[l+1], nums[rightEnd]
    return l + 1
}

快排及其优化就介绍这么多，此外还有混合插入排序以及尾递归优化等形式，倡议各位看其余博客。

[1]《数据结构与算法剖析 C 语言形容》7.5
[2] 五点七边:【排序算法精髓 3】疾速排序 (上）
[3] 疾速排序算法的工夫复杂度剖析[详解 Master method]

关于快速排序:快速排序的简介以及随机三数中值优化

介绍

实现

东尼霍尔的实现

算法导论的实现

优化

随机优化

三数中值

参考