这种排序算法存在吗？ （在 Swift 中实现）
Does this sorting algorithm exist? (implemented in Swift)
这可能是个糟糕的问题，但我很好奇。
我在网上学习了一些数据结构和算法课程，遇到了选择排序、插入排序、冒泡排序、归并排序、快速排序、堆排序等算法。它们几乎从未接近 O( n) 当数组反向排序时。
我想知道一件事：为什么我们没有在 return 的时间内使用 space？
当我整理东西时，我会拿起一个，把它放在它所属的地方。所以我想如果我们有一个项目数组，我们可以将每个值放入具有该值的索引中。
这是我在 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
感谢您的回答
这是基数排序的极端版本。引自 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，因此您没有任何 "elements with more than one significant digit"（来自上面的引述）。
现在，如果您要使用哈希集数据结构而不是数组，您实际上不需要为整个范围分配 space。你仍然会保留所有循环迭代（从 0 到 maxSpace），并且它会检查哈希集是否包含 i（循环变量）的值，并且如果是，输出它。
只有当 maxSpace 与输入数组中的元素数量数量级相同时，这才是有效的算法。其他排序算法可以用 O(nlogn) 时间复杂度排序，所以对于 maxSpace 远大于 nlogn 的情况，该算法没有那么引人注目。
这可能是个糟糕的问题，但我很好奇。
我在网上学习了一些数据结构和算法课程，遇到了选择排序、插入排序、冒泡排序、归并排序、快速排序、堆排序等算法。它们几乎从未接近 O( n) 当数组反向排序时。
我想知道一件事：为什么我们没有在 return 的时间内使用 space？
当我整理东西时，我会拿起一个，把它放在它所属的地方。所以我想如果我们有一个项目数组，我们可以将每个值放入具有该值的索引中。
这是我在 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
感谢您的回答
这是基数排序的极端版本。引自 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，因此您没有任何 "elements with more than one significant digit"（来自上面的引述）。
现在，如果您要使用哈希集数据结构而不是数组，您实际上不需要为整个范围分配 space。你仍然会保留所有循环迭代（从 0 到 maxSpace），并且它会检查哈希集是否包含 i（循环变量）的值，并且如果是，输出它。
只有当 maxSpace 与输入数组中的元素数量数量级相同时，这才是有效的算法。其他排序算法可以用 O(nlogn) 时间复杂度排序，所以对于 maxSpace 远大于 nlogn 的情况，该算法没有那么引人注目。