Links

06.冒泡排序

一、 常规冒泡

func bubbleSortA(nums: [Int]) -> [Int] {
var nums = nums
let count = nums.count
for i in 0..<count {
print("<")
for j in (i + 1)..<count {
if nums[i] > nums[j] {
nums.swapAt(i, j)
}
print(nums)
}
print(">\n")
}
return nums
}

二、 外层优化

当发现在某一趟排序中没有发生交换,则说明排序已经完成,所以可以在此趟排序后结束排序,在每趟排序前设置flag,当其未发生变化时,终止算法
func bubbleSortB(nums: [Int]) -> [Int] {
print("bubbleSortB")
var nums = nums
let count = nums.count
for i in 0..<count {
var swapFlag = true
print("<")
for j in (i + 1)..<count {
if nums[i] > nums[j] {
nums.swapAt(i, j)
swapFlag = false
}
print(nums)
}
print(">\n")
if swapFlag {
break
}
}
return nums
}

三、 内层优化

在每趟排序中,右面的许多元素已经是有序的结果了,可算法还是进行后面数值的排序,因此进行第二次优化
func bubbleSortC(nums: [Int]) -> [Int] {
print("bubbleSortC")
var nums = nums
var boundary = nums.count - 1
var lastSwapIdx = 0
for _ in 0..<nums.count {
var swapFlag = true
print("<")
for j in 0..<boundary {
if nums[j] > nums[j+1] {
nums.swapAt(j, j+1)
swapFlag = false
lastSwapIdx = j
}
print(nums)
}
print(">\n")
boundary = lastSwapIdx
if swapFlag {
break
}
}
return nums
}

四、 对比

let numbers: [Int] = [3, 5, 1, 11, 2, 4, 12]
bubbleSortA(nums: numbers)
bubbleSortB(nums: numbers)
bubbleSortC(nums: numbers)
输出:
<
[3, 5, 1, 11, 2, 4, 12]
[1, 5, 3, 11, 2, 4, 12]
[1, 5, 3, 11, 2, 4, 12]
[1, 5, 3, 11, 2, 4, 12]
[1, 5, 3, 11, 2, 4, 12]
[1, 5, 3, 11, 2, 4, 12]
>
<
[1, 3, 5, 11, 2, 4, 12]
[1, 3, 5, 11, 2, 4, 12]
[1, 2, 5, 11, 3, 4, 12]
[1, 2, 5, 11, 3, 4, 12]
[1, 2, 5, 11, 3, 4, 12]
>
<
[1, 2, 5, 11, 3, 4, 12]
[1, 2, 3, 11, 5, 4, 12]
[1, 2, 3, 11, 5, 4, 12]
[1, 2, 3, 11, 5, 4, 12]
>
<
[1, 2, 3, 5, 11, 4, 12]
[1, 2, 3, 4, 11, 5, 12]
[1, 2, 3, 4, 11, 5, 12]
>
<
[1, 2, 3, 4, 5, 11, 12]
[1, 2, 3, 4, 5, 11, 12]
>
<
[1, 2, 3, 4, 5, 11, 12]
>
<
>
bubbleSortB
<
[3, 5, 1, 11, 2, 4, 12]
[1, 5, 3, 11, 2, 4, 12]
[1, 5, 3, 11, 2, 4, 12]
[1, 5, 3, 11, 2, 4, 12]
[1, 5, 3, 11, 2, 4, 12]
[1, 5, 3, 11, 2, 4, 12]
>
<
[1, 3, 5, 11, 2, 4, 12]
[1, 3, 5, 11, 2, 4, 12]
[1, 2, 5, 11, 3, 4, 12]
[1, 2, 5, 11, 3, 4, 12]
[1, 2, 5, 11, 3, 4, 12]
>
<
[1, 2, 5, 11, 3, 4, 12]
[1, 2, 3, 11, 5, 4, 12]
[1, 2, 3, 11, 5, 4, 12]
[1, 2, 3, 11, 5, 4, 12]
>
<
[1, 2, 3, 5, 11, 4, 12]
[1, 2, 3, 4, 11, 5, 12]
[1, 2, 3, 4, 11, 5, 12]
>
<
[1, 2, 3, 4, 5, 11, 12]
[1, 2, 3, 4, 5, 11, 12]
>
<
[1, 2, 3, 4, 5, 11, 12]
>
bubbleSortC
<
[3, 5, 1, 11, 2, 4, 12]
[3, 1, 5, 11, 2, 4, 12]
[3, 1, 5, 11, 2, 4, 12]
[3, 1, 5, 2, 11, 4, 12]
[3, 1, 5, 2, 4, 11, 12]
[3, 1, 5, 2, 4, 11, 12]
>
<
[1, 3, 5, 2, 4, 11, 12]
[1, 3, 5, 2, 4, 11, 12]
[1, 3, 2, 5, 4, 11, 12]
[1, 3, 2, 4, 5, 11, 12]
>
<
[1, 3, 2, 4, 5, 11, 12]
[1, 2, 3, 4, 5, 11, 12]
[1, 2, 3, 4, 5, 11, 12]
>
<
[1, 2, 3, 4, 5, 11, 12]
>