/**

 * 排序方法整理

 * @author zhyea

 *

 */

public class Sort {

    /**

     * 冒泡排序，从小到大。

     * 冒泡排序是比较相邻的两个元素，若顺序错误，则执行交换。循环走访序列直到不需要比较。稳定排序。

     * @param arr

     *             待排序的数组

     */

    public static void bubbleSort(int[] arr){

        int tmp = 0;

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

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

                if(arr[i-1] > arr[i] ){

                    tmp = arr[i];

                    arr[i] = arr[i-1];

                    arr[i-1] = tmp;

                }

            }

        }

    }

    /**

     * 选择排序，从小到大

     * 每次从待排序序列中取出最大(或最小)的一个元素,放入已排好序的序列后面。不稳定排序。

     * @param arr

     *             待排序数组

     */

    public static void selectSort(int[] arr){

        int tmp = 0;

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

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

                if(arr[i] < arr[k]){

                    tmp = arr[i];

                    arr[i] = arr[k];

                    arr[k] = tmp;

                }

            }

        }

    }

    /**

     * 插入排序，从小到大

     * 从待排序序列中取出一个，插入已排好序的序列的适当位置，如是重复。稳定排序。

     * @param arr

     *             待排序数组

     *

     */

    public static void insertSort(int[] arr){

        int tmp = 0;

        for(int k=1; k<arr.length; k++){

            for(int i=k; i>0; i--){

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

                    tmp = arr[i];

                    arr[i] = arr[i-1];

                    arr[i-1] = tmp;

                }

            }

        }

    }

    /**

     * 快速排序，从小到大

     * 通过一次排序，将待排序序列分成两部分，其中一部分中的值比另一部分都小；递归如上步骤，可完成排序。不稳定排序

     * 可以通过减少交换优化快速排序，不列出了

     * @param arr

     */

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

        int l = low;

        int h = high;

        int tmp = 0;

        int key = arr[0];

        while(h>l){

            while(h>l && arr[h]>=key){

                h--;

            }

            if(h>l){

                tmp = arr[l];

                arr[l] = arr[h];

                arr[h] = tmp;

                l++;

            }else{

                break;

            }

            while(h>l && arr[l]<=key){

                l++;

            }

            if(h!=l){

                tmp = arr[h];

                arr[h] = arr[l];

                arr[l] = tmp;

                h--;

            }else{

                break;

            }

        }

        if(l>low)quickSort(arr, 0, h-1);

        if(h<high)quickSort(arr, l+1, high);

    }

    public static void main(String[] args){

        int[] arr = {8, 5, 4, 6, 9, 7, 5, 6};

        System.out.println("冒泡排序" );

        bubbleSort(arr);

        printArr(arr);

    }

    /**

     * 循序输出数组中的每个元素

     * @param arr

     *             待输出数组

     */

    private static void printArr(int[] arr){

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

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

        }

        System.out.print("\n");

    }

}