Julia 中的合并排序实现

Question

我正在尝试在 Julia 中实现合并排序算法，但我似乎无法理解该算法所需的递归步骤。我的代码如下：

\n

m\xe2\x82\x90 = [1, 10, 7, 4, 3, 6, 8, 2, 9]\n\nb\xe2\x82\x81(t, z, half\xe2\x82\x81, half\xe2\x82\x82)= ((t<=length(half\xe2\x82\x81)) && (z<=length(half\xe2\x82\x82))) && (half\xe2\x82\x81[t]<half\xe2\x82\x82[z])\nb\xe2\x82\x82(t, z, half\xe2\x82\x81, half\xe2\x82\x82)= ((z<=length(half\xe2\x82\x82)) && (t<=length(half\xe2\x82\x81)) ) && (half\xe2\x82\x81[t]>half\xe2\x82\x82[z])\n\nfunction Merge(m\xe2\x82\x81, m\xe2\x82\x82)\n    N = length(m\xe2\x82\x81) + length(m\xe2\x82\x82)\n    B = zeros(N)\n\n    i = 1\n    j = 1\n\n    for k in 1:N\n        if b\xe2\x82\x81(i, j, m\xe2\x82\x81, m\xe2\x82\x82)\n            B[k] =  m\xe2\x82\x81[i]\n            i += 1 \n        elseif b\xe2\x82\x82(i, j, m\xe2\x82\x81, m\xe2\x82\x82)\n            B[k] =  m\xe2\x82\x82[j]\n            j += 1\n        elseif j >= length(m\xe2\x82\x82)\n            B[k] =  m\xe2\x82\x81[i]\n            i += 1 \n        elseif i >= length(m\xe2\x82\x81)\n            B[k] = m\xe2\x82\x82[j]\n            j += 1\n        end\n    end\n\n    return B\nend\n\n\nfunction MergeSort(M)\n    if length(M) == 1\n        return M\n    elseif length(M) == 0\n        return nothing\n    end\n    \n    n = length(M)\n    i\xe2\x82\x81 = n \xc3\xb7 2\n    i\xe2\x82\x82 = n - i\xe2\x82\x81 \n    h\xe2\x82\x81 = M[1:i\xe2\x82\x81]\n    h\xe2\x82\x82 = M[i\xe2\x82\x82:end]\n\n    C = MergeSort(h\xe2\x82\x81)\n    D = MergeSort(h\xe2\x82\x82)\n\n    return Merge(C, D)\nend\n\nMergeSort(m\xe2\x82\x90)\n

\n

当 C 成为单个元素时，它总是会卡住，因为它返回它，然后再次拆分它，唯一的解决方案是一旦它成为单个元素，就使其成为循环。然而，这不是递归方法。

\n

解决方案

\n

接受@Sundar R 的回答和建议。这是一个有效的实现

\n

#implementation of MergeSort in julia\n\n# merge function, it joins two ordered arrays and returning one single ordered array\n\nfunction merge(m\xe2\x82\x81, m\xe2\x82\x82)\n    N = length(m\xe2\x82\x81) + length(m\xe2\x82\x82)\n\n    # create a zeros array of the same input type (int64)\n    B = zeros(eltype(m\xe2\x82\x81), N)\n\n    i = 1\n    j = 1\n\n    for k in 1:N\n    \n        if !checkbounds(Bool, m\xe2\x82\x81, i)\n            B[k] = m\xe2\x82\x82[j]\n            j += 1\n        elseif !checkbounds(Bool, m\xe2\x82\x82, j)\n            B[k] =  m\xe2\x82\x81[i]\n            i += 1 \n        elseif m\xe2\x82\x81[i]<m\xe2\x82\x82[j]\n            B[k] =  m\xe2\x82\x81[i]\n            i += 1 \n        else\n            B[k] =  m\xe2\x82\x82[j]\n            j += 1\n                \n        end\n    end\n\n    return B\nend\n\n# merge mergesort, this function recursively orders m/2 sub array given an array M\n\nfunction mergeSort(M)\n\n    # base cases\n    if length(M) == 1\n\n        return M\n\n    elseif length(M) == 0\n\n        return nothing\n        \n    end\n\n    # dividing array in two\n    n = length(M)\n\n    i\xe2\x82\x81 = n \xc3\xb7 2\n        \n    # be careful with the indexes, thank you @Sundar R\n    i\xe2\x82\x82 = i\xe2\x82\x81 + 1 \n    \n    h\xe2\x82\x81 = M[1:i\xe2\x82\x81]\n\n    h\xe2\x82\x82 = M[i\xe2\x82\x82:end]\n\n    # recursively sorting the array \n\n    C = mergeSort(h\xe2\x82\x81)\n\n    D = mergeSort(h\xe2\x82\x82)\n\n    return merge(C, D)\n    \nend\n\n#test the function\n\nm\xe2\x82\x90 = [1, 10, 7, 4, 3, 6, 8, 2, 9]\nb =  mergeSort(m\xe2\x82\x90)\n\nprintln(b)\n

\n

Answer 1

问题在于用于拆分的索引，特别是i\xe2\x82\x82。n - i\xe2\x82\x81是元素的数量数组后半部分中的 i\xe2\x82\x82 = i\xe2\x82\x81 + 1，但不一定是后半部分开始的索引 - 为此您只需要.

\n

对于i\xe2\x82\x82 = n - i\xe2\x82\x81，当 n 为 2 时，即当您归结为[1, 10]要排序的数组时，i\xe2\x82\x81 = n \xc3\xb7 2为 1，并且i\xe2\x82\x82也是 (2 - 1) = 1。因此，您最终不会将其拆分为[1], [10]，而是将其“拆分”为[1], 和[1, 10]，从而无限循环。

\n

一旦你解决了这个问题，就会因为一个小错误而出现一个BoundsErrorfrom ：条件应该检查​​ ，而不是（因为 Julia 使用基于 1 的索引，当Mergeelseif>>=jj == length(m\xe2\x82\x82)）。

\n

其他一些建议：

\n

\n
1. zeros(N)返回一个Float64数组，因此这里的结果将始终是一个浮点数组。我建议zeros(eltype(m\xe2\x82\x81), N)改为。
\n
2. 感觉就像b\xe2\x82\x81并且b\xe2\x82\x82只会使代码复杂化并使其不太清晰，我建议if在那里嵌套一个简单的，一个外部的来检查索引 - 查找checkbounds，例如。checkbounds(Bool, m\xe2\x82\x81, i)- 和一个内在的，看看哪个更大。
\n
3. Julia 约定是对函数使用小写，somerge和mergesort代替MergeandMergeSort
\n

\n