swift - 这种排序算法存在吗？ (在 Swift 中实现)

Question

这可能是个糟糕的问题，但我很好奇。

我在网上学习了一些数据结构和算法类(class)，我遇到了选择排序、插入排序、冒泡排序、归并排序、快速排序、堆排序等算法。它们几乎从未接近 O(n)当数组反向排序时。

我想知道一件事:为什么我们不使用空间来换取时间？

当我整理东西时，我会拿起一个，然后把它放在它所属的地方。所以我想如果我们有一个项目数组，我们可以将每个值放入具有该值的索引中。

这是我在 Swift 4 中的实现:

let simpleArray = [5,8,3,2,1,9,4,7,0]
let maxSpace = 20

func spaceSort(array: [Int]) -> [Int] {
    guard array.count > 1 else {
        return array
    }
    var realResult = [Int]()
    var result = Array<Int>(repeating: -1, count: maxSpace)

    for i in 0..<array.count{
        if(result[array[i]] != array[i]){
            result[array[i]] = array[i]
        }
    }
    for i in 0..<result.count{
        if(result[i] != -1){
            realResult.append(i)
        }
    }
    return realResult
}

var spaceSorted = [Int]()

var execTime = BenchTimer.measureBlock {
    spaceSorted = spaceSort(array: simpleArray)
}
print("Average execution time for simple array: \(execTime)")
print(spaceSorted)

我得到的结果:

这个排序算法是否已经存在？

这是一个坏主意，因为它只采用唯一值并丢失重复项吗？或者它有什么用处？

为什么我不能将 Int.max 用于 maxSpace？

编辑:我收到以下错误

error: Execution was interrupted.

当我使用 let maxSpace = Int.max 时

MyPlayground(6961,0x7000024af000) malloc: Heap corruption detected, free list is damaged at 0x600003b7ebc0 * Incorrect guard value: 0 MyPlayground(6961,0x7000024af000) malloc: * set a breakpoint in malloc_error_break to debug

感谢您的回答

Answer 1

这是基数排序的一个极端版本。引自 Wikipedia :

radix sort is a non-comparative sorting algorithm. It avoids comparison by creating and distributing elements into buckets according to their radix. For elements with more than one significant digit, this bucketing process is repeated for each digit, while preserving the ordering of the prior step, until all digits have been considered. For this reason, radix sort has also been called bucket sort and digital sort.

在这种情况下，您将基数选择为 maxSpace，因此您没有任何“具有超过一位有效数字的元素”(来自上面的引用)。

现在，如果您使用哈希集数据结构而不是数组，您实际上不需要为整个范围分配空间。你仍然会保留所有循环迭代(从 0 到 maxSpace)，它会检查哈希集是否包含 i(循环变量)的值，并且如果是，输出它。

只有当 maxSpace 的数量级与输入数组中的元素数量相同时，这才是有效的算法。其他排序算法可以用 O(nlogn) 时间复杂度进行排序，所以对于 maxSpace 远大于 nlogn 的情况，算法不是那个引人注目。