冒泡排序各种实现

冒泡排序是最简单的排序算法,其时间复杂度O(n2),但是在数据量不是很大的情况,经优化过的冒泡乃是一种高效的算法。

简单粗暴的思路:

  1. 前面元素依次和后面元素进行比较
  2. 如果前面元素大于后面元素则进行交换 (这样进行一轮交换后,第一个元素就是最小的)
  3. 重复上面,直到前面所有位置的元素都跟后面的元素进行了一轮比较,排序完成。

按照这个思路写出的代码如下:


    public static void bubble(int arr[]) {
        int i, j;
        int length = arr.length;
        for (i = 0; i < length; i++) {
            for (j = i + 1; j < length; j++) {
                if (arr[i] > arr[j]) {
                    int tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
//                    swap(arr[i], arr[j]);这样是不行的
                }
            }
        }
    }
验证:
    public static void main(String[] args) {
        int array[] = {45, 234, 13, 45, 565, 76, 5, 3, 23, 45};
        bubble(array);
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }
//output:
3
5
13
23
45
45
45
76
234
565

我们看一下另一个版本的冒泡,设数据的大小为N,其思路是这样的:

  1. 依次比较相邻的二个数据
  2. 如果前面数据大于后面的数据,就将二个数据交换(这样进行一轮交换后,即数组的第0个数据到N-1个数据进行一次遍历,最大的元素就沉在数组的末尾N-1的位置)
  3. N=N-1,重复上面,直到N=0或者没有交换发生

按照这个想法写出的代码如下:


    public void bubble2(int arr[]) {
        int i, j;
        int length = arr.length;
        for (i = length - 1; 0 < i; i--) {
            for (j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
        }
    }

下面进行优化,很明显如果一轮比较没有发生交换,说明数组已经是有序的了。


    public void bubble3(int arr[]) {
        int j;
        int len = arr.length;
        Boolean flag = Boolean.TRUE;
        while (flag) {
            flag = Boolean.FALSE;
            for (j = 1; j < len; j++)
                if (arr[j - 1] > arr[j]) {
                    int tmp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = tmp;
                    flag = Boolean.TRUE;
                }
            len--;
        }
    }

进一步优化,如果有100个数的数组,仅前面10个无序,后面90个都已排好序且都大于前面10个数字,那么在第一趟遍历后,最后发生交换的位置必定小于10,且这个位置之后的数据必定已经有序了,记录下这位置,第二次只要从数组头部遍历到这个位置就可以了。


    public void bubble4(int arr[]) {
        int j, len;
        int flag = arr.length;
        while (flag > 0) {
            len = flag;
            flag = 0;
            for (j = 1; j < len; j++)
                if (arr[j - 1] > arr[j]) {
                    int tmp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = tmp;
                    flag = j;
                }
        }
    }

这里可以观看冒泡排序的动画演示:

https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

 

# 算法 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×