概述

1. 排序原理

• 选择排序：遍历比较数组最大值，通过游标标记，最后和末位交换。2个for循环和index解决问题。
• 冒泡排序：遍历比较最大值，不停交换最大值一直到末位，2个for循环解决问题。
• 插入排序：维护一个递增的数组，通过一个游标，和最大的数比，比最大的大就break；否则游标和比较对象都左移
• 希尔排序：3层for循环+while，插入排序的改进版本，跨度插入排序形成基本有序数组再插入排
• 快排排序：每次首位元素通过交换找到它在该数组段中的位置，再递归，引入low high head tail关键标记位。基于这种思路，可以解决无序数组中中位数，和无需数组求中位数的算法，随机第一个元素切分数组，缩小范围的方式来定位查找目标。
• 归并(分治)：精华是拆分问题，把数组拆分成2个小数组最后在递归性的从小问题解决到最大的问题，第二个核心在于2个连续的有序数组的merge方法。利用一个辅助数组。
• 堆排序：初始化的时候构建最大堆（调用 2/N ++以上的Node挨个swim），然后和末尾交换位置，下标自减，调用sink()即可

2. 空间复杂度：

• 归并排序依赖辅助数组，空间复杂度为N（Merge函数调用时，需要先写到辅助数组中，最后再写回到原数组)
• 快速排序因为递归的次数（N-LogN次）（最差和最好），递归时要保存一些数据
• 其它排序的空间复杂度都是1，常数级别

3. 平均时间复杂度

• 冒泡、选择、插入排序 N²
• 希尔排序 N<实际<N²
• 快排、归并、堆排 N*LogN

选择排序

        for(int i=0;i<length;i++){
            int max=0;
            for(int j=1;j<length-i;j++){
                if(arr[max]<arr[j]){
                    max=j;
                }
            }
            Util.exchange(max, length-i-1, arr);
        }

插入排序

        for(int i=1;i<length;i++){
            int index=i;
            for(int j=i-1;j>=0;j--){
                if(arr[index]>arr[j]) break;
                Util.exchange(index, j, arr);
                index--;
            }
        }

Shell

public static void shellSortByGap(int gap, int[] arr){
        int length=arr.length;
        for(int i=0;i<gap;i++){
            for(int j=i+gap;j<length;j=j+gap){
                int index=j;
                while(index>i){
                    if(arr[index]>arr[index-gap]) break;
                    if(arr[index]<arr[index-gap]){
                        Util.exchange(index-gap, index, arr);
                        index-=gap;
                    }
                }
            }
        }   
    }

Quick

    public static void locate(int low,int high,int[] arr){
        if(low>=high) return;
        int index=low;
        int tail=high;
        while(tail>index){
            if(arr[index]>arr[index+1]){
                Util.exchange(index, index+1, arr);
                index++;
            }else if(arr[index]<arr[index+1]){
                Util.exchange(index+1, tail, arr);
                tail--;
            }
        }
        locate(low,index-1,arr);
        locate(index+1,high,arr);
    }

heap

    public void sink(int k){
        //check是否有子节点
        while(2*k<=size){
            int bigSonNode=2*k;
            //如果有右子节点且右子节点大于左子节点则 最大子节点指向右子节点
            if((2*k+1<size)&&list.get(2*k)<list.get(2*k+1)){
                bigSonNode=2*k+1;
            }
            
            //比较左子节点，如果小于，就交换
            if(list.get(k)<list.get(bigSonNode)){
                Util.exchangeList(k, bigSonNode, list);
                k=bigSonNode;
                //检查是否存在右子树，如果右且大于父节点就交换
              }else{
                  break;
              }
            
        }
    }

    //通过从N/2开始往堆顶进行sink()操作构建堆有序
    public static void buildHeap(MaxPQ pq){
        int N=pq.list.size()-1;
        for(int i=N/2;i>0;i--){
            pq.sink(i);
        }
    }

    public static void HeapSort(MaxPQ pq){
        List<Integer> list=pq.getList();
        int size=list.size();
        int tail=size-1;
        for(int i=1;i<size;i++){
            Util.exchangeList(1, tail, list);
            pq.setSize(--tail);
            pq.sink(1);
        }
    }

Merge

    //对一个数组按照下标进行归并排序
    //归并排序的精华所在：问题拆分，把一个大问题拆分为N个性质一样但更简单的小问题
    public static void mergeSort(int[] arr,int start,int end){
        //这也是递归的终结，当数组拆分到只有1个元素的时候，必然是有序的，否则就继续拆分
        if(start<end){
            //拆分大问题为两个小问题
            int mid=(start+end)/2;
            mergeSort(arr,start,mid);
            mergeSort(arr,mid+1,end);
            //小问题解决完之后，最后父问题
            merge(arr,start,mid,end);
        }
    }

    //有两个数组，一个数源数组arr1，一个是工具数组是长度一样但是都是null的arr2
    //arr1数组中有2个连续且有序的数组 arr11 和 arr12
    
    //low是arr11的start，mid是arr11的end，mid+1是arr12的start，high是arr12的end
    //设置了3个游标，i为arr11的游标，j为arr12的游标，k为arr2的游标
    
    //merge的思路是当arr11和arr12中从起始位置开始比较，最小的写到arr2中，一直到有一个掏空了
    //假如是arr11先掏空，那么顺序把arr12中的元素顺序写入到arr2中；反之把arr11中剩余元素写入到arr2中
    //最后再把工具数组里的数据按照low high位置写回到arr1中，这样可以arr1可以继续比较了
    public static int[] arr2=new int[20];
    public static void merge(int[] arr1,int low,int mid,int high){
        int i=low,k=low,j=mid+1;
        //当arr11和arr12中从起始位置开始比较，最小的写到arr2中，对应下标移动，一直到有一个掏空了为止
        while(i<=mid&&j<=high){
            if(arr1[i]<arr1[j]){
                arr2[k++]=arr1[i++];
            }else {
                arr2[k++]=arr1[j++];}
        }
        //如果是arr12先被掏空，则arr11中剩余元素写入到arr2中,这里可以优化
        while(i<=mid){
            arr2[k++]=arr1[i++];
        }
        //如果是arr11先被掏空，则arr12中剩余元素写入到arr2中，这里可以优化
        while(j<=high){
            arr2[k++]=arr1[j++];
        }
        //arr2排序结束写回到arr1中相应位置
        for (i = low; i <= high; i++) {
            arr1[i] = arr2[i];
        }
    }