当前位置：首页 > 文章列表 > Golang > Go问答 > 随机快速排序比尾递归快速排序运行得更快吗？

随机快速排序比尾递归快速排序运行得更快吗？

来源：stackoverflow 2024-04-14 12:27:37 0浏览收藏

积累知识，胜过积蓄金银！毕竟在Golang开发的过程中，会遇到各种各样的问题，往往都是一些细节知识点还没有掌握好而导致的，因此基础知识点的积累是很重要的。下面本文《随机快速排序比尾递归快速排序运行得更快吗？》，就带大家讲解一下知识点，若是你对本文感兴趣，或者是想搞懂其中某个知识点，就请你继续往下看吧~

问题内容

我在golang中实现了随机快速排序和尾递归快速排序并记录了运行时间。我发现尾递归快速排序需要更多时间来对数组进行排序。我输入的数组长度是 250, 500, 750, 1000, 1250, 1500, 1750, 2000, 2250, 2500。

下面是我的 golang 代码实现。

随机快速排序：

// this method will sort the array and place pivot at than correct position.
// we will then run another randomizedquicksort on the partitioned array.
// it take both float and int arrays as input
func randomizedquicksort(arr []interface{}, left int, right int) {
    if left < right {
        pivot := randomizedpartition(arr, left, right)
        randomizedquicksort(arr, left, pivot-1)
        randomizedquicksort(arr, pivot+1, right)
    }
}

func partition(a []interface{}, left int, right int) int {
    pivot := a[right]
    i := left - 1
    for j := left; j <= right-1; j++ {
        switch piv := pivot.(type) {
        case float64:
            if a[j].(float64) < piv {
                i++
                //swap
                a[i], a[j] = a[j], a[i]
            }
        case int:
            if a[j].(int) < piv {
                i++
                //swap
                a[i], a[j] = a[j], a[i]
            }
        }
    }
    //swap pivot with pth index
    a[right], a[i+1] = a[i+1], a[right]
    return i + 1
}

尾递归快速排序：

// this method will sort the array and place pivot at than correct position.
// we will then run another quicksort on the partitioned array.
// last thing we do is recursion in tail recursion
func tailrecursivequicksort(a []interface{}, left int, right int) {
    for left < right {
        pi := tailpartition(a, left, right)
        tailrecursivequicksort(a, left, right-1)
        left = pi + 1
    }
}

// this method will partition the array around pivot and return pivot's index
func tailpartition(a []interface{}, left int, right int) int {
    pivot := a[right]
    p := left - 1
    for i := left; i < right; i++ {
        switch piv := pivot.(type) {
        case float64:
            // if element is found lower than pivot swap it with pth element
            if a[i].(float64) <= piv {
                //swap
                p++
                a[p], a[i] = a[i], a[p]
            }
        case int:
            // if element is found lower than pivot swap it with pth element
            if a[i].(int) <= piv {
                //swap
                p++
                a[p], a[i] = a[i], a[p]
            }
        }
    }
    //swap pivot with pth index
    a[right], a[p+1] = a[p+1], a[right]
    return p + 1
}

尾递归快速排序的一个示例单元测试用例：

package main

import (
    "fmt"
    "testing"
    "time"
)

// 250 numbers
func testtailrecursionquicksort1(t *testing.t) {
    starttime := time.now()
    actualarray := []interface{}{123, 39, 2, 198, 236, 5, 214, 195, 100, 86, 162, 16, 233, 34, 197, 209, 173, 174, 238, 75, 6, 12, 191, 4, 44, 108, 85, 72, 216, 210, 248, 152, 226, 155, 38, 103, 45, 136, 206, 19, 181, 107, 81, 133, 118, 35, 190, 154, 212, 193, 232, 106, 196, 43, 243, 63, 245, 165, 60, 124, 36, 235, 137, 176, 228, 234, 183, 22, 187, 128, 142, 42, 29, 224, 131, 112, 110, 117, 217, 98, 178, 13, 74, 146, 122, 109, 1, 121, 78, 229, 46, 127, 150, 114, 28, 95, 8, 237, 32, 207, 166, 227, 144, 120, 15, 17, 94, 151, 47, 88, 247, 192, 82, 230, 31, 41, 138, 56, 21, 97, 53, 164, 126, 30, 67, 91, 66, 105, 71, 148, 125, 10, 218, 99, 203, 25, 119, 40, 250, 246, 153, 51, 84, 102, 186, 33, 37, 93, 104, 68, 18, 50, 139, 80, 205, 199, 20, 57, 27, 249, 145, 223, 168, 83, 140, 90, 201, 23, 184, 221, 156, 163, 202, 204, 157, 175, 241, 219, 116, 54, 149, 129, 194, 49, 64, 167, 211, 62, 87, 89, 59, 169, 14, 244, 200, 79, 24, 141, 171, 77, 189, 147, 134, 180, 225, 185, 73, 111, 213, 215, 158, 52, 69, 70, 11, 135, 7, 115, 101, 177, 76, 61, 208, 242, 48, 132, 26, 188, 182, 92, 239, 3, 58, 9, 172, 113, 160, 220, 222, 143, 130, 65, 170, 240, 231, 55, 159, 96, 179, 161}
    expectedarray := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250}
    tailrecursivequicksort(actualarray, 0, 249)
    timediff := time.now().sub(starttime)
    fmt.printf("time take to sort %v numbers is %v", len(actualarray), timediff)
    for i := 0; i < len(actualarray); i++ {
        if actualarray[i] != expectedarray[i] {
            t.fail()
            break
        }
    }
}

运行时间日志：

=== RUN   TestRandomizedQuickSort1
Time take to sort 250 numbers is 93.1µs--- PASS: TestRandomizedQuickSort1 (0.00s)
=== RUN   TestRandomizedQuickSort2
Time take to sort 500 numbers is 153.913µs--- PASS: TestRandomizedQuickSort2 (0.00s)
=== RUN   TestRandomizedQuickSort3
Time take to sort 750 numbers is 249.653µs--- PASS: TestRandomizedQuickSort3 (0.00s)
=== RUN   TestRandomizedQuickSort4
Time take to sort 1000 numbers is 299.693µs--- PASS: TestRandomizedQuickSort4 (0.00s)
=== RUN   TestRandomizedQuickSort5
Time take to sort 1250 numbers is 452.812µs--- PASS: TestRandomizedQuickSort5 (0.00s)
=== RUN   TestRandomizedQuickSort6
Time take to sort 1500 numbers is 577.646µs--- PASS: TestRandomizedQuickSort6 (0.00s)
=== RUN   TestRandomizedQuickSort7
Time take to sort 1750 numbers is 793.466µs--- PASS: TestRandomizedQuickSort7 (0.00s)
=== RUN   TestRandomizedQuickSort8
Time take to sort 2000 numbers is 2.100078ms--- PASS: TestRandomizedQuickSort8 (0.00s)
=== RUN   TestRandomizedQuickSort9
Time take to sort 2250 numbers is 1.534166ms--- PASS: TestRandomizedQuickSort9 (0.00s)
=== RUN   TestRandomizedQuickSort10
Time take to sort 2500 numbers is 1.488542ms--- PASS: TestRandomizedQuickSort10 (0.00s)
PASS

Debugger finished with the exit code 0




=== RUN   TestTailRecursionQuickSort1
Time take to sort 250 numbers is 2.166925ms--- PASS: TestTailRecursionQuickSort1 (0.00s)
=== RUN   TestTailRecursionQuickSort2
Time take to sort 500 numbers is 11.049337ms--- PASS: TestTailRecursionQuickSort2 (0.01s)
=== RUN   TestTailRecursionQuickSort3
Time take to sort 750 numbers is 36.98923ms--- PASS: TestTailRecursionQuickSort3 (0.04s)
=== RUN   TestTailRecursionQuickSort4
Time take to sort 1000 numbers is 213.94526ms--- PASS: TestTailRecursionQuickSort4 (0.21s)
=== RUN   TestTailRecursionQuickSort5
Time take to sort 1250 numbers is 87.065747ms--- PASS: TestTailRecursionQuickSort5 (0.09s)
=== RUN   TestTailRecursionQuickSort6
Time take to sort 1500 numbers is 105.232837ms--- PASS: TestTailRecursionQuickSort6 (0.11s)
PASS

Debugger finished with the exit code 0
=== RUN   TestTailRecursionQuickSort7
Time take to sort 1750 numbers is 2.632979054s--- PASS: TestTailRecursionQuickSort7 (2.63s)
=== RUN   TestTailRecursionQuickSort8
Time take to sort 2000 numbers is 1.082278134s--- PASS: TestTailRecursionQuickSort8 (1.08s)
=== RUN   TestTailRecursionQuickSort9
Time take to sort 2250 numbers is 3.14799009s--- PASS: TestTailRecursionQuickSort9 (3.15s)
=== RUN   TestTailRecursionQuickSort10
Time take to sort 2500 numbers is 4.877045862s--- PASS: TestTailRecursionQuickSort10 (4.88s)

运行这两种算法的测试用例后，我发现随机快速排序比尾递归更快。尾递归不就是随机快速排序的优化吗？让我知道你的想法。

谢谢

正确答案

问题的代码不包含随机配分函数。尾递归仅在每个循环上将大小减少一（从右到右-1），这是最坏的情况。如果存在大量重复元素，代码中使用的 lomuto 分区方案会降低到最坏情况时间复杂度：

https://en.wikipedia.org/wiki/Quicksort#Repeated_elements

示例 c++ hoare 分区代码，在较小的分区上递归，然后循环返回较大的分区。

void quicksort(int a[], int lo, int hi)
{
    while (lo < hi){
        int p = a[lo + (hi - lo) / 2];
        int i = lo - 1;
        int j = hi + 1;
        while (1){
            while (a[++i] < p);
            while (a[--j] > p);
            if (i >= j)
                break;
            std::swap(a[i], a[j]);
        }
        if(j - lo < hi - j){
            quicksort(a, lo, j);
            lo = j+1;
        } else {
            quicksort(a, j+1, hi);
            hi = j;
        }
    }
}

一个真正的 c++ 尾递归示例。 visual studio 发布版本会将尾递归调用转换为循环。

void QuickSort(int a[], int lo, int hi)
{
    if(lo < hi){
        int p = a[lo + (hi - lo) / 2];
        int i = lo - 1;
        int j = hi + 1;
        while (1){
            while (a[++i] < p);
            while (a[--j] > p);
            if (i >= j)
                break;
            std::swap(a[i], a[j]);
        }
        if(j - lo < hi - j){
            QuickSort(a, lo, j);
            QuickSort(a, j+1, hi);  // converted to loop
        } else {
            QuickSort(a, j+1, hi);
            QuickSort(a, lo, j);    // converted to loop
        }
    }
}

今天关于《随机快速排序比尾递归快速排序运行得更快吗？》的内容介绍就到此结束，如果有什么疑问或者建议，可以在golang学习网公众号下多多回复交流；文中若有不正之处，也希望回复留言以告知！

版本声明

本文转载于：stackoverflow 如有侵犯，请联系study_golang@163.com删除