时间戳

首页 > 解决方案 > 使用自定义对象实现计数排序

swift - 使用自定义对象实现计数排序

问题描述

我想实现计数排序，但想用自定义对象来实现。这是在 Swift 中，但实现细节并不太重要。

我想对一个基本上只包含一个整数（键）和一个字符的对象进行排序。

class ToSort : CustomStringConvertible {
    var description: String {
        return String(num)
    }
    var num : Int
    var val : Character
    init(_ num: Int, _ val : Character)  {
        self.num = num
        self.val = val
    }
}

现在通常存储整数的频率（https://www.geeksforgeeks.org/counting-sort/）。我想存储我的对象 - 我不知道该怎么做。我花了一些时间寻找实现（使用自定义对象 - 我在上面有一个标准实现的链接），找不到一个并且无法弄清楚我应该如何实现这个......

我想我可以通过实现一个字典（哈希图）来做到这一点，但如果我这样做，那么使用计数排序的优势就消失了吗？

标签： swiftalgorithm

解决方案

您可以尝试这个算法，我实现它以使用自定义对象可能会让您了解它是如何完成的，

struct Foo {
    var number: Int
    var name: String
}

enum CountingSortError: Error {
    case arrayEmpty
}

func countingSort(array: [Foo]) throws -> [Foo] {
    guard array.count > 0 else {
        throw CountingSortError.arrayEmpty
    }

    // Step 1
    // Create an array to store the count of each element
    let maxElement = array.max{ a, b in a.number < b.number } ?? Foo(number: 0, name: "Zero")
    var countArray = [Int](repeating: 0, count: Int(maxElement.number + 1))
    for element in array {
        countArray[element.number] += 1
    }

    // Step 2
    // Set each value to be the sum of the previous two values
    for index in 1 ..< countArray.count {
        let sum = countArray[index] + countArray[index - 1]
        countArray[index] = sum
    }

    print(countArray)
    // Step 3
    // Place the element in the final array as per the number of elements before it
    let count = array.count
    var sortedArray = [Foo](repeating: Foo(number: 0, name: ""), count: count)
     sortedArray = array.sorted(by: { (a, b) -> Bool in
    countArray[a.number] -= 1
    return a.number < b.number
    })
    return sortedArray
}

用法：

print(try countingSort(array: [Foo(number: 10, name: ""), Foo(number: 9, name: ""), Foo(number: 8, name: ""), Foo(number: 7, name: ""), Foo(number: 1, name: ""), Foo(number: 2, name: ""), Foo(number: 7, name: ""), Foo(number: 3, name: "")]).flatMap {$0.number})

输出

  count [0, 1, 2, 3, 3, 3, 3, 5, 6, 7, 8]
  sorted [1, 2, 3, 7, 7, 8, 9, 10]

基本算法代码

推荐阅读