冒泡排序
最常见的排序方法就是冒泡排序,冒泡排序会重复比较两个相邻的元素,如果需要排序,就要执行排序。集合中最大的元素会上升到集合的尾部。
示例
观察如下卡片:
sort1.png
一个完整的冒泡排序算法由以下几步组成:
- 在集合的开始部分,9和4进行比较,需要进行交换,该集合变成
[4, 9, 10, 3]
。 - 接下来比较 9和10,由于 9 小于 10,不需要进行交换。该集合 还是
[4, 9, 10, 3]
。 - 接下来比较 10 和 3,需要进行交换,该集合变为
[4, 9, 3, 10]
经过上述的排序之后,卡片的顺序为
sort2.png
对集合重复以上操作,第二次执行完成时,卡片的顺序为:
sort3.png
重复执行第3次之后:
sort4.png
代码实现
public func bubbleSort<Element>(_ array: inout [Element])
where Element: Comparable {
// 1
guard array.count >= 2 else {
return
}
// 2
for end in (1..<array.count).reversed() {
var swapped = false
// 3
for current in 0..<end {
if array[current] > array[current + 1] {
array.swapAt(current, current + 1)
swapped = true
}
}
// 4
if !swapped {
return
}
}
}
1,如果数组的长度小于2,则没有必要进行排序了。
2,一次冒泡排序会将最大的元素放到集合的最末端,每个回合比较的次数,都会比上一回合的比较次数少一次。
3,每个回合,都会对两个相邻的元素进行比较,如果需要交换位置就进行交换。
4,如果在其中一个回合中,没有发生元素交换,则说明数组已经是有序的,则无需进行下一回合的比较了,直接退出即可。
选择排序
选择排序是在冒泡排序的基础上,减少 交换(swap at)的操作。选择排序在每一回合结束后,会执行交换操作。接下来,你会看到选择排序是如何操作的。
示例
sort5.png在每一回合中,选择排序会找到最小的元素,并把它交换至相应位置:
1,首先,遍历数组,找到最小值3,并和9进行交换,顺序变为
3, 4, 10, 9
2,第二次遍历的时候,从 4开始查找,4是最小值,已经在正确的位置上了,无需进行交换了。
3,第三次遍历是,从10 开始,交换 10 和 9的位置。
sort6.png
实现
public func selectionSort<Element>(_ array: inout [Element])
where Element: Comparable {
guard array.count >= 2 else {
return
}
// 1
for current in 0..<(array.count - 1) {
var lowest = current
// 2
for other in (current + 1)..<array.count {
if array[lowest] > array[other] {
lowest = other
}
}
// 3
if lowest != current {
array.swapAt(lowest, current)
}
}
}
1,在每一个回合中,找到值最小元素的位置,如果其不再正确的位置上,则需要进行调整。
2,在每一个次遍历中,找到最小的元素,并记录下来。
3,如果最小值元素的索引和当前索引不一致,则交换两个元素。
插入排序
插入排序是一个更有用的算法,和冒泡排序、选择排序类似,插入排序平均时间复杂度为O(n²),但是插入排序的性能有所不同,如果更多的数据已经排好序,则排序的效率会更高,在Swift标准库中,当对小于20个元素进行排序时,使用的是插入排序。
示例
插入排序的思想和你在玩牌时,对牌进行整理的思想有点相似。考虑以下情景:
sort7.png
插入排序将会从左到右依次遍历卡牌,然后移动卡牌,直到完全符合排序规则为止。
sort8.png
- 1,第一张牌9,由于没有牌在第一张前面可以用来比较,所以可以忽略第一张牌。
- 2,接下来,用 4 和 9 进行比较,通过将 4 和 9 进行交换,将 4 移到左边。
- 3,通过 10和 9 进行比较,10 不需要进行移动。
- 4,最后,通过 3 和 10, 9,4 进行比较,3 插入到最前面。
public func insertionSortTwo<Element>(_ array: inout [Element]) where Element: Comparable {
guard array.count > 1 else {
return
}
print("Array: \(array)")
for begin in (1..<array.count) {
// 找到要插入的位置
let des = search(begin, array)
print("begin: \(begin), des: \(des)")
// 插入元素
insert(begin, des, &array)
}
}
/*
将 source 位置的元素插入到dest位置
*/
private func insert<Element>(_ source: Int, _ dest: Int, _ sourceArray: inout [Element]) where Element: Comparable{
// 对source处的值进行备份
let e = sourceArray[source]
if dest == source {
print("排序后的Array: \(sourceArray)")
return
}
// 将 [dest, source)区间的元素后移
for i in (dest...source).reversed() where i > 0 {
sourceArray[i] = sourceArray[i - 1]
}
sourceArray[dest] = e
print("排序后的Array: \(sourceArray)")
}
/*
利用二分搜索找到 index位置元素的待插入位置
已经排好序数组的范围时 [0, index)
*/
private func search<Element>(_ index: Int, _ sourceArray: [Element]) -> Int where Element: Comparable {
var begin = 0
var end = index
// 当 begin == end 时,查找结束,这时的 begin 就是插入位置的索引。
while begin < end {
let mid = (begin + end) >> 1
if sourceArray[index] < sourceArray[mid] {
end = mid
} else {
begin = mid + 1
}
}
return begin;
}
最后附上本文的相关代码DataAndAlgorim
网友评论