JAVA算法系列 冒泡排序

java算法系列之排序

手写冒泡

冒泡算是最基础的一个排序算法，简单的可以理解为，每一趟都拿i与i+1进行比较，两个for循环，时间复杂度为 O(n^2),同时本例与选择排序进行了比较，选择排序又叫直接排序，之所以直接，就是简单粗暴，不像冒泡，冒泡是紧挨着的两个小伙伴两两比较，直接排序是每一趟直接拿当前i与整个数组中所有元素进行比较，如果大小不一致，直接替换，相当于跳跃过去了，根本不考虑小伙伴的感受，我看到哪个小伙伴比我小，我就占领它的位置，彼此替换。

package com.rsc.sort;

import java.util.Arrays;

/**
 * 冒泡排序
 *
 * @author 落雨 2015年6月5日09:33:13 http://ae6623.cn
 */
public class BubbleSort {
    /**
     * 直接排序(选择排序)
     * i与j进行比较，如果大小不一致，直接将a[i]与a[j]元素进行置换
     * @param array
     */
    public static void selectionSort(int[] array) {
        int temp = 0;
        int total = 1;
        for (int i = 0; i < array.length; i++) {// 循环length次
            //System.out.println("第"+i+"趟");
            for (int j = i + 1; j < array.length; j++) {// 从i+1开始和i进行比较，找到大小不一致的，直接与a[i]进行置换

                if (array[i] > array[j]) {
                    temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                    for (int k : array) {
                        System.out.print(k + " ");
                    }
                    System.out.println("交换" + total++ + "次 【" + array[j] + "交换"
                            + array[i] + "】");
                }
            }
        }

    }

    /**
     * 冒泡排序
     * 只置换相邻的两个元素
     * @param array
     */
    public static void bubbleSort(int[] array) {
        int temp = 0;
        int total = 1;
        boolean flag = false;
        //对于length个元素，只需要比较length-1即可 比如 5个数字，只需要循环比较4次
        for(int i=0;i<array.length-1;i++){

            //由于是冒泡排序，第一个位置肯定是最小的，每循环i次，就不用再判断前i个位置，所以length-1-i
            for(int j=0;j<array.length-i-1;j++){
                if(array[j]>array[j+1]){
                    /*
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                    */
                    array[j] = array[j] ^ array[j+1];
                    array[j+1] = array[j] ^ array[j+1];
                    array[j] = array[j] ^ array[j+1];

                    flag = true;//发生了置换
                    for (int k : array) {
                        System.out.print(k + " ");
                    }
                    System.out.println("交换" + total++ + "次 【" + array[j+1] + "交换"
                            + array[j] + "】");
                }
            }
            if(!flag){//如果无置换，则跳出循环
                break;
            }else{
                flag = false;//有置换，把标志位重新置为false，方便下一次判断
            }
            System.out.println("完成第"+(i+1)+"趟冒泡");
        }
    }

    public static void swap(int a,int b){

        a = a^b;
        b = a^b;
        a = a^b;
        System.out.println(a+","+b);
    }

    public static void main(String[] args) {

        //swap(5,3);

        int[] array = { 4, 1, 3, 2, 5 , 6 , 8 , 7 , 9  };
        int[] array2 = Arrays.copyOf(array, array.length) ;

        System.out.println("直接排序如下:");
        selectionSort(array); 

        System.out.println("冒泡排序如下:");
        bubbleSort(array2); 

    }
}

打印结果如下:

直接排序如下:
1 4 3 2 5 6 8 7 9 交换1次 【4交换1】
1 3 4 2 5 6 8 7 9 交换2次 【4交换3】
1 2 4 3 5 6 8 7 9 交换3次 【3交换2】
1 2 3 4 5 6 8 7 9 交换4次 【4交换3】
1 2 3 4 5 6 7 8 9 交换5次 【8交换7】
冒泡排序如下:
1 4 3 2 5 6 8 7 9 交换1次 【4交换1】
1 3 4 2 5 6 8 7 9 交换2次 【4交换3】
1 3 2 4 5 6 8 7 9 交换3次 【4交换2】
1 3 2 4 5 6 7 8 9 交换4次 【8交换7】
完成第1趟冒泡
1 2 3 4 5 6 7 8 9 交换5次 【3交换2】
完成第2趟冒泡