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); 

    }
}