排序之交换类排序

1.冒泡排序

package Sort; 
/** 
 * @author wangpei 
 * @version 
 *创建时间：2017年3月28日 下午8:28:00 
 * 冒泡排序
 * 思路：依次两两比较，按顺序判断是否交换位置，经过一次冒泡，最后一个元素，肯定为最大值。
 * 在依次进行前n-1个元素的比较交换。
 */
//稳定排序。最小O(n) 平均o(n*n)
public class Maopao {
    public static void main(String[] args) {
        int a[]={0,2,5,3,9,10,1};
        sort(a);
    }
    public static void sort(int a[] ){
        for(int i=0;i<a.length;i++){
            for(int j=0;j<a.length-i-1;j++){
                if(a[j]>a[j+1]){
                    int t=a[j];
                    a[j]=a[j+1];
                    a[j+1]=t;
                }

            }
        }
        for(int i=0;i<a.length;i++){
            System.out.println(a[i]+",");
        }
    }

}

2.快速排序

package Sort; 
/** 
 * @author wangpei 
 * @version 
 *创建时间：2017年3月28日 上午11:15:05 
 * 思路：设置一个标记位a[0]=a[枢纽]
 * high=a.length-1
 * low=1
 * 依次进行high++,low--若将大于a[0]的移动到a[0]的右边，
 * 小于a[0]的，移动到a[0]的左边。
 * 再分治法，递归分别进行枢纽左边和右边的移动。
 * 一次快排后枢纽的左边是小于枢纽的数字，右边是大于枢纽的数字。
 */
//不稳定。o(nlog2n) 最坏：o(n*n)
public class Kuaipai {
    public static int pai(int a[], int low, int high) {// 一趟快排。
        a[0] = a[low];
        while (low < high) {
            while (low < high && a[0] < a[high])
                --high;
            a[low] = a[high];
            while (low < high && a[0] > a[low])
                ++low;
            a[high] = a[low];

        }
        a[low] = a[0];
        return low;

    }

    public static void KPai(int a[], int low, int high) {
        if (low < high) {
            int pos = pai(a, low, high);
            KPai(a, low, pos - 1);
            KPai(a, pos + 1, high);
        }

    }
    public static void main(String[] args) {
        int a[]={0,1,5,3,9,2};
         KPai(a,1,a.length-1);
         for (int i = 1; i < a.length; i++) {
            System.out.print(a[i]+",");
        }

    }

}