排序
冒泡排序
这是一个简单的排序算法,它反复遍历要排序的列表,比较每对相邻的项目,如果它们的顺序错误则交换它们。重复通过列表直到不需要交换。虽然算法很简单,但对于大多数问题来说它太慢而且不切实际。它具有 O(n2)
的复杂性,但被认为比插入排序慢。
extension Array where Element: Comparable {
func bubbleSort() -> Array<Element> {
//check for trivial case
guard self.count > 1 else {
return self
}
//mutated copy
var output: Array<Element> = self
for primaryIndex in 0..<self.count {
let passes = (output.count - 1) - primaryIndex
//"half-open" range operator
for secondaryIndex in 0..<passes {
let key = output[secondaryIndex]
//compare / swap positions
if (key > output[secondaryIndex + 1]) {
swap(&output[secondaryIndex], &output[secondaryIndex + 1])
}
}
}
return output
}
}
插入排序
插入排序是计算机科学中更基本的算法之一。插入排序通过迭代集合对元素进行排名,并根据元素的值定位元素。该集合分为有序和未分类的一半,并重复,直到所有元素都被排序。插入排序具有 O(n2)
的复杂度。你可以将其放在扩展名中,如下面的示例所示,或者你可以为其创建方法。
extension Array where Element: Comparable {
func insertionSort() -> Array<Element> {
//check for trivial case
guard self.count > 1 else {
return self
}
//mutated copy
var output: Array<Element> = self
for primaryindex in 0..<output.count {
let key = output[primaryindex]
var secondaryindex = primaryindex
while secondaryindex > -1 {
if key < output[secondaryindex] {
//move to correct position
output.remove(at: secondaryindex + 1)
output.insert(key, at: secondaryindex)
}
secondaryindex -= 1
}
}
return output
}
}
选择排序
选择排序因其简单性而着称。它从数组中的第一个元素开始,将其值保存为最小值(或最大值,具体取决于排序顺序)。然后它通过数组进行迭代,并将 min 值替换为在路上找到的 min 之后的任何其他值。然后将该最小值放在数组的最左边部分,并从下一个索引重复该过程,直到数组结束。选择排序具有 O(n2)
的复杂度,但它被认为比它的对应物慢 - 选择排序。
func selectionSort()
- > Array {//检查琐碎的案例保护 self.count> 1 else {return self}
//mutated copy
var output: Array<Element> = self
for primaryindex in 0..<output.count {
var minimum = primaryindex
var secondaryindex = primaryindex + 1
while secondaryindex < output.count {
//store lowest value as minimum
if output[minimum] > output[secondaryindex] {
minimum = secondaryindex
}
secondaryindex += 1
}
//swap minimum value with array iteration
if primaryindex != minimum {
swap(&output[primaryindex], &output[minimum])
}
}
return output
}
快速排序 - O(n log n)复杂时间
Quicksort 是一种先进的算法。它具有 O(n log n)的时间复杂度,并采用分而治之的策略。这种组合产生了先进的算法性能。Quicksort 首先将一个大数组分成两个较小的子数组:低元素和高元素。Quicksort 然后可以递归地对子数组进行排序。
步骤是:
从数组中选择一个称为 pivot 的元素。
对数组重新排序,使得值小于 pivot 的所有元素都在 pivot 之前,而值大于 pivot 的所有元素都在它之后(相同的值可以是任意一种)。在此分区之后,枢轴处于其最终位置。这称为分区操作。
递归地将上述步骤应用于具有较小值的元素的子数组,并分别应用于具有较大值的元素的子数组。
mutating func quickSort()
- > Array {
func qSort(start startIndex: Int, _ pivot: Int) {
if (startIndex < pivot) {
let iPivot = qPartition(start: startIndex, pivot)
qSort(start: startIndex, iPivot - 1)
qSort(start: iPivot + 1, pivot)
}
}
qSort(start: 0, self.endIndex - 1)
return self
}
mutating func qPartition(start startIndex: Int, _ pivot: Int) -> Int {
var wallIndex: Int = startIndex
//compare range with pivot
for currentIndex in wallIndex..<pivot {
if self[currentIndex] <= self[pivot] {
if wallIndex != currentIndex {
swap(&self[currentIndex], &self[wallIndex])
}
//advance wall
wallIndex += 1
}
}
//move pivot to final position
if wallIndex != pivot {
swap(&self[wallIndex], &self[pivot])
}
return wallIndex
}