quicksort 相关问题

Quicksort是由C. A. R. Hoare发明的排序算法，其平均情况复杂度为O（n log n）和最坏情况二次复杂度。它是最快的通用排序算法之一。

我的印象是随机数据导致快速排序退化的概率呈指数级小，但找不到公式。当然，已经排序的数据会导致天真的快速......

algorithm probability quicksort denial-of-service introsort

回答 1 投票 0

昨天，在一次初级 iOS 开发人员的面试中，我被要求实现 QuickSort 算法。我写了这个： func sort(_ array: Array) -> Array 昨天，在一次初级 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 版本。尽管我要求他们解释，他们还是建议回家寻找真正的算法。如果你是面试官，你会对我的代码有何评价？我看到的唯一主要问题是您正在为每次交换创建新的数组。所以你的内存使用量将是 m^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 } 你应该使用数组过滤器而不是“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) }

swift quicksort

回答 3 投票 0

使用 ForkJoin 实现 Stackoverflow 和 Quicksort Java 实现

我一直在尝试使用Java中的ForkJoin进行快速排序，而在大部分情况下，当数组的每个元素相等时，我会得到一个堆栈溢出。导入 java.util.Comparator; 导入j...

java multithreading sorting quicksort fork-join

回答 1 投票 0

Verilog HDL 快速排序错误：在终止条件中必须仅使用常量表达式

我正在尝试在 Quartus II 中运行此 Verilog 代码，但由于 for 它不起作用。模块 verilog_qs( 输入线时钟，输入线 [10:0] in1, in2, in3, in4, in5, in6, in7, in8, in9, in...

verilog quicksort quartus

回答 1 投票 0

单一函数的快速排序算法

公共静态无效排序（int [] a）{ if (a.length>1){ int 枢轴=a[a.length-1]; 左整数=0； int right=a.length-1; 同时（左<=right){ ...