//代码原理

public static void iSort(int[] a){

    for(int i = 1;i < a.length; i++){

        if(a[i] < a[i-1]){

            int temp = a[i];

            while(temp < a[i-1]){

                a[i] = a[i-1];

                if(i-1 > 0){

                    i--;

                }else{

                    break;

                }

            }

            a[i-1] = temp;

        }

    }

}

//精简代码1

public static void iSort2(int[] a){

        for(int i = 1;i < a.length; i++){

            if(a[i] < a[i-1]){

                int temp = a[i];

                while(temp < a[i-1]){

                    a[i] = a[i-1];

                    if(i-1 > 0){

                        i--;

                    }else{

                        break;

                    }

                }

                a[i-1] = temp;

            }

        }

    }

//精简代码2

for(current=1;current<=arr.length-1;current++){

    //每当current变化，key和before都随之变化

    key = arr[current];

    before = current-1;//红色有序索引第一个值。

    while(before>=0 && arr[before]>key){

        arr[before+1] = arr[before];//大值向后移一位

        before--;

    }

    //插入点：before+1

    arr[before+1] = key;

}

public class BubbleSort {

    public static int[] bSort(int[] a){

        for(int j = a.length-1; j >= 1; j--){

//            如果flag没有变为false那么证明数组本身有序

            boolean flag = true;

            for(int i = 0; i <= j-1; i++){

                if(a[i] > a[i+1]){

                    int temp = a[i];

                    a[i+1] = a[1];

                    a[i] = temp;

                    flag = false;

                }

            }

            if(flag)

                break;

        }

        return a;

    }

}

/*

 * 选择排序基本思路：

 * 把第一个元素依次和后面的所有元素进行比较。

 * 第一次结束后，就会有最小值出现在最前面。

 * 依次类推

 */

public class SelectionSort {

    public static void sort(int[] data) {

        for (int x = 0; x < data.length - 1; x++) {

            for (int y = x + 1; y < data.length; y++) {

                if (data[y] < data[x]) {

                    SortTest.swap(data, x, y);

                }

            }

        }

    }

}

/**

 * 快速排序

 * @author mly11

 *

 */

public class QuickSort {

    static int low = 0;

    static int high = 0;

    static int mid = 0;

    public static void main(String[] args) {

        int[] arr = {5,1,3,9,2,7,2,4};

//        开始的数组为

        System.out.println("开始的数组为：");

        for(int i = 0; i < arr.length; i++){

            System.out.print(arr[i]+"\t");

        }

        System.out.println();

//        排序

        judge(arr);

//        排序后遍历

        System.out.println("排序后数组为：");

        for(int i = 0; i < arr.length; i++){

            System.out.print(arr[i]+"\t");

        }

        System.out.println();

    }

//    判断数组是否为空

    public static void judge(int[] arr){

        if(arr.length > 0){

            all(arr,0,arr.length-1);

        }else{

            System.out.println("换个吧");;

        }

    }

//    循环条件，递归调用循环体

    public static void all(int[] arr,int low,int high){

        if(low < high){

//            用mid记录每一次选择的分界数字的角标，

            mid = structure(arr, low, high);

//            当low < mid -1的时候，从low到mid-1进行递归

            if(low < mid - 1){

                all(arr, low, mid-1);

            }

//            当high>mid+1时候,从mid+1到high递归

            if(high > mid +1){

                all(arr, mid+1, high);

            }

        }

    }

//    循环体   一次循环

    public static int structure(int[] arr,int low,int high){

//        当索引low小于high时，进行运算，让小于所选值在左边，否则在右边

/*        原理：

        取出a[low]的数据存入temp，使a[low]为空；开始循环：

        当low < high 时，一直循环

        while(low < high){

            当low从第一个开始时，从后向前一一查找，如果比temp大，则high--；

            否则交换a[low]和a[high]，此时a[low]的值为a[high]，a[high]为空；

            现在从前（a[low]被a[high]占据的位置）向后查找，如果比temp小，则low++；

            否则将a[low]的位置存入a[high](上一步为空的a[high])，此时a[low]为空；

        }

        a[low] = temp;

        返回low,此时low的位置之前数据全部<a[low],low之后的位置的数据全部>a[low];

*/

        int temp = arr[low];

        while (low < high) {

            while (low < high && arr[high] >= temp) {

                high--;

            }

            arr[low] = arr[high];

            while (low < high && arr[low] < temp) {

                low++;

            }

            arr[high] = arr[low];

        }

        arr[low] = temp;

        return low;    

/*错误的方法

    while(low < high){

            int temp = arr[low];

            while(arr[low] <= arr[high]){

                high--;

            }

            arr[low] = arr[high];

            low++;

            arr[high] = arr[low];

            arr[low] = temp;

        }

        return low;*/

    }

}