为什么面试官对我在 Swift 4 中的 QuickSort 实现不满意？

Question

昨天，在一次初级 iOS 开发人员的面试中，我被要求实现 QuickSort 算法。

我写了这个：

func sort<T: Comparable>(_ array: Array<T>) -> Array<T> {

    let arraySize = array.count

    guard arraySize > 1 else { return array }

    let pivot = array[arraySize / 2]

    var less = [T]()
    var equal = [T]()
    var greater = [T]()

    for element in array {

        if element < pivot {
            less.append(element)
        } else if element > pivot {
            greater.append(element)
        } else {
            equal.append(element)
        }

    }

    return sort(less) + equal + sort(greater)

}

他们说这不是 QuickSort，而是它的一些 quicksortish 版本。 尽管我要求他们解释，他们还是建议回家寻找真正的算法。

如果你是面试官，你会对我的代码有何评价？

Answer 1

我看到的唯一主要问题是您正在为每次交换创建新的数组。所以你的内存使用量将是 m^2 而不是数组。除此之外，我没有发现它有什么大问题，但我已经有一段时间没有使用快速排序了。

Answer 2

你应该就地做。选择最后一项作为枢轴，将所有小于枢轴的项放在左侧，将其他相等且更大的项放在右侧，然后将枢轴放在其位置。

您可以选择任何项目作为枢轴，但您应该在每次迭代时将枢轴放在正确的位置，并且小于枢轴的数字应位于左侧，其他数字应位于右侧。

func quickSort<T: Comparable>(array: inout [T]) {
    quickSort(array: &array, startIndex: 0, endIndex: array.count-1)
}

func quickSort<T: Comparable>(array: inout [T], startIndex: Int, endIndex: Int) {
    if startIndex >= endIndex {
        return
    }
    let itemIndex = partition(array: &array, startIndex: startIndex, endIndex: endIndex)
    quickSort(array: &array, startIndex: startIndex, endIndex: itemIndex-1)
    quickSort(array: &array, startIndex: itemIndex+1, endIndex: endIndex)
}

func partition<T: Comparable>(array: inout [T], startIndex: Int, endIndex: Int) -> Int {
    var i = startIndex
    for index in startIndex..<endIndex {
        if array[index] < array[endIndex] {
            array.swapAt(i, index)
            i += 1
        }
    }
    array.swapAt(i, endIndex)
    return i
}

Answer 3

你应该使用数组过滤器而不是“for in循环”：

public func quickSort<T: Comparable>(_ a: [T]) -> [T] {
    guard a.count > 1 else {
        return a
    }
    let pivot = a[a.count / 2]
    let less = a.filter { $0 < pivot }
    let equal = a.filter { $0 == pivot }
    let greater = a.filter { $0 > pivot }
    return quickSort(less) + equal + quickSort(greater)
}