小学生都能学会的冒泡排序
作者 | 小K
故事起源
从首位置开始，依次比较前后两个数，如果前面的数比后面的数大，就交换两个数。这样第1轮结束后，最大的数就会移动到最后的位置。对剩余元素重复执行N-1次，整个数组有序。因为像空气上浮到水面，最大的元素会慢慢浮到最后，所以冒泡因此得名。
for (
int i =
0; i < n -
1; ++i) {
for (
int j =
0; j < n - i -
1; ++j) {
if (a[j] > a[j +
1]) {
swap(a[j], a[j +
1]);
}
}
}
改进点1：
如果某一轮没有发生过交换，说明数组已经有序，那么以后也不会发生交换，此时可以终止迭代。
for (
int i =
0; i < n -
1; ++i) {
// flag标记是否有交换
bool flag =
true;
for (
int j =
0; j < n - i -
1; ++j) {
if (a[j] > a[j +
1]) {
swap(a[j], a[j +
1]);
flag =
false;
}
}
if (flag) {
break;
}
}
记录每一次最后发生交换的位置，下一轮只需要扫描到此位置的前一个即可。
// 记录最后交换的位置
int position =
0;
int len = n -
1;
for (
int i =
0; i < n -
1; ++i) {
// flag标记是否有交换
bool flag =
true;
for (
int j =
0; j < len; ++j) {
if (a[j] > a[j +
1]) {
swap(a[j], a[j +
1]);
flag =
false;
position = j;
}
}
len = position;
if (flag) {
break;
}
}
来源：小K算法
原标题：图解算法：冒泡排序
编辑：hxg
近期热门文章Top10