public class InsertSort {
    public static void insertSort(int[] array){
        for(int i = 1;i < array.length;i++){    //讓從1下標(biāo)開始，因?yàn)槿绻挥幸粋€(gè)元素，它自己默認(rèn)有序
            int key = array[i];          //從數(shù)組中的第二個(gè)元素開始比較，進(jìn)行插入
            int end = i-1;        //end的位置是要插入元素的前一個(gè)位置
            while(end >= 0 && key < array[end]){    //end不能越界，找待插入的位置，此處注意：key不能小于等于array[end]，否則為不穩(wěn)定
                array[end+1] = array[end];
                end--;
            }
            array[end+1] = key;         //找到位置進(jìn)行插入，因?yàn)樯厦鎒nd--了，所以這里要插入的位置為end+1
        }
    }
 
    public static void main(String[] args) {
        int[] array = {2,5,1,3,8,6,9,4,7,0,6};
        insertSort(array);
        for(int i : array){
            System.out.print(i+" ");
        }
    }
}

public class ShellSort {
    public static void shellSort(int[] array){
        int gap = array.length;
        while(gap > 1){
            gap = gap/3+1;
            for(int i = gap;i < array.length;i++){  //跟插入排序一樣，都從一組數(shù)的第二個(gè)元素開始，因?yàn)榈谝粋€(gè)數(shù)默認(rèn)有序
                int key = array[i];
                int end = i - gap;        //end的位置也是代排數(shù)的前一個(gè)，但這里間隔為gap，所以前一個(gè)位置為i-gap
                while(end >= 0 && key < array[end]){   //與插入排序保持不變,找待插入的位置
                    array[end+gap] = array[end];    // key小于前一個(gè)數(shù)，讓end位置的元素往后移一位，
                    end -= gap;    //end每次向左走的時(shí)候一次走gap的間隔
                }
                array[end+gap] = key;    //找到待排位置將key插入相應(yīng)位置
            }
        }
    }
 
    public static void main(String[] args) {
        int[] array = {2,5,1,3,8,6,9,4,7,0,6};
        shellSort(array);
        for(int i : array){
            System.out.print(i+" ");
        }
    }
}

public class SelectSort {
    public static void selectSort1(int[] array){
        int size = array.length;
        for(int i = 0;i < size-1;i++){   //選擇的趟數(shù)，size-1是因?yàn)楫?dāng)選擇到序列剩一個(gè)元素時(shí)就不用選了
            int pos = 0;    //pos標(biāo)記最大元素的位置，剛開始是默認(rèn)為第一個(gè)位置
            for(int j = 1;j < size-i;j++){   //j=1是因?yàn)槟J(rèn)第一個(gè)元素的位置為最大元素的位置，所以從第二個(gè)元素的位置開始比較
                                             //size-i是因?yàn)槊刻诉x擇完后，序列都要減少一個(gè)
                if(array[j] > array[pos]){
                    pos = j;    //找到最大元素位置，更新pos
                }
            }
            if(pos != size-i-1){   //如果最大元素的位置剛好是最后一個(gè)位置，則不需要交換，反之進(jìn)行交換
                swap(array,pos,size-i-1);
            }
        }
    }
    public static void selectSort2(int[] array){
        int left = 0;     //序列的左邊界
        int right = array.length-1;   //序列的右邊界
        while(left < right){   //當(dāng)序列中至少存在倆元素時(shí)
            int minPos = left;   //剛開始將最小元素的位置設(shè)定為序列的第一個(gè)位置
            int maxPos = left;   //剛開始將最大元素的位置也設(shè)定為序列的第一個(gè)位置
            int index = left+1;  //從序列的第二個(gè)元素開始找最大元素和最小元素的位置
            //找最大元素和最小元素的位置
            while(index <= right){
                if(array[index] < array[minPos]){
                    minPos = index;
                }
                if(array[index] > array[maxPos]){
                    maxPos = index;
                }
                index++;
            }
            if(minPos != left){  //當(dāng)最小的元素不在序列的最左端時(shí)交換位置
                swap(array,minPos,left);
            }
            //這里我是先交換最小的元素，但是如果最大的元素在最左側(cè)，那么會(huì)將maxPos位置的元素更新為最小的元素，導(dǎo)致后面
            //交換最大元素的時(shí)候maxPos標(biāo)記的元素不準(zhǔn)確，所以下面將maxPos的位置更新了一下
            //注意：如果是先交換最大的元素，則更新minPos的位置
            if(maxPos == left){
                maxPos = minPos;
            }
           // if(minPos == right){
           //     minPos = maxPos;
           // }
            if(maxPos != right){    //當(dāng)最大元素不在序列的最右端時(shí)交換位置
                swap(array,maxPos,right);
            }
            left++;  //左邊界+1
            right--; //右邊界-1
        }
    }
    public static void swap(int[] array,int a,int b){
        int t = array[a];
        array[a] = array[b];
        array[b] = t;
    }
 
    public static void main(String[] args) {
        int[] array = {9,5,1,3,8,6,2,4,7,6,0};
        selectSort1(array);
        for(int i : array){
            System.out.print(i+" ");
        }
        System.out.println();
        selectSort2(array);
        for(int i : array){
            System.out.print(i+" ");
        }
    }
}

public class HeapSort {
    //向下調(diào)整
    public static void shiftDown(int[] array,int parent,int size){
        int child = parent*2+1;  //默認(rèn)將左孩子設(shè)為parent的孩子，因?yàn)椴恢烙疫吅⒆邮欠翊嬖?
        while(child<size){
            if(child+1<size && array[child+1]>array[child]){   //如果右孩子存在，比較哪個(gè)孩子值大
                child += 1;   //將child設(shè)為較大的孩子
            }
            if(array[parent]<array[child]){  //如果parent小，將parent與child交換
                swap(array,parent,child);
                parent = child;   //更新parent
                child = parent*2+1;   //更新child
            }else{    //如果已經(jīng)滿足堆特性則直接返回
                return;
            }
        }
    }
    //堆排序
    public static void heapSort(int[] array){
        //建堆
        int size = array.length;
        int lastLeaf = ((size-1)-1)/2;  //找到倒數(shù)第一個(gè)非葉子節(jié)點(diǎn)
        for(int root=lastLeaf;root>=0;root--){    //從該結(jié)點(diǎn)開始，依次向下調(diào)整直到根節(jié)點(diǎn)
            shiftDown(array,root,size);
        }
        //利用堆刪除思想排序,從最后一個(gè)元素開始與堆頂元素交換，然后對(duì)堆頂元素進(jìn)行向下調(diào)整
        int end = size-1;
        while(end>0){
            swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }
    public static void swap(int[] array,int a,int b){
        int t = array[a];
        array[a] = array[b];
        array[b] = t;
    }
 
    public static void main(String[] args) {
        int[] array = {2,5,1,3,8,6,9,4,7,0,6};
        heapSort(array);
        for(int i : array){
            System.out.print(i+" ");
        }
    }
}

public class BubbleSort {
    public static void bubbleSort(int[] array){
        int size = array.length;
        for(int i = 0;i < size-1;i++){
            boolean isChange = false;         //為了優(yōu)化冒泡排序給的標(biāo)記，當(dāng)元素不發(fā)生交換的時(shí)候說明已經(jīng)有序
            for(int j = 0;j < size-1-i;j++){
                if(array[j+1] < array[j]){
                    swap(array,j,j+1);
                    isChange = true;
                }
            }
            if(isChange == false){     //如果元素不發(fā)生交換，直接返回
                return;
            }
        }
    }
    public static void swap(int[] array,int a,int b){
        int t = array[a];
        array[a] = array[b];
        array[b] = t;
    }
 
    public static void main(String[] args) {
        int[] array = {2,5,1,3,8,6,9,4,7,0,6};
        bubbleSort(array);
        for(int i : array){
            System.out.print(i+" ");
        }
    }
}

public static void quickSort(int[] array,int left,int right){   //左閉右開
        if(right-left > 1){       //遞歸的返回條件，區(qū)間最少得有兩個(gè)元素
            int div = partition(array,left,right);
            quickSort(array,left,div);    //遞歸排左側(cè)
            quickSort(array,div+1,right);   //遞歸排右側(cè)
        }
    }

 //分割區(qū)間方法1：hoare：左邊找比基準(zhǔn)值大的，右邊找比基準(zhǔn)值小的，兩個(gè)交換位置,最后再將基準(zhǔn)值放到中間的位置
    public static int partition1(int[] array,int left,int right){
        int key = array[right-1];   //找基準(zhǔn)值，以最右側(cè)元素為基準(zhǔn)值
        int begin = left;    //在左側(cè)找的下標(biāo)
        int end = right-1;    //在右側(cè)找的下標(biāo)
        while(begin < end){
            while(array[begin] <= key && begin < end){  //左側(cè)找大的，不能越界
                begin++;
            }
            while(array[end] >= key && end > begin){    //右側(cè)找小的，不能越界
                end--;
            }
            if(begin != end){
                swap(array,begin,end);    //begin與end不在同一位置的時(shí)候交換，否則沒有交換的必要
            }
        }
        if(begin != right-1){
            swap(array,begin,right-1);    //將基準(zhǔn)值與begin位置的元素交換，begin或者end都行
        }
        return end;        //將分割的位置返回，begin與end都可以
    }

 //分割區(qū)間方法二：挖坑法：基準(zhǔn)值是一個(gè)坑位，左側(cè)找大的放到基準(zhǔn)值的坑位上，此時(shí)形成了新的坑位，再在右側(cè)找小的放到上一個(gè)坑位，依次循環(huán)
    public static int partition2(int[] array,int left,int right){
        int key = array[right-1];  //取最右側(cè)元素為基準(zhǔn)值，end的位置形成了第一個(gè)坑位
        int begin = left;
        int end = right-1;
        while(begin < end){
            while(begin < end && key >= array[begin]){   //在左側(cè)找比基準(zhǔn)值大的
                begin++;
            }
            if(begin < end){
                array[end] = array[begin];   //填end坑位，重新生成begin坑位
            }
            while(begin < end && key <= array[end]){    //在右側(cè)找比基準(zhǔn)值小的
                end--;
            }
            if(begin < end){
                array[begin] = array[end];    //填begin坑位，重新生成end坑位
            }
        }
        array[begin] = key;     //將基準(zhǔn)值填充在最后一個(gè)坑位
        return end;
    }

  //分割區(qū)間方法三：前后標(biāo)記法
    public static int partition3(int[] array,int left,int right){
        int key = array[right-1];
        int cur = left;
        int pre = cur-1;
        while(cur < right){
            if(array[cur] < key && ++pre != cur){   //當(dāng)cur位置的元素小于基準(zhǔn)值并且++pre！=cur的時(shí)候，交換
                swap(array,cur,pre);
            }
            cur++;
        }
        if(++pre != right-1){        //++pre為與基準(zhǔn)值交換的位置，所以當(dāng)++pre！=right-1的時(shí)候，交換基準(zhǔn)值的位置
            swap(array,pre,right-1);
        }
        return pre;
    }

//快排優(yōu)化：三數(shù)取中法來取基準(zhǔn)值，左側(cè)，右側(cè)，中間這三個(gè)數(shù)的中間值來作為基準(zhǔn)值,這里返回的是基準(zhǔn)值下標(biāo)
    public static int getIndexOfMid(int[] array,int left,int right){
        int mid = left+((right-left)>>1);
        if(array[left] < array[right-1]){    //最右側(cè)的下標(biāo)為right-1
            if(array[mid] < array[left]){
                return left;
            }else if(array[mid] > array[right-1]){
                return right-1;
            }else{
                return mid;
            }
        }else{
            if(array[mid] < array[right-1]){
                return right-1;
            }else if(array[mid] > array[left]){
                return left;
            }else{
                return mid;
            }
        }
    }

//分割區(qū)間方法三：前后標(biāo)記法
    public static int partition3(int[] array,int left,int right){
        int index = getIndexOfMid(array,left,right);   //用三數(shù)取中法獲得基準(zhǔn)值的下標(biāo)
        if(index != right-1){
            swap(array,index,right-1);    //如果下表不在最右側(cè)就交換
        }
        int key = array[right-1];
        int cur = left;
        int pre = cur-1;
        while(cur < right){
            if(array[cur] < key && ++pre != cur){   //當(dāng)cur位置的元素小于基準(zhǔn)值并且++pre！=cur的時(shí)候，交換
                swap(array,cur,pre);
            }
            cur++;
        }
        if(++pre != right-1){        //++pre為與基準(zhǔn)值交換的位置，所以當(dāng)++pre！=right-1的時(shí)候，交換基準(zhǔn)值的位置
            swap(array,pre,right-1);
        }
        return pre;
    }

 //非遞歸的快速排序，利用棧來保存分割的區(qū)間，傳參只需要傳數(shù)組即可
    public static void quickSort(int[] array){
        Stack<Integer> s = new Stack<>();
        s.push(array.length);
        s.push(0);
        while(!s.empty()){
            int left = s.pop();
            int right = s.pop();
            if(right - left == 0){
                continue;
            }
            int div = partition(array,left,right);
            s.push(right);
            s.push(div+1);
            s.push(div);
            s.push(left);
        }
    }

public class MergeSort {
    public static void mergeSort(int[] array,int left,int right,int[] temp){
        if(right - left > 1){
            int mid = left+((right-left)>>1);
            mergeSort(array,left,mid,temp);      //遞歸均分左側(cè)
            mergeSort(array,mid,right,temp);      //遞歸均分右側(cè)
            mergeData(array,left,mid,right,temp);  //合并兩個(gè)序列，[left,mid) , [mid,right)
            System.arraycopy(temp,left,array,left,right-left); //拷貝到原數(shù)組，源，起始位置，新，起始位置，長度
        }
    }
    public static void mergeData(int[] array,int left,int mid,int right,int[] temp){
        //[begin1,end1),[begin2,end2),為兩個(gè)合并的區(qū)間
        int begin1 = left;
        int end1 = mid;
        int begin2 = mid;
        int end2 = right;
        int index = left;   //輔助數(shù)組的下標(biāo)
        while(begin1 < end1 && begin2 < end2){
            if(array[begin1] <= array[begin2]){
                temp[index++] = array[begin1++];
            }else{
                temp[index++] = array[begin2++];
            }
        }
        while(begin1 < end1){
            temp[index++] = array[begin1++];
        }
        while(begin2 < end2){
            temp[index++] = array[begin2++];
        }
    }
    //重新包裝一下，便于用戶傳參
    public static void mergeSort(int[] array){
        int[] temp = new int[array.length];
        mergeSort(array,0,array.length,temp);
    }
}

 //非遞歸的歸并排序
    public static void mergeSortNor(int[] array){
        int size = array.length;
        int[] temp = new int[size];
        int gap = 1;       //先每兩個(gè)元素歸并
        while(gap < size){
            for(int i = 0;i < size;i+=gap*2){
                int left = i;
                int mid = i+gap;
                int right = mid+gap;
                if(mid > size){    //防止mid越界
                    mid = size;
                }
                if(right > size){   //防止right越界
                    right = size;
                }
                mergeData(array,left,mid,right,temp);
            }
            System.arraycopy(temp,0,array,0,size);
            gap <<= 1;
        }
    }

public class CountSort {
    public static void countSort(int[] array){
        //找出數(shù)組的最大值與最小值
        int maxNum = array[0];
        int minNum = array[0];
        for(int i = 1;i < array.length;i++){
            if(array[i] > maxNum){
                maxNum = array[i];
            }
            if(array[i] < minNum){
                minNum = array[i];
            }
        }
        int range = maxNum - minNum + 1;   //序列元素的范圍大小
        int[] count = new int[range];      //new一個(gè)范圍大小的數(shù)組
        for(int i = 0;i < array.length;i++){
            count[array[i]-minNum]++;      //讀取
        }
        int index = 0;     //存入原數(shù)組的下標(biāo)
        for(int i = 0;i < range;i++){
            while(count[i] > 0){
                array[index] = i + minNum;
                index++;
                count[i]--;
            }
        }
    }
 
}