- 冒泡排序
- 一、题目描述
- 二、解题思路及代码实现
- 1、解题思路
- 2、C 代码实现
- 三、提交结果
- 总结
给定一个数组 in，请实现插入排序算法。
示例:
输入: in = [3,4,2,1,5,0]
输出: ret = [0,1,2,3,4,5]
冒泡排序的思想:
内循环：数组从最左边开始，依次比较相邻的元素，如果左侧元素大于右侧元素，则交换两个元素，直到最右侧的元素。这样一轮循环下来，最大元素已经被交换到了最右侧。
外循环：控制内循环。每执行一遍内循环，外循环遍历次数-1，当外循环结束时，数组即完成排序。
优化：增加一个标志，当内循环没有交换任何一个元素的时候，可以退出排序，提前完成排序工作，可以提高效率。
我们可以通过调试查看每次循环的执行结果，来理解冒泡排序：
1、初始状态：
2、第一轮内循环：最大值5已经排好序
i=0：3、4不变，结果： 3, 4, 2 ,1, 5, 0
i=1：4、2交换，结果： 3, 2, 4 ,1, 5, 0
i=2：4、1交换，结果： 3, 2, 1 ,4, 5, 0
i=3：4、5不变，结果： 3, 2, 1 ,4, 5, 0
i=4：5、0交换，结果： 3, 2, 1 ,4, 0, 5
i=5 j=5：结束内循环
3、第二轮内循环：4已经排好序
i=0：3、2交换，结果： 2, 3, 1 ,4, 0, 5
i=1：3、1交换，结果： 2, 1, 3 ,4, 0, 5
i=2：3、4不变，结果： 2, 1, 3 ,4, 0, 5
i=3：4、0交换，结果： 2, 1, 3 ,0, 4, 5
i=4 j=4：结束内循环
4、第三轮内循环：3已经排好序
i=0：2、1交换，结果： 1, 2, 3 ,0, 4, 5
i=1：2、3不变，结果： 1, 2, 3 ,0, 4, 5
i=2：3、0交换，结果： 1, 2, 0 ,3, 4, 5
i=3 j=3：结束内循环
5、第四轮内循环：2已经排好序
i=0：1、2不变，结果： 1, 2, 0 ,3, 4, 5
i=1：2、0交换，结果： 1, 0, 2 ,3, 4, 5
i=2 j=2：结束内循环
6、第五轮内循环：1已经排好序
i=0：0、1交换，结果： 0, 1, 2 ,3, 4, 5
i=1 j=1：结束内循环
7、外循环j等于0退出，此时只有一个最左侧元素，自然是最小值，无需再处理，排序完成。
vector<int> bubble_sort(vector<int> in) {
int flag = true;
int length = in.size();
for (int j = length - 1; j > 0; j--) {
for (int i = 0; i < j; i ) {
if (in.at(i) > in.at(i 1)) {
int tmp = in.at(i 1);
in[i 1] = in[i];
in[i] = tmp;
flag = false;
}
}
if (flag) return in;
flag = true;
}
return in;
}
三、提交结果
无提交结果。
总结冒泡排序算是最基础的一种排序算法，其时间复杂度为O(N*N)，就像水底的气泡，越往上冒，泡泡越大。这个c 版本的冒泡排序是加入了优化算法的，并不一定需要外循环全部执行完才退出，当内循环没有一次元素交换时，就表明所有元素已经排好序了，可以提前退出，结束排序了。
