排序——快速排序

已知数列{49，38，65，97，76，13，27，49}

1>快速排序      --> http://blog.csdn.net/jianyuerensheng/article/details/51258374

　　快速排序(是冒泡排序的一个升级)就是先找一个基准（一般是将数组第一个值作为基准元素)，然后通过第一趟扫描 将数组分为两部分，一部分是小于基准元素的，另一部分是大于基准元素的，最后通过递归实现分而治之，用同样的方法对两部分都进行操作，直到不能再分

public class sortKuaiTest {
    public static void main(String[] args) {
        int[] arrNum = {49,38,65,97,76,13,27,49};
        //排序方法
        sort(arrNum,0,arrNum.length-1);
        //打印输出结果
        for(int i=0;i<arrNum.length;i++){
            System.out.println(arrNum[i]);
        }
    }
    //排序
    public static void sort(int[] arrNum,int ss,int ee){
        if(ss>=ee){
            return;
        }
　　　　　//找中间位置
        int middle = getMiddleNum(arrNum,ss,ee);
        //递归排序
        sort(arrNum,ss,middle-1);
        sort(arrNum,middle+1,ee);
    }
　　//找中间位置
    public static int getMiddleNum(int[] arrNum,int ss,int ee){
        int tempNum = arrNum[ss];  //基准（选取数组第一个为基准数）
        while(ss<ee){
　　　　　　　//从后往前遍历
            while(ss<ee && arrNum[ee]>=tempNum){
                ee--;
            }
            arrNum[ss] = arrNum[ee];
　　　　　　　//从前往后遍历
            while(ss<ee && arrNum[ss]<=tempNum){
                ss++;
            }
            arrNum[ee] = arrNum[ss];
        }
　　　　　//讲基准数赋值给结束位置
        arrNum[ee] = tempNum;
        return ee;
    }
}

2>冒泡排序

public class sortKuaiTest {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] arrNum = {49,38,65,97,76,13,27,49};
        sortMP(arrNum);
        for(int i=0;i<arrNum.length;i++){
            System.out.println(arrNum[i]);
        }
    }
    public static void sortMP(int[] arrNum){
　　　　　//双层for循环遍历数组，逐个对比，如果后者小于前者则交换位置，实现了冒泡
　　　　　for(int i=0;i<arrNum.length;i++){
            for(int j=i+1;j<arrNum.length;j++){
                if(arrNum[i]>arrNum[j]){
                    int tempNum = arrNum[i];
                    arrNum[i] = arrNum[j];
                    arrNum[j] = tempNum;
                }
            }
        }
    }
}

3>插入排序

　　插入排序，就是从第二个值开始，与前面的值进行比较然后进行移位和插入

public class sortKuaiTest {
    public static void main(String[] args) {
        int[] arrNum = {49,38,65,97,76,13,27,49};
        sortCR(arrNum);
        for(int i=0;i<arrNum.length;i++){
            System.out.println(arrNum[i]);
        }
    }
    //----------------------------插入排序-------------------------------
    public static void sortCR(int[] arrNum){
        int i,j,tempNum;
        for(i=1;i< arrNum.length;i++){ //从数组第二个值开始进行
            tempNum = arrNum[i];       //暂时保存当前循环的值（即：要插入的值）
            j=i-1;
            while(j>=0 && tempNum<arrNum[j]){ //如果有插入的值比较小的，循环后移
                arrNum[j+1] = arrNum[j];
                j--;
            }
            arrNum[j+1] = tempNum;
        }
    }
}

4>希尔排序

　　希尔排序是插入排序的升级，是先设置增量(初始将增量设置为数组的一半，逐渐递减为增量的一半，直到增量为1)，然后判断两个值的大小进行交换位置

public class sortKuaiTest {
    public static void main(String[] args) {
        int[] arrNum = {49,38,65,97,76,13,27,49};
        sortXE(arrNum);
        for(int i=0;i<arrNum.length;i++){
            System.out.println(arrNum[i]);
        }
    }
    //----------------------------希尔排序-------------------------------
    public static void sortXE(int[] arrNum){
        int i,j,tempNum; //i为每次排序的增量
        for(i=arrNum.length/2;i>0;i /= 2){  //增量为上一次的一半（i/2）
            for(j=0;j<arrNum.length-i; j++){
                if(arrNum[j]>arrNum[j+i]){  //升序或降序在这里可以设置
                    tempNum = arrNum[j];
                    arrNum[j] = arrNum[j+i];
                    arrNum[j+i] = tempNum;
                }
            }
        }
    }
}