###冒泡排序
- 冒泡排序的执行流程
- 从头开始以此比较相邻两个元素的大小,每轮比较过后当前轮次最大(或最小)元素会冒泡到最末尾的位置
- 排除尾部已经有序的序列,循环执行冒泡操作直至完毕。
for end in (1...(array.count - 1)).reversed() {
for begin in 0..<end {
cmpCount += 1
if array[begin] > array[begin+1]{
swapCount += 1
let temp = array[begin]
array[begin] = array[begin+1]
array[begin+1] = temp
}
}
}
- 冒泡排序的优化
- 当数组全部有序后,提前终止循环.
for end in (1...(array.count - 1)).reversed() {
var flag = true
for begin in 0..<end {
cmpCount += 1
if array[begin] > array[begin+1]{
swapCount += 1
let temp = array[begin]
array[begin] = array[begin+1]
array[begin+1] = temp
flag = false
}
}
if flag == true {
break
}
}
- 每次排列后尾部已经有序,记录有序元素的位置,减少比较次数
for var end in (1...(array.count - 1)).reversed() {
var lastSwapIndex = 1
for begin in 0..<end {
cmpCount += 1
if array[begin] > array[begin+1]{
let temp = array[begin]
array[begin] = array[begin+1]
array[begin+1] = temp
lastSwapIndex = begin
swapCount += 1
}
}
end = lastSwapIndex
}
-
冒泡排序的稳定性 属于稳定的排序算法,前提是在比较元素大小和交换元素位置时,不使用 <= || >= 运算符
-
冒泡排序的时间复杂度和空间复杂度
- 时间复杂度 采用两轮for循环,时间复杂度为O(n^2)
- 空间复杂度 O(1)
-
原地算法
- 概念:不依赖或依赖少数的额外资源,仅依靠输出覆盖输入
- 空间复杂度为O(1)的算法可以认为是原地算法
- 冒泡排序即位原地算法
代码及单元测试:github.com/yukifeng/su…