[数据结构与算法]java--排序算法--插入；希尔；选择；堆；冒泡

//1.插入排序
public class TestSort {
    //升序排序
    public static void insertSort(int[] array) {
        //通过bound来划分出两个区间
        //[0,bound)已排序区间
        //(bound,size]待排序区间
        for (int bound = 1;bound < array.length;bound++) {
            int v = array[bound];
            int cur = bound - 1;//已排序区间的最后一个元素下标
            for (;cur >= 0;cur--){
                //注意！！！这里如果是>=，插入排序就不是稳定排序了
                if (array[cur] > v){
                    array[cur + 1] = array[cur];
                }else {
                    //此时说明已经找到了合适的位置
                    break;
                }
            }
            array[cur + 1] = v;
        }
    }

    //2.希尔排序
    public static void shellSort(int[] array) {
        int gap = array.length / 2;
        while(gap > 1) {
            //需要循环进行分组插排
            insertSortGap(array,gap);
            gap = gap / 2;
        }
        insertSortGap(array,1);
    }
    private static void insertSortGap(int[] array,int gap) {
        //通过bound来划分出两个区间
        //[0,bound)已排序区间
        //(bound,size]待排序区间

        //当把gap替换成1的时候，理论上这个代码就和前面的插排代码一模一样
        for (int bound = gap;bound < array.length;bound++) {
            int v = array[bound];
            int cur = bound - gap;//这个操作是在找同组中的上一个元素
            for (;cur >= 0;cur -= gap){
                //注意！！！这里如果是>=，插入排序就不是稳定排序了
                if (array[cur] > v){
                    array[cur + gap] = array[cur];
                }else {
                    //此时说明已经找到了合适的位置
                    break;
                }
            }
            array[cur + gap] = v;
        }
    }


    //3.选择排序
    public static void selectSort(int[] array) {
        for (int bound = 0;bound < array.length;bound++) {
            //以bound位置的元素作为擂主，循环从待排序区间中取出元素和擂主比较
            //如果打擂成功，就和擂主交换
            for (int cur = bound + 1;cur < array.length;cur++) {
                if (array[cur] < array[bound]) {
                    int tmp = array[cur];
                    array[cur] = array[bound];
                    array[bound] = tmp;
                }
            }
        }
    }

    //4.堆排序
    private static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    public static void heapSort(int[] array) {
        //先建立堆
        createHeap(array);
        //循环把堆顶元素交换到最后，并进行调整堆
        //循环此时是length - 1，当堆中只剩一个元素的时候，也就一定是有序的了
        for (int i = 0;i < array.length - 1;i++) {
            //当前堆的元素个数
            int heapSize = array.length - i;
            //交换堆顶元素和堆的最后一个元素
            //堆的元素个数是array.length - i
            //堆的最后一个元素下标array.length - i - 1
            swap(array,0, heapSize - 1);
            heapSize--;//排除最后一个元素
            //交换完成之后把最后一个元素从堆中删除，堆的长度进一步减小为array.length - i - 1
            //数组中[0,array.length - i - 1)待排序区间，[array.length - i - 1,array.length)已排序区间
            //“差1问题”带入验证
            myShiftDown(array,heapSize,0);
        }
    }

    private static void createHeap(int[] array) {
        for (int i = (array.length - 1 - 1) / 2;i >= 0;i--) {
            myShiftDown(array,array.length,i);
        }
    }


    private static void myShiftDown(int[] array,int heapLength,int index) {
     int parent = index;
     int child = 2 * parent + 1;
     while(child < heapLength) {
         if (child + 1 < heapLength && array[child + 1] > array[child]) {
             child = child + 1;
         }
         //条件结束意味着child已经是左右子树比较大的那个
         if (array[child] > array[parent]) {
             swap(array,child,parent);
         }else {
             break;
         }
         parent = child;
         child = 2 * parent +1;
     }
}


//5.冒泡排序
    public static void bubbleSort(int[] array) {
        //按照每次找最小的方式来排序（从后往前比较交换）
        for (int bound = 0; bound < array.length;bound++) {
            //[0,bound)已排序区间；[bound，size）待排序区间
            //cur > bound而不是 >=,当bound为0时，如果>=,cur也为0，cur-1也就下标越界了
            for (int cur = array.length-1;cur > bound;cur--) {
                //此处cur-1是因为cur初始值是array.length - 1,如果取cur+1下标的元素就越界了
                //此处的条件如果写成 >=同样无法保证稳定性
                if (array[cur - 1] > array[cur]) {
                    swap(array,cur - 1,cur);
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {9,5,6,8,3, 1};
       heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}