- public class BubbleSort {
-
- /**
- * 冒泡排序 顾名思义:每次比较两个数,然后当顺序有错误的时候进行交换。
- * 这样看起来就是慢慢的把最小的冒出水面。
- * 算法实现:也是通过两层for循环进行,最外层的for循环每执行一次就会把 最小的气
- * 泡冒到前面(前面这些是已经排好序的),然后第二次的时候就不去比较这几个了通过外层循环控制。
- * 这样就会大大的减少没用的操作。
- *
- * @param src
- */
- public static void sort(int[] src) {
- int len = src.length;
- //这是最基本的没用任何算法的排序,效率比较低下,有时候会做重复的事情.
- /*for (int i = 0; i < len; i++) {
- for (int j = i + 1; j < len; j++) {
- if (src[j] > src[i]) {
- int temp = src[i];
- src[i] = src[j];
- src[j] = temp;
- }
- }
- }*/
- //采用冒泡算法,最外层从第一个元素开始循环
- for(int i = 0; i < len; i++){
- //从最后面开始进行冒泡,是比较小就往前。
- for(int j = (len-1);j > i;j--){
- //比较小就直接进行交换。
- if(src[j] < src[j-1]){
- int temp = src[j];
- src[j] = src[j-1];
- src[j-1] = temp;
- }
- }
- }
- }
-
- public static void main(String[] args) {
- int[] src = {55,77,33,44,22,1,9,0,3,9,-34,9999,-66};
- sort(src);
- for (int i : src) {
- System.out.print(i);
- System.out.print(" ");
- }
- }
- }
时间复杂度: 最好的时间复杂度(正序):O(n) :(好像是改进过的)。 最差的时间复杂度(反序):O(n^2): 比较次数:(n-1)+(n-2)+(n-3)+....+2+1 也就是 O(n^2). 移动次数:3*比较次数,最坏的情况. 也就是O(n^2)。
- 10000
- name: 冒泡排序1 花费了 = 183ms
- name: 冒泡排序2 花费了 = 36ms
- name: 冒泡排序3 花费了 = 29ms
- name: 冒泡排序4 花费了 = 169ms
- name: 冒泡排序5 花费了 = 31ms
-
- 平均大概是89
-
- 50000
- name: 冒泡排序1 花费了 = 5090ms
- name: 冒泡排序2 花费了 = 833ms
- name: 冒泡排序3 花费了 = 757ms
- name: 冒泡排序4 花费了 = 5125ms
- name: 冒泡排序5 花费了 = 744ms
-
- 平均 2509
-
-
- 100000
- name: 冒泡排序1 花费了 = 20694ms
- name: 冒泡排序2 花费了 = 3338ms
- name: 冒泡排序3 花费了 = 3120ms
- name: 冒泡排序4 花费了 = 20862ms
- name: 冒泡排序5 花费了 = 3103ms
-
- 平均:10223
可以看出来和选择排序排序哪一张对比(在相同条件下做出的测试): 1、平均时间都比选择排序用时要长,这是由于冒泡排序交换的次数远比选择排序多,而比较次数则一样。 2、冒泡排序的时间波动相对来说比较大,和随机数组的原本排序有关。如果原本顺序比较好,那么冒泡排序就 不需要太多的交换,那么速度会快很多。而相对插入排序,每次都的遍历完所有的未排序的序列,所以时间 也是相对很稳定的。
稳定性:稳定。 如果两个元素相等,我想你是不会再无聊地把他们俩交换一下的;如果两个相等的元素没有相邻,那么即使通过 前面的两两交换把两个相 邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳 定排序算法。