1. 插入排序：平均On2，最好On，最坏On2，稳定

2. 提取当前元素作为基准，对当前位置前面区间进行以当前元素为基准进行升序排列，排序完成后将当前元素放入区间的后一个位置

    private static void insertSort(int[] nums) {
        for(int i=1;i<nums.length;i++){
            int insertIndex;
            int insertNum = nums[i];
   
            //以insertNum为基准对[0,insertIndex-1]区间进行升序排序
            for(insertIndex=i-1;insertIndex >= 0 && nums[insertIndex] > insertNum;insertIndex--){
                nums[insertIndex+1] = nums[insertIndex];
            }
   
            //将insertNum插入到排序好的序列的后一个
            nums[insertIndex+1] = insertNum;
        }
    }

2. 冒泡排序：平均On2，最好On，最坏On2，稳定

2. 前后比较，前比后大，交换前后

    private static void bubbleSort(int[] nums) {
        for(int i=0;i<nums.length-1;i++){
            for(int j=0;j<nums.length-1-i;j++){
                //前后比较，前比后大，交换前后
                if(nums[j] > nums[j+1]){
                    swap(nums,j,j+1);
                }
            }
        }
    }

3. 选择排序：平均On2，最好On2，最坏On2，不稳定

2. 选择当前元素为基准，对后面的区间查找最小值，交换当前和最小值

    private static void selectSort(int[] nums) {
        for(int i=0;i<nums.length;i++){
            int min = i;
            for(int j=i+1;j<nums.length;j++){
                if(nums[j] < nums[min]){
                    min = j;
                }
            }
            if(min != i){
                swap(nums,min,i);
            }
        }
    }

4. 归并排序：平均Onlogn，最好Onlogn，最坏Onlogn，稳定

    private static void MergeSort(int[] nums, int start, int end) {
        if(start == end){
            return;
        }

        int middle = start + (end - start)/2;
        //递归排序左右
        MergeSort(nums,start,middle);
        MergeSort(nums,middle+1,end);
        //合并左右
        Merge(nums,start,middle,end);
    }

    private static void Merge(int[] nums, int start, int middle, int end) {
        int[] temp = new int[end - start + 1];
        int index = 0;

        int index1 = start;
        int index2 = middle+1;

        while(index1 <= middle && index2 <= end){
            if(nums[index1] < nums[index2]){
                temp[index++] = nums[index1++];
            }else{
                temp[index++] = nums[index2++];
            }
        }
        while(index1 <= middle){
            temp[index++] = nums[index1++];
        }
        while(index2 <= end){
            temp[index++] = nums[index2++];
        }
        for(int i=0;i<temp.length;i++){
            nums[i+start] = temp[i];
        }
    }

5. 快排：平均Onlogn，最坏On2(冒泡)，最好Onlogn，不稳定

1. 以第一个数为基准，比基准数小的，排在基准数左边，比基准数大的，排在基准数右边。递归再对这两个数组进行快排

    private static void quickSort(int[] nums, int start, int end) {
        if(start > end){
            return;
        }
   
        int pivot = getPivot(nums,start,end);
        //根据本次基准数，排序基准数左右序列
        quickSort(nums,start,pivot-1);
        quickSort(nums,pivot+1,end);
    }
   
    private static int getPivot(int[] nums, int start, int end) {
        int pivot = nums[start];
        int left = start;
        int right = end;
   
        while(left <= right){
            while(left <= right && nums[left] <= pivot){
                left++;
            }
            while(left <= right && nums[right] > pivot){
                right--;
            }
            if(left <= right){
                swap(nums,left,right);
            }
        }
        //基准数归位，返回基准数
        swap(nums,start,right);
        return right;
    }

7. 堆排：平均Onlogn，最好Onlogn，最坏Onlogn，不稳定

3. 建堆：par和cur比较，如果par比cur小，交换，cur=par

4. 排序：提取nums[0]，将nums[0]替换nums[index]，提取left和right，判断left越界，提取left为max，比较max和right，比较max和cur

    public static void main(String[] args) {
        int[] nums = new int[]{10,3,5,6,7,0,2};
   
        //建堆
        for(int i=0;i<nums.length;i++){
            create(nums,i);
        }
   
        //排序
        int [] result = new int[nums.length];
        int len = result.length-1;
        for(int i=nums.length-1;i>=0;i--){
            result[i] = poll(nums,len--);
        }
   
        for(int i : result){
            System.out.println(i);
        }
    }
   
    private static int poll(int[] nums, int index) {
        int result = nums[0];
        nums[0] = nums[index];
        int cur = 0;
        while(true){
            int left = cur*2 + 1;
            int right = cur*2 + 2;
            //左子树越界
            if(left >= index){
                break;
            }
            //右子树和max比较
            int max = left;
            if(right <= index && nums[max] < nums[right]){
                max = right;
            }
            //cur和max比较
            if(nums[cur] < nums[max]){
                swap(nums,cur,max);
            }else{
                break;
            }
            cur = max;
        }
        return result;
    }
   
    private static void create(int[] nums, int index) {
        //当前节点
        int cur = index;
        while(cur > 0){
            //父节点
            int par = (cur-1)/2;
            //如果当前比父节点大，交换
            if(nums[par] < nums[cur]){
                swap(nums,par,cur);
            }else{
                break;
            }
            cur = par;
        }
    }