十大经典排序--冒泡排序及其优化
冒泡排序思路：
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
动画图：
代码：
1public void BubbleSort(int[] arr) {
2 int length = arr.length;
3 //确定排序趟数
4 for (int i = 0; i < length - 1; i++) {
5 //确定比较次数
6 for (int j = 0; j < length - 1 - i; j++) {
7 if (arr[j] > arr[j + 1]) {
8 //交换
9 int tmp = arr[j];
10 arr[j] = arr[j + 1];
11 arr[j + 1] = tmp;
12 }
13 }
14 }
15}
优化一：
思路：假设我们现在排序ar[]={1,2,3,4,5,6,7,8,10,9}这组数据，按照上面的排序方式，第一趟排序后将10和9交换已经有序，接下来的8趟排序就是多余的，什么也没做。
所以我们可以在交换的地方加一个标记，如果那一趟排序没有交换元素，说明这组数据已经有序，不用再继续下去。
代码：
1public void BubbleSort(int[] arr) {
2 int length = arr.length;
3 //确定排序趟数
4 for (int i = 0; i < length - 1; i++) {
5 //是否发生比较
6 boolean flag = false;
7 //确定比较次数
8 for (int j = 0; j < length - 1 - i; j++) {
9 if (arr[j] > arr[j + 1]) {
10 //交换
11 int tmp = arr[j];
12 arr[j] = arr[j + 1];
13 arr[j + 1] = tmp;
14 flag = true;
15 }
16 }
17 //没有发生变化比较 说明已经有序
18 if (!flag) {
19 break;
20 }
21 }
22}
优化二：
思路：优化一仅仅适用于连片有序而整体无序的数据(例如：1， 2，3 ，4 ，7，6，5)。但是对于前面大部分是无序而后边小半部分有序的数据(1，2，5，7，4，3，6，8，9，10)排序效率也不可观
针对这类情况，咱们可以继续优化，即咱们可以记下最后一次交换的位置，后边没有交换，必然是有序的，然后下一次排序从第一个比较到上次记录的位置结束即可
代码：
1public void BubbleSort(int[] arr) {
2 int length = arr.length;
3 int k = length - 1;
4 int pos = 0;//用来记录最后一次交换的位置
5 //确定排序趟数
6 for (int i = 0; i < length - 1; i++) {
7 //是否发生比较
8 boolean flag = false;
9 //确定比较次数
10 for (int j = 0; j < k; j++) {
11 if (arr[j] > arr[j + 1]) {
12 //交换
13 int tmp = arr[j];
14 arr[j] = arr[j + 1];
15 arr[j + 1] = tmp;
16 flag = true;
17 //更新最后一次比较位置
18 pos = j;
19 }
20 }
21 //没有发生变化比较 说明已经有序
22 if (!flag) {
23 break;
24 }
25 //下一次比较到记录位置即可
26 k = pos;
27 }
28}
时间复杂度：O(n2)，优化后最好能达到O(n)
空间复杂度：O(1)
以上仅是个人思路解法，觉得还不错欢迎点赞关注分享
往期精彩推荐