Skip to content

Latest commit

 

History

History
383 lines (317 loc) · 10.5 KB

02高级排序问题.md

File metadata and controls

383 lines (317 loc) · 10.5 KB
Raw

高级排序问题

归并排序

归并排序的思想是将数组分成两部分，分别进行排序，然后归并起来。


1. 归并方法

归并方法将数组中两个已经排序的部分归并成一个。

public abstract class MergeSort<T extends Comparable<T>> extends Sort<T> {
    protected T[] aux;//自定义的辅助数组

    /**
     * 合并[l,mid]和[mid+1,r]
     * 其中[l,mid]、[mid+1，r]是已经有序的序列
     */
    protected void merge(T[] arr,int l,int mid,int r){
       int k=l;
       //i数值在[l,mid]之间
       int i=l;
       //j数值在[mid+1,r]之间
       int j=mid+1;
       while(i<=mid && j<=r){
           if(less(arr[i],arr[j])){
               aux[k++]=arr[i++];
           }else{
               aux[k++]=arr[j++];
           }
       }
       while(i<=mid){
           aux[k++]=arr[i++];
       }
       while(j<=r){
           aux[k++]=arr[j++];
       }

       for(int index=l;index<=r;index++){
           arr[index]=aux[index];
       }
    }
}

2. 自顶向下归并排序

将一个大数组分成两个小数组去求解。

因为每次都将问题对半分成两个子问题，这种对半分的算法复杂度一般为 O(NlogN)。

/**
 * 将一个大数组分成两个小数组去求解。
 * 因为每次都将问题对半分成两个子问题，这种对半分的算法复杂度一般为 O(NlogN)。
 */
public class Up2DownMergeSort<T extends Comparable<T>> extends  MergeSort<T>{
    @Override
    public void sort(T[] arr) {
        //aux=new T[nums.length];//error 因为存在类型擦除
        //正确方式
        aux = (T[]) new Comparable[arr.length];
        sort(arr,0,arr.length-1);
    }

    private void sort(T[] arr,int l,int r){
        //l==r 就只有一个元素，已经排好序了
        if(l>=r){
            return;
        }
        int mid=(r-l)/2+l;
        sort(arr,l,mid);
        sort(arr,mid+1,r);
        merge(arr,l,mid,r);
    }
}

3. 自底向上归并排序

先归并那些微型数组，然后成对归并得到的微型数组。

public class Down2UpMergeSort<T extends Comparable<T>> extends MergeSort<T> {

    @Override
    public void sort(T[] nums) {

        int N = nums.length;
        aux = (T[]) new Comparable[N];

        for (int sz = 1; sz < N; sz += sz) {
            for (int lo = 0; lo < N - sz; lo += sz + sz) {
                merge(nums, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
            }
        }
    }
}

4.归并排序思想统计逆序对

/**
 * 使用归并排序思路求解逆序对
 */
public class ReverseNum {
    /**
     * 暴力求解
     */
    public int getNum1(int[] arr){
        int res=0;
        int N=arr.length;
        for(int i=0;i<N-1;i++){
            for(int j=i+1;j<N;j++){
                if(arr[i]>arr[j]){
                    res++;
                }
            }
        }
        return res;
    }

    /**
     * 使用归并排序思路求解逆序对
     */
    public int getNum2(int[] arr){
        return sort(arr);
    }

    private int sort(int[] arr){
        return sort(arr,0,arr.length-1);
    }

    private int sort(int[] arr,int l,int r){
        if(l==r){
            return 0;
        }
        int m=l+(r-l)/2;
        int res=0;
        res+=sort(arr,l,m);
        res+=sort(arr,m+1,r);
        res+=merge(arr,l,m,r);
        return res;
    }

    private int merge(int[] arr,int l,int mid,int r){
        int[] aux=new int[r-l+1];
        int k=0;
        //i数值在[l,mid]之间
        int i=l;
        //j数值在[mid+1,r]之间
        int j=mid+1;
        int res=0;
        while(i<=mid && j<=r){
            if(arr[i]<=arr[j]){
                aux[k++]=arr[i++];
            }else{
                res+=mid-i+1;
                aux[k++]=arr[j++];
            }
        }
        while(i<=mid){
            aux[k++]=arr[i++];
        }
        while(j<=r){
            aux[k++]=arr[j++];
        }

        //arr的[l,r]
        for(int index=0;index<k;index++){
            arr[index+l]=aux[index];
        }
        return res;
    }
}

5.归并排序思想求解小和问题

  • 小和问题： 在一个数列中，任意元素p左边所有比p小的数之和，即为小和。 数列中所有元素的小和之和就是小和问题。
public class SmallNum {
    /**
     * 使用归并排序思路求解逆序对
     */
    public int getSmallNum(int[] arr){
        return sort(arr);
    }

    private int sort(int[] arr){
        return sort(arr,0,arr.length-1);
    }

    private int sort(int[] arr,int l,int r){
        if(l==r){
            return 0;
        }
        int m=l+(r-l)/2;
        return sort(arr,l,m)+sort(arr,m+1,r)+merge(arr,l,m,r);
    }

    private int merge(int[] arr,int l,int mid,int r){
        int[] aux=new int[r-l+1];
        int k=0;
        //i数值在[l,mid]之间
        int i=l;
        //j数值在[mid+1,r]之间
        int j=mid+1;
        int res=0;
        while(i<=mid && j<=r){
            if(arr[i]<arr[j]){
                //右侧(r-j+1)个元素都比arr[i]大
                //arr[i]对于这些元素就是小数
                res+=(r-j+1)*arr[i];
                aux[k++]=arr[i++];
            }else{
                aux[k++]=arr[j++];
            }
        }
        while(i<=mid){
            aux[k++]=arr[i++];
        }
        while(j<=r){
            aux[k++]=arr[j++];
        }

        //arr的[l,r]
        for(int index=0;index<k;index++){
            arr[index+l]=aux[index];
        }
        return res;
    }
}

快速排序

1. 基本算法

  • 归并排序将数组分为两个子数组分别排序，并将有序的子数组归并使得整个数组排序；
  • 快速排序通过一个切分元素将数组分为两个子数组，左子数组小于等于切分元素，右子数组大于等于切分元素，将这两个子数组排序也就将整个数组排序了。

public class QuickSort<T extends Comparable<T>> extends Sort<T> {

    @Override
    public void sort(T[] nums) {
        shuffle(nums);
        sort(nums, 0, nums.length - 1);
    }

    private void sort(T[] nums, int l, int h) {
        if (h <= l)
            return;
        int j = partition(nums, l, h);
        sort(nums, l, j - 1);
        sort(nums, j + 1, h);
    }

    private void shuffle(T[] nums) {
        List<Comparable> list = Arrays.asList(nums);
        Collections.shuffle(list);
        list.toArray(nums);
    }
}

2. 切分

取 a[l] 作为切分元素，然后从数组的左端向右扫描直到找到第一个大于等于它的元素，再从数组的右端向左扫描找到第一个小于它的元素，交换这两个元素。不断进行这个过程，就可以保证左指针 i 的左侧元素都不大于切分元素，右指针 j 的右侧元素都不小于切分元素。当两个指针相遇时，将切分元素 a[l] 和 a[j] 交换位置。


private int partition(T[] arr,int l,int r){
    T pivot=arr[l];
 
    while(l<r){
        //从数组的右端向左扫描找到第一个小于pivot的元素，交换这两个元素
        while(!less(arr[r],pivot) && l<r){
            r--;
        }
        arr[l]=arr[r];
        //从数组的左端向右扫描找到第一个大于pivot的元素，交换这两个元素
        while(!less(pivot,arr[l]) && l<r){
            l++;
        }
        arr[r]=arr[l];
    }
    arr[l]=pivot;
    return l;
}

3. 性能分析

快速排序是原地排序，不需要辅助数组，但是递归调用需要辅助栈。

快速排序最好的情况下是每次都正好将数组对半分，这样递归调用次数才是最少的。这种情况下比较次数为 CN=2CN/2+N，复杂度为 O(NlogN)。

最坏的情况下，第一次从最小的元素切分，第二次从第二小的元素切分，如此这般。因此最坏的情况下需要比较 N2/2。为了防止数组最开始就是有序的，在进行快速排序时需要随机打乱数组。

4. 算法改进

4.1 切换到插入排序

因为快速排序在小数组中也会递归调用自己，对于小数组，插入排序比快速排序的性能更好，因此在小数组中可以切换到插入排序。

4.2 三数取中

最好的情况下是每次都能取数组的中位数作为切分元素，但是计算中位数的代价很高。一种折中方法是取 3 个元素，并将大小居中的元素作为切分元素。

4.3 三向切分

对于有大量重复元素的数组，可以将数组切分为三部分，分别对应小于、等于和大于切分元素。

三向切分快速排序对于有大量重复元素的随机数组可以在线性时间内完成排序。

public class ThreeWayQuickSort<T extends Comparable<T>> extends QuickSort<T> {

    @Override
    protected void sort(T[] nums, int l, int h) {
        if (h <= l) {
            return;
        }
        int lt = l, i = l + 1, gt = h;
        T v = nums[l];
        while (i <= gt) {
            int cmp = nums[i].compareTo(v);
            if (cmp < 0) {
                swap(nums, lt++, i);
                i++;
            } else if (cmp > 0) {
                swap(nums, i, gt--);
            } else {
                i++;
            }
        }
        sort(nums, l, lt - 1);
        sort(nums, gt + 1, h);
    }
}

5. 基于切分的快速选择算法

快速排序的 partition() 方法，会返回一个整数 j 使得 a[l..j-1] 小于等于 a[j]，且 a[j+1..h] 大于等于 a[j]，此时 a[j] 就是数组的第 j 大元素。

可以利用这个特性找出数组的第 k 个元素。

该算法是线性级别的，假设每次能将数组二分，那么比较的总次数为 (N+N/2+N/4+..)，直到找到第 k 个元素，这个和显然小于 2N。

public T select(T[] nums, int k) {
    int l = 0, h = nums.length - 1;
    while (h > l) {
        int j = partition(nums, l, h);

        if (j == k) {
            return nums[k];

        } else if (j > k) {
            h = j - 1;

        } else {
            l = j + 1;
        }
    }
    return nums[k];
}