仅以数组作为输入的递归排序

Question

我已经编写了一些简短的递归程序，现在正在递归地进行排序。到目前为止我一直在使用 2 个输入：数组和索引。有没有一种只需要数组作为输入的递归排序方法？我认为冒泡排序可以解决这个问题，但它也使用索引来跟踪位置。

如果有人想知道，我有一个硬件来进行递归排序（我已经这样做了，使用数组和索引），这只是为了看看是否可以在没有索引的情况下完成它。

Answer 1

我相信可以仅使用数组作为参数来执行递归合并排序：
http://en.wikipedia.org/wiki/Merge_sort

编辑：
我想你可以像这样跳过索引：

function bubble_sort(arr)
{
    for (i=0 to arr.length-1)
    {
        if(arr[i] > arr[i+1])
        {
            swap(arr, i);
            return bubble_sort(arr);
        }
    }
    return arr;
}

这不是完美的冒泡排序，因为起始索引始终为零。复杂度仍然是O(n^2)。如果您愿意克隆数组（并浪费大量内存），那么您可以替换

return bubble_sort(arr);

为：

return combineArrays(arr.subArray(0, i), bubble_sort(arr.subArray(i, n)));

然后，这是一种仅以数组作为参数实现递归冒泡排序的有效但浪费的方法。