快速排序忘记怎么写了

综合讨论区
1

前几天装opensuse时候不小心把文档所在的分区当做安装路径，于是工作三个月的成果全没了，这几天忙着重写代码，但是在写快速排序时总是出错，有哪位可以帮忙写一个给我，顺便说一下，排序基准是数组中间的元素

2

@thautwarm 的MLStyle.jl 秀场:heart_eyes:

using MLStyle
qsort(lis)=
    @match lis begin
        []=>[]
        [x,xs...]=> [qsort(filter(i->i<=x,xs));[x]; qsort(filter(i->i>x,xs))]
    end
2 个赞
3

看上去速度不行啊

julia> using MLStyle

julia> using BenchmarkTools

julia> qsort(lis)=
           @match lis begin
               []=>[]
               [x,xs...]=> [qsort(filter(i->i<=x,xs));[x]; qsort(filter(i->i>x,xs))]
           end
qsort (generic function with 1 method)

julia> x = rand(1000);

julia> @btime qsort($x)
  1.649 ms (20001 allocations: 1.14 MiB)

julia> @btime sort($x; alg=QuickSort);
  16.300 μs (2 allocations: 7.95 KiB)

julia> @btime qsort($x);
  1.643 ms (20001 allocations: 1.14 MiB)

julia> @btime sort($x; alg=QuickSort);
  16.400 μs (2 allocations: 7.95 KiB)

julia> @btime sort($x);
  16.200 μs (1 allocation: 7.94 KiB)

julia> @btime sort($x);
  16.201 μs (1 allocation: 7.94 KiB)

julia> sort(x) == sort(x; alg=QuickSort)
true

julia> sort(x) == qsort(x)
true

还是默认算法厉害

function sort!(v::AbstractVector, lo::Int, hi::Int, a::QuickSortAlg, o::Ordering)
    @inbounds while lo < hi
        hi-lo <= SMALL_THRESHOLD && return sort!(v, lo, hi, SMALL_ALGORITHM, o)
        j = partition!(v, lo, hi, o)
        if j-lo < hi-j
            # recurse on the smaller chunk
            # this is necessary to preserve O(log(n))
            # stack space in the worst case (rather than O(n))
            lo < (j-1) && sort!(v, lo, j-1, a, o)
            lo = j+1
        else
            j+1 < hi && sort!(v, j+1, hi, a, o)
            hi = j-1
        end
    end
    return v
end
1 个赞
4

我只能表示@match没拖慢速度…