盒子
盒子
文章目录
  1. 实现步骤
  2. 实现
  3. 优化
  4. 总结

算法(二)冒泡排序

冒泡排序主要是相邻的两个数两两进行比较,拿从小到大说明,进行冒泡排序后会将大的数到底部,将小得数到顶部。所以冒泡说法由此得名。

实现步骤

以从小到大为例,排序数组大小为n

  1. N = 0趟排序开始都从a[0]开始与其下面的相邻的数进行比较,如果大于相邻的数则交换他们的位置。
  2. 继续与下一个相邻的数进行比较,大于相邻的就交换,最后进行比较n-1次后,第N = 0趟排序结束,最大的数就在数组的a[n-1]处。
  3. 重复前面的步骤,直到 N = n-1,排序结束。

根据思想实现就不难了

实现

1
2
3
4
5
6
7
8
9
10
11
public static void bubbleSort(int[] arr) {
int temp;
for (int n = 0; n < arr.length - 1; n++)//需要n-1次
for (int j = 0; j < arr.length - n - 1; j++) {
if (arr[j] > arr[j + 1]) {//交换
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}

实现完之后我们是否心中有点疑问,因为他要逐个比较,如果数组后面的一些数是有序的呢,是否可以减少排序的次数呢?结果是肯定的,例如,我们数组后面的30个数是已经排好序的,那么我们在排序的时候就可以直接忽略后面的数,只考虑他们前面的,所以我们在排序的时候可以设计个标识flag,当从第j开始都没有进行数据的交换,即有序。那么我们就可以把原来的数据切段只对j前面的数继续比较,相对于形成新的排序数组。这样就对原来的排序进行了一些优化。

优化

根据上面的思想,我们可以这样修改代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void bubbleSort2(int[] arr) {
int temp;
int flag = arr.length - 1;
while (flag > 0) {
int n = flag;
flag = 0;
for (int j = 0; j < n; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = j;
}
}
}
}

总结

根据前面的思想我们会知道该排序为稳定排序,最好的时间复杂度为O(n)即排序数组开始就是有序的且与要排序的顺序相同,因此只要进行一趟比较排序,遍历一次数组。最坏的情况自然是数组开始时与要排序的顺序相反,所以时间复杂度为O(n^2)

转载请指明出处 idisfkj博客:https://idisfkj.github.io

支持一下
赞赏是一门艺术