[数据结构与算法]【算法学习日志】高级排序算法（希尔，归并，快排）

?去看了会披荆斩棘的哥哥，接着回来学习。

• 希尔排序

?

public class Solution {
    public int[] sortArray(int[] nums) {
        int n = nums.length;
        int h = 1;
        while(h < n/2){
            h = 2*h+1;
        }
        while(h >= 1){
            for(int i=h;i<n;i++){
                for(int j=i;j>=h;j-=h){
                    if(nums[j-h] > nums[j]){
                        exchange(nums,j-h,j);
                    }else{
                        break;
                    }
                }
            }
            h = h/2;
        }
        return nums;
    }

    public static void exchange(int[] a,int i,int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

改进版的插入排序！

时间复杂度跟增量h的设置有关，我这里是每次循环结束都折半

算麻了，应该是吗…？

提交通过了，用时12ms

• 归并排序

public class Solution {
    public static int[] sortArray(int[] nums) {
        int[] assist = new int[nums.length];
        int lo = 0;
        int hi = nums.length - 1;
        sort(nums,assist,lo,hi);
        return nums;
    }

    public static void sort(int[] a,int[] assist,int lo,int hi){
        if(hi<=lo){
            return;
        }
        int mid = lo + (hi-lo)/2;
        sort(a,assist,lo,mid);
        sort(a,assist,mid+1,hi);
        merge(a,assist,lo,mid,hi);
    }

    public static void merge(int[]a,int[] assist,int lo,int mid,int hi){
        int i = lo;
        int p1 = lo;
        int p2 = mid+1;
        while(p1<=mid && p2 <=hi){
            if(a[p1] <= a[p2]){
                assist[i++] = a[p1++];
            }else{
                assist[i++] = a[p2++];
            }
        }
        while (p1<=mid){
            assist[i++] = a[p1++];
        }
        while (p2<=hi){
            assist[i++] = a[p2++];
        }
        for(int j = lo;j<=hi;j++){
            a[j] = assist[j];
        }
    }

    public static void exchange(int[] a,int i,int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

分治思想的典例了吧，先对半对半拆开，再两个两个合起来。用了递归，思路不难理解，但是自己写的时候出了各种各样的问题……看别人用comparable在sort方法里定义的assist数组，中间调用方法的时候也没有传递过assist这个数组，然后直接在merge里就可以用了。

但我用int数组就怎么都不行，郁闷，最后还是在调用的时候加了这个参数的传递。

时间复杂度是

但是因为用到了辅助数组，所以空间复杂度是

提交通过了，用时10ms

• 快速排序

?

public class Solution {
    public static int[] sortArray(int[] nums) {
        int lo = 0;
        int hi = nums.length - 1;
        sort(nums,lo,hi);
        return nums;
    }

    public static void sort(int[] a,int lo,int hi){
        if(hi<=lo){
            return;
        }
        int part = part(a,lo,hi);
        sort(a,lo,part-1);
        sort(a,part+1,hi);
    }

    public static int part(int[]a,int lo,int hi){
        int key = a[lo];
        int left = lo+1;
        int right = hi;
        while(true){
            while (a[right] > key){
                right--;
                if(right == lo){
                    break;
                }
            }
            while (a[left] < key){
                left++;
                if(left == hi){
                    break;
                }
            }
            if(left >= right){
                break;
            }else{
                exchange(a,left,right);
            }
        }
        exchange(a,lo,right);
        return right;
    }

    public static void exchange(int[] a,int i,int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

最后提交的时候执行出错了，输入数组是：

[3,-1]

于是稍微修改了下，当数组太小的时候就直接插入排序就可以了。

时间复杂度是

空间复杂度是，主要占用空间来自递归的栈空间

另外选择排序，希尔排序，快速排序都是不稳定排序。

啊，完事！看会中国好声音去（咸鱼躺平