我该如何读懂这个15行的数组排序函数qsort!的代码？

综合讨论区 Julia入门
1

我使用vscode左边栏的run and debug, 添加了一些断点，可以看到local变量每次运行的变化…

但函数qsort!里又出现了qsort!击溃了我。这来自于c吗？

把函数体当作一种循环之后这个套娃变得好接受了。
我想我现在的问题在于：

pivot = a[(lo+hi)>>>1]

这个函数来自于官方主页，那么我认为它就是最优算法，那么为什么这样做是最优的呢？

function qsort!(a,lo,hi)
    i, j = lo, hi
    while i < hi
        pivot = a[(lo+hi)>>>1]
        while i <= j
            while a[i] < pivot; i += 1; end
            while a[j] > pivot; j -= 1; end
            if i <= j
                a[i], a[j] = a[j], a[i]
                i, j = i+1, j-1
            end
        end
        if lo < j; qsort!(a,lo,j); end
        lo, j = i, hi
    end
    return a
end

sortperf(n) = qsort!(rand(n), 1, n)

sortperf(6)

代码引自：

Microbenchmarks/perf.jl at master · JuliaLang/Microbenchmarks · GitHub

我试图debug：
F5（继续）:每一行添加断点，运行代码。

这里发现每一行添加断点和单步调试的区别：

F11（单步调试）:跳到了另一个page里

@eval setindex!(A::Array{T}, x, i1::Int) where {T} = arrayset($(Expr(:boundscheck)), A, convert(T,x)::T, i1)

vscode这个debug还能快一些吗，读秒时间有点久了，助长self-humiliation…

2

看上去是利用了二分法，递归的快排算法。

julia> a = collect(1:10)
10-element Vector{Int64}:
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10

julia> a .>>> 1
10-element Vector{Int64}:
 0
 1
 1
 2
 2
 3
 3
 4
 4
 5

pivot 应当是取了 lo 与 hi 中间的元素。
你可以参考

3

题外话，qsort这个是不是暂且不说，但一般情况下并不能单靠是否出自官方主页就得出这种结论。

4

啊对对对！就是它！
昨晚我把问题梳理好拿两个手指头比划指针比划出来了，对上了，感谢回复！

这个>>>1，玩矩阵是真好用索引拼接啥的，现在也是我的了。

不好意思再发帖了，这里偷偷问一下：
想把vector{Vector{Any}}变成Matrix{any}，有比reduce(hcat,target)更好的吗？

a = [collect(0:2) for i in (1:3)]
reduce(hcat,a)
5

aye aye.
确实不妥，我改下。
#update
我改不了了呢！

6

我一般这么用VScode来debug:
先用Alt+Enter(实际是Julia: Execute Code in REPL and Move的快捷键，可用F1，输入命令来找到)加载相关的函数，再用Alt+Enter运行@run foo(arg) 进入debug.

7

qsort，q的含义应该是quickly，就是快排。快排是不是最优排序我不太清楚，但是快排的分而治之（这就是你会遇到函数递归函数的原因）使得快排的时间复杂度变成了O(nlogn)，比冒泡排序的双循环的O(n2)快很多。
。。。>>>1，表示二进制下右移1位，等价于整除2并向下取整，这个做法比//2快很多。

8

如何一行一行的执行并看中间变量的变化呢? 没能找到.
像我恨不得每个函数每一行都添加个断点(:older_man:就是这样做的).

9

感谢各位的回复!

明天下午年终大组会, 老板给我30min让我推销Julia.

回复不及时希望原谅.

ppt还在做做做做不完了呜呜

1 个赞
10

image
image838×156 14.4 KB

image
image1804×865 126 KB

在源码点上断点，用上面的按钮/快捷键进行单步、进入函数等调试。

1 个赞