public static void insertSort(int[] array) {
        //該循環(huán)實現(xiàn)對整個數(shù)組的遍歷操作
        for (int i = 1; i < array.length; ++i) {
            
            //記錄將被插入的元素(i下標元素)
            int tmp = array[i];
            //j指向i的前一個元素
            int j = i - 1;

            for (; j >= 0; j--) {
                //如果j指向的元素比被插入元素大，就往后移一位
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {//否則就找到了插入位置，跳出該循環(huán)
                    break;
                }
            }

            
            //j+1即為插入位置
            array[j + 1] = tmp;
        }
}

public static void shellSort(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            //gap為1時，就是直接插入排序
            gap = gap / 3 + 1;
            shell(array, gap);
        }
}
public static void shell(int[] array, int gap) {
        for (int i = gap; i < array.length; ++i) {
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if (array[j] > tmp) {
                    array[j + gap] = array[j];
                } else {
                    break;
                }
            }
            array[j + gap] = tmp;
        }
}

public static void selectSort(int[] array){
    for(int i = 0;i<array.length;++i){
        for(int j = i+1;j<array.length;++j){
            if(array[j]<array[i]){
                int tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
            }
        }
    }
}

public static void heapSort(int[] array) {
        createHeap(array);//建大堆
        int end = array.length - 1;
    //將堆頭元素與堆尾元素互換位置，就將最大元素放到了最后一位，舍去最后一位小標重新將堆向下調整；直到堆為空，數(shù)組中元素就排序完成。
        while (end >= 0) {
            int tmp = array[0];
            array[0] = array[end];
            array[end] = tmp;
            end--;
            siftDown(array, 0, end);
        }
    }
	//從小到大排序，建一個大堆
	public static void createHeap(int[] array) {
        for (int parent = (array.length - 1) / 2; parent >= 0; parent--) {
            siftDown(array, parent, array.length-1);
        }
    }

	//向下調整大堆
    public static void siftDown(int[] array, int root, int end) {
        int parent = root;
        int child = 2 * parent + 1;
        while (child <= end) {
            if (child + 1 <= end && array[child] < array[child + 1])
                child++;
            if (array[parent] < array[child]) {
                int tmp = array[parent];
                array[parent] = array[child];
                array[child] = tmp;
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;
            }
        }
    }

 public static void bubbleSort(int[] array) {
     //最外層循環(huán)為比較的趟數(shù)
        for (int i = 0; i < array.length - 1; ++i) {
            //flag是為了判斷接下來的循環(huán)是否有必要進行
            boolean flag = false;
            //內層循環(huán)為每趟比較的次數(shù)
            for (int j = 0; j < array.length - 1 - i; ++j) {
                if (array[j] > array[j + 1]) {
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                    flag = true;
                }
            }
            //flag==false說明這趟循環(huán)沒有交換數(shù)據(jù)，也就是說數(shù)組已經有序，可以直接返回。
            if (flag == false) return;

        }
    }

public static void quickSort(int[] array, int l, int r) {
        if (l >= r) return;
    //因為用do while（）循環(huán)，所以先將左右指針向兩邊移動一位
        int i = l - 1, j = r + 1;
    //取數(shù)組中間元素的值作為這個分割點
        int mid = array[(l + r)>>1];

        while (i < j) {
            //左邊的數(shù)小于中間值，指針向右移動
            do ++i; while (array[i] < mid);
            //右邊的數(shù)大于中間值，指針向左移動
            do --j; while (array[j] > mid);
            //兩個指針停下后交換元素
            if (i < j) {
                int tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
            }

        }
    //遞歸左半部分
        quickSort(array, l, j);
    //遞歸右半部分
        quickSort(array, j + 1, r);


    }

 public static void mergeSort(int[] array){
        mergerSortInternal(array,0,array.length-1);
    }
    public static void mergerSortInternal (int[] array,int l,int r){
        if(l>=r)    return;
        int mid = (l+r)>>1;
        //遞歸左半部分
        mergerSortInternal(array,l,mid);
        //遞歸右半部分
        mergerSortInternal(array,mid+1,r);
        //歸并
        merge(array,l,mid,r);
    }
    public static void merge(int[] array,int l,int mid, int r){
        int s1 = l,e1 = mid;
        int s2 = mid+1, e2 = r;
        int [] tmp = new int[r-l+1];
        int k = 0;
        //比較兩個有序小數(shù)組元素，將小的元素放到新數(shù)組前面，大的元素放到新數(shù)組后面
        while(s1<=e1 && s2<=e2){
            if(array[s1]<array[s2]){
                tmp[k++] = array[s1++];
            }else{
                tmp[k++] = array[s2++];
            }
        }
        //處理剩余元素
        while(s1<=e1)   tmp[k++] = array[s1++];
        while(s2<=e2)   tmp[k++] = array[s2++];
        //將排完序的新數(shù)組元素放回原數(shù)組中
        for(int i = 0;i<tmp.length;++i){
            array[i+l] = tmp[i];
        }
    }