用位运算写了一个不通过比较大小的快速排序，有兴趣瞧一瞧？

学科相关
1

这是我用位运算写的快速排序算法，目前只能对正整数进行快速排序。有兴趣的朋友可以帮忙优化下代码，谢谢。
算法的原理是从最高位开始，把该位是0的数字划分到左边，是1的划分到右边，然后分别对左边和右边分别进行低一位的类似的排序，

# 如果要考虑最坏的情况，从二进制的角度进行考虑

# 不稳定的算法
# function partition!(v::AbstractVector, lo::Int, hi::Int, shift::Int64)
#     @inbounds while true
#         while lo <= hi && (v[lo] & shift) == 0; lo += 1; end;
#         while lo <= hi && (v[hi] & shift) != 0; hi -= 1; end;
#         lo >= hi && break
#         v[lo], v[hi] = v[hi], v[lo]
#         lo += 1; hi -= 1
#     end
#     return lo
# end

# 稳定的算法
function partition!(v::AbstractVector, lo::Int, hi::Int, shift::Int64)
    cur = lo
    @inbounds while lo <= hi
        if (v[lo] & shift) != 0
            j = max(cur, lo) + 1
            while j <= hi && (v[j] & shift) != 0; j += 1; end
            j > hi && return lo
            v[lo], v[j] = v[j], v[lo]
            cur = j
        end
        lo += 1
    end
    return lo
end


function BitSort!(v::AbstractVector, lo::Int, hi::Int, shift::Int64)
   if lo < hi && shift > 0
        j = partition!(v, lo, hi, shift)
        BitSort!(v, lo, j - 1, shift >> 1)
        BitSort!(v, j, hi, shift >> 1)
    end
    return v
end


function flp2(n::Int64)
    for i in (1, 2, 4, 8, 16, 32)
        n |= n >> i
    end
    n - (n >> 1)
end

function BitSort!(v::AbstractVector)
    shift = flp2(maximum(v))
    BitSort!(v, 1, length(v), shift)
end

number = 10^7
v = rand(1:number, number)
@time BitSort!(v)
@assert issorted(v)
@time BitSort!(v)