Swift 冒泡排序及优化
冒泡排序是大家都常用的排序方法
冒泡排序算法的运作如下：（从后往前）
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
冒泡排序是稳定的排序算法
时间复杂度 冒泡排序的最佳时间复杂度为O(n)，即初始状态就是排好序的。 冒泡排序的最坏时间复杂复杂度为O(n2)，即初始状态就是逆序的。 冒泡排序的平均时间复杂复杂度为O(n2)
根据这个原理代码如下:
//冒泡排序
func bubbleSort(_ nums: inout [Int]) {
let n = nums.count
for i in 0..<n {
for j in 0..<(n - 1 - i) {
if nums[j] > nums[j + 1] {
nums.swapAt(j, j + 1)
}
}
}
}
//使用
var nums = [1,3,6,9,0,5,2,4,8,7]
bubbleSort(&nums)
print(nums)
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]冒泡排序优化一： 当发现在某一趟排序中发现没有发生交换，则说明排序已经完成，所以可以在此趟排序后结束排序。在每趟排序前设置flag，当其未发生改变时，终止算法；
代码如下：
//冒泡排序 优化一（外层优化）
func bubbleSort1(_ nums: inout [Int]) {
let n = nums.count
for i in 0..<n {
var flag = true
for j in 0..<(n - 1 - i) {
if nums[j] > nums[j + 1] {
nums.swapAt(j, j + 1)
flag = false
}
}
if flag {
break
}
}
}
//使用
var nums = [1,3,6,9,0,5,2,4,8,7]
bubbleSort1(&nums)
print(nums)
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]冒泡排序优化二： 每趟排序中，最后一次发生交换的位置后面的数据均已有序，所以我们可以记住最后一次交换的位置来减少排序的趟数。
//冒泡排序 优化二（内层优化）
func bubbleSort2(_ nums: inout [Int]) {
let n = nums.count
var swap = 0 //swap变量用来标记循环里最后一次交换的位置
var k = n - 1 //内循环判断条件
for _ in 0..<n {
var flag = true
for j in 0..<k {
if nums[j] > nums[j + 1] {
nums.swapAt(j, j + 1)
flag = false
swap = j
}
}
k = swap
if flag {
break
}
}
}
//使用
var nums = [1,3,6,9,0,5,2,4,8,7]
bubbleSort2(&nums)
print(nums)
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]那么现在用上面的代码做个测试：
1.在排序算法外层排序记录次数
//冒泡排序
func bubbleSort(_ nums: inout [Int]) {
let n = nums.count
var count = 0
for i in 0..<n {
count = I
for j in 0..<(n - 1 - i) {
if nums[j] > nums[j + 1] {
nums.swapAt(j, j + 1)
}
}
}
print(count)
}
//使用
var nums = [1,3,6,7,9,0,5,2,4,8]
bubbleSort(&nums)另外两个算法也一样这么处理，发现简单的冒泡排序外层运行10次，而优化后的代码运行6次。
2.在排序算法内层排序记录次数 直接打印k值和原来的（n - 1 - i）来比较
//冒泡排序 优化二（内层优化）
func bubbleSort2(_ nums: inout [Int]) {
let n = nums.count
var swap = 0 //swap变量用来标记循环里最后一次交换的位置
var k = n - 1 //内循环判断条件
var count = 0
for i in 0..<n {
count = i
var flag = true
for j in 0..<k {
if nums[j] > nums[j + 1] {
nums.swapAt(j, j + 1)
flag = false
swap = j
}
}
k = swap
print("k:",k)
print("n:",n - i - 1)
if flag {
break
}
}
print(count)
}
//使用
var nums2 = [1,3,6,7,9,0,5,2,4,8]
bubbleSort2(&nums2)结果如下：
内层循环次数比较
根据结果可以发现，内层的循环减少的次数还是很多的。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2018.04.03 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
