Julia中的递归冒泡排序和插入排序

Question

我对Julia比较陌生，我已经在Julia中实现了冒泡排序和插入排序算法的迭代形式。

我想知道如何在JULIA中实现递归形式的冒泡排序和插入排序?

谢谢。

Answer 1

尾部递归在这里会有帮助:

using BenchmarkTools
function bubblesort(arr::T) where T <: AbstractArray
function recursebubble(a::T, remaining::T, sorted::T)
if length(a) < 2
if isempty(remaining)
return [a ; sorted]
else
x = popfirst!(a)
return recursebubble(remaining, T(), [x ; sorted])
end
else
x = popfirst!(a)
y = popfirst!(a)
if x > y
pushfirst!(remaining, y)
pushfirst!(a, x)
else
pushfirst!(remaining, x)
pushfirst!(a, y)
end
return recursebubble(a, remaining, sorted)
end
end
recursebubble(copy(arr), T(), T())
end
function insertionsort(arr::T) where T <: AbstractArray
function insert(a::T, x::eltype(T))
if isempty(a)
push!(a, x)
else
y = popfirst!(a)
if x <= y
pushfirst!(a, y)
pushfirst!(a, x)
else
a = insert(a, x)
pushfirst!(a, y)
end
end
return a
end
function recursiveinsertion(a::T)
isempty(a) && return a
x = popfirst!(a)
return insert(recursiveinsertion(a), x)
end
return recursiveinsertion(copy(arr))
end

randarray = rand(Int8, 100)
println("Recursive insertion: ", insertionsort(randarray))
@btime insertionsort(randarray)
println("Recursive bubble: ", bubblesort(randarray))
@btime bubblesort(randarray)
println("Base sort: ", sort(randarray))
@btime sort(randarray)
Recursive insertion: Int8[-126, -124, -124, -124, -108, -106, -105, -99, -98, -96, -95, -94, -89, -86, -85, -85, -83, -82, -79, -72, -66, -62, -59, -57, -56, -52, -42, -41, -37, -36, -35, -32, -26, -22, -18, -16, -10, -9, -6, -6, -2, -1, 2, 2, 3, 3, 5, 10, 10, 13, 13, 14, 17, 17, 17, 18, 19, 26, 26, 26, 27, 28, 30, 33, 35, 36, 37, 42, 45, 46, 48, 48, 51, 52, 53, 57, 60, 62, 63, 64, 68, 68, 71, 73, 80, 81, 93, 93, 93, 94, 96, 99, 104, 109, 113, 117, 120, 120, 121, 126]
194.500 μs (6 allocations: 640 bytes)
Recursive bubble: Int8[-126, -124, -124, -124, -108, -106, -105, -99, -98, -96, -95, -94, -89, -86, -85, -85, -83, -82, -79, -72, -66, -62, -59, -57, -56, -52, -42, -41, -37, -36, -35, -32, -26, -22, -18, -16, -10, -9, -6, -6, -2, -1, 2, 2, 3, 3, 5, 10, 10, 13, 13, 14, 17, 17, 17, 18, 19, 26, 26, 26, 27, 28, 30, 33, 35, 36, 37, 42, 45, 46, 48, 48, 51, 52, 53, 57, 60, 62, 63, 64, 68, 68, 71, 73, 80, 81, 93, 93, 93, 94, 96, 99, 104, 109, 113, 117, 120, 120, 121, 126]
391.400 μs (358 allocations: 26.84 KiB)
Base sort: Int8[-126, -124, -124, -124, -108, -106, -105, -99, -98, -96, -95, -94, -89, -86, -85, -85, -83, -82, -79, -72, -66, -62, -59, -57, -56, -52, -42, -41, -37, -36, -35, -32, -26, -22, -18, -16, -10, -9, -6, -6, -2, -1, 2, 2, 3, 3, 5, 10, 10, 13, 13, 14, 17, 17, 17, 18, 19, 26, 26, 26, 27, 28, 30, 33, 35, 36, 37, 42, 45, 46, 48, 48, 51, 52, 53, 57, 60, 62, 63, 64, 68, 68, 71, 73, 80, 81, 93, 93, 93, 94, 96, 99, 104, 109, 113, 117, 120, 120, 121, 126]
847.761 ns (1 allocation: 160 bytes)