算法:优化冒泡排序
2018-10-23 本文已影响3人
小码侠
之前我们已经聊过 冒泡排序
,但是当我们的元素列表中如果存在了一批已经排好序的数据,冒泡排序还是会坚挺的执行下去。造成资源的浪费,针对这种情况我们来优化一下。
如需要对以下数据排序:
{5, 2, 4, 3, 1, 6 ,7 ,8 ,9 ,10 }
原始冒泡排序效果
第 1 次
- [2 5 4 3 1 6 7 8 9 10]
- [2 4 5 3 1 6 7 8 9 10]
- [2 4 3 5 1 6 7 8 9 10]
- [2 4 3 1 5 6 7 8 9 10]
- [2 4 3 1 5 6 7 8 9 10]
- [2 4 3 1 5 6 7 8 9 10]
- [2 4 3 1 5 6 7 8 9 10]
- [2 4 3 1 5 6 7 8 9 10]
- [2 4 3 1 5 6 7 8 9 10]
第 2 次
- [2 4 3 1 5 6 7 8 9 10]
- [2 3 4 1 5 6 7 8 9 10]
- [2 3 1 4 5 6 7 8 9 10]
- [2 3 1 4 5 6 7 8 9 10]
- [2 3 1 4 5 6 7 8 9 10]
- [2 3 1 4 5 6 7 8 9 10]
- [2 3 1 4 5 6 7 8 9 10]
- [2 3 1 4 5 6 7 8 9 10]
第 3 次
- [2 3 1 4 5 6 7 8 9 10]
- [2 1 3 4 5 6 7 8 9 10]
- [2 1 3 4 5 6 7 8 9 10]
- [2 1 3 4 5 6 7 8 9 10]
- [2 1 3 4 5 6 7 8 9 10]
- [2 1 3 4 5 6 7 8 9 10]
- [2 1 3 4 5 6 7 8 9 10]
第 4 次
从第四次开始,排序已经没有效果了。
- [1 2 3 4 5 6 7 8 9 10]
- [1 2 3 4 5 6 7 8 9 10]
- [1 2 3 4 5 6 7 8 9 10]
- [1 2 3 4 5 6 7 8 9 10]
- [1 2 3 4 5 6 7 8 9 10]
- [1 2 3 4 5 6 7 8 9 10]
第 5 次
- [1 2 3 4 5 6 7 8 9 10]
- [1 2 3 4 5 6 7 8 9 10]
- [1 2 3 4 5 6 7 8 9 10]
- [1 2 3 4 5 6 7 8 9 10]
- [1 2 3 4 5 6 7 8 9 10]
第 6 次
- [1 2 3 4 5 6 7 8 9 10]
- [1 2 3 4 5 6 7 8 9 10]
- [1 2 3 4 5 6 7 8 9 10]
- [1 2 3 4 5 6 7 8 9 10]
第 7 次
- [1 2 3 4 5 6 7 8 9 10]
- [1 2 3 4 5 6 7 8 9 10]
- [1 2 3 4 5 6 7 8 9 10]
第 8 次
- [1 2 3 4 5 6 7 8 9 10]
- [1 2 3 4 5 6 7 8 9 10]
第 9 次
- [1 2 3 4 5 6 7 8 9 10]
优化后效果
第 1 次
- [2
5
4 3 1 6 7 8 9 10] - [2 4
5
3 1 6 7 8 9 10] - [2 4 3
5
1 6 7 8 9 10] - [2 4 3 1
5
6 7 8 9 10] - [2 4 3 1 5 6 7 8 9 10]
- [2 4 3 1 5 6 7 8 9 10]
- [2 4 3 1 5 6 7 8 9 10]
- [2 4 3 1 5 6 7 8 9 10]
- [2 4 3 1 5 6 7 8 9 10]
第 2 次
- [2
4
3 1 5 6 7 8 9 10] - [2 3
4
1 5 6 7 8 9 10] - [2 3 1
4
5 6 7 8 9 10]
第 3 次
- [2
3
1 4 5 6 7 8 9 10] - [2 1
3
4 5 6 7 8 9 10]
第 4 次
- [1
2
3 4 5 6 7 8 9 10]
代码实现
package main
import "fmt"
func main() {
//声明数组
numbers := []int{5, 2, 4, 3, 1, 6, 7, 8, 9, 10}
length := len(numbers)
lastSwap := length
count:=0
//构建遍历循环
for i := 0; i < length-1; i++ {
fmt.Printf("**第 %d 次**\n\n", count+1)
count++
for j := 0; j < length-i-1; j++ {
//fmt.Println(i,j)
//对比两个相邻元素
if numbers[j] > numbers[j+1] {
//如果如果第一个比第二个大,就交换它们的位置。 【顺序】
//倒序反之:如果第一个比第二个小,就交换它们的位置。
numbers[j+1], numbers[j] = numbers[j], numbers[j+1]
//记录最后交换的位置。因为从零开始,所以加1
lastSwap = j+1
}
fmt.Printf("%d. %v\n", j+1, numbers)
}
fmt.Println("")
//如果长度和最后位置不匹配,意味着还有数据进行交换。
if length!=lastSwap {
length = lastSwap //交换位置。
i=-1 //重置外层循环,因为接下来会有`i++`,所以设置为 `-1`
}
}
}
PHP
<?php
$numbers = array(5, 2, 4, 3, 1, 6, 7, 8, 9, 10);
$len = count($numbers);
$last = $len;
//构建遍历循环
for ($i = 0; $i < $len - 1; $i++) {
for ($j = 0; $j < $len - $i - 1; $j++) {
//对比两个相邻元素
if ($numbers[$j] > $numbers[$j + 1]) {
//如果如果第一个比第二个大,就交换它们的位置。 【顺序】
//倒序反之:如果第一个比第二个小,就交换它们的位置。
list($numbers[$j + 1], $numbers[$j]) = array($numbers[$j], $numbers[$j + 1]);
$last = $len;
}
}
//如果长度和最后位置不匹配,意味着还有数据进行交换。
if ($last != $len) {
$len = $last;
$i = -1;//重置外层循环,因为接下来会有`i++`,所以设置为 `-1`
}
}
print_r($numbers);
/*
Array
(
[0] => 1
[1] => 2
[2] => 3
[3] => 4
[4] => 5
[5] => 6
[6] => 7
[7] => 8
[8] => 9
[9] => 10
)
*/
JS
let numbers = [5, 2, 4, 3, 1, 6, 7, 8, 9, 10];
let len = numbers.length;
let last = len;
//构建遍历循环
for (let i = 0; i < len - 1; i++) {
for (let j = 0; j < len - i - 1; j++) {
//对比两个相邻元素
if (numbers[j] > numbers[j + 1]) {
//如果如果第一个比第二个大,就交换它们的位置。 【顺序】
//倒序反之:如果第一个比第二个小,就交换它们的位置。
//解构交换位置
[numbers[j + 1], numbers[j]] = [numbers[j], numbers[j + 1]];
last = j + 1;
}
}
if (last != len) {
len = last;
i = -1;
}
}
console.log(numbers);
// [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
Python
# -*- coding: UTF-8 -*-
numbers = [5, 2, 4, 3, 1, 6, 7, 8, 9, 10]
length = len(numbers)
last = length
while 1 == 1:
swapFlag = False # 记录是否交换过
for i in range(length - 1):
for j in range(length - i - 1):
"""
如果如果第一个比第二个大,就交换它们的位置。 【顺序】
倒序反之:如果第一个比第二个小,就交换它们的位置。
"""
if numbers[j] > numbers[j + 1]:
numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]
last = j + 1
swapFlag = True
if length != last:
length = last
break
if not swapFlag: # 已经没有数据可以交换了。直接退出。
break
print(numbers)
# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
微信搜索:小码侠
长按二维码关注我们