2_排序.md

排序

1、数组中的逆序对

数组中的逆序对

//思路：利用归并排序算法
//在合并两个有序数组中，
//[l,mid]
//[mid+1,r]
//如果 arr[i] > arr[j]
//则 arr[i] 后面的元素都会大于 arr[j],即 [i,mid] 的长度就是逆序对数

private long P; //逆序对数

public int InversePairs(int [] array) {
    sort(array,0,array.length-1);
    return (int)(P%1000000007);
}

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

//合并 [l,m] 和 [m+1,r] 两个有序数组
private void merge(int[] arr,int l,int m,int r){
    int[] newArr = new int[r-l+1];
    int index =0;
    int i=l;
    int j=m+1;
    while(i<=m && j<=r){
        if(arr[i]<=arr[j]){
            newArr[index++]=arr[i++];
        }else{ //arr[i]>arr[j]，arr[i]后面的元素都会大于 arr[j]
            P+=(m-i+1);
            newArr[index++]=arr[j++];
        }
    }
    while(i<=m){
        newArr[index++]=arr[i++];
    }
    while(j<=r){
        newArr[index++]=arr[j++];
    }
    index=0;
    for(int k=l;k<=r;k++){
        arr[k]=newArr[index++];
    }
}

2、最小的 k 个数

最小的 k 个数

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
    ArrayList<Integer> res = new ArrayList<>();
    if(k<=0 || k>input.length){
        return res;
    }
    int index = findKthSmallest(input,k-1);
    if(index==-1){
        return res;
    }

    for(int i=0;i<=index;i++){
        res.add(input[i]);
    }
    return res;
}

//查找数组中第 k 小的元素
private int findKthSmallest(int[] input,int k){
    int l=0,r=input.length-1;
    while (l<=r){
        int p = partion(input,l,r);
        if(p==k){
            return p;
        }else if(p<k){
            l = p+1;
        }else{
            assert p>k;
            r = p-1;
        }
    }
    return -1;
}

//使用快速排序中的切分思路
private int partion(int[] nums,int start,int end){
    int pivot = nums[start];

    while (start<end){
        while (start<end && nums[end]>=pivot){
            end--;
        }
        nums[start]=nums[end];
        while(start<end && nums[start]<=pivot){
            start++;
        }
        nums[end]=nums[start];
    }
    nums[start] = pivot;
    return start;
}

3、颜色分类

颜色分类

//思路:
//基于快速排序的 3 路快排思路

public void sortColors(int[] nums) {
    int zero = -1;
    int two = nums.length;

    for(int i=0;i<two;){
        if(nums[i]==0){
            zero++;
            swap(nums,zero,i);
            i++;
        }else if(nums[i]==1){
            i++;
        }else{
            assert nums[i]==2;
            two--;
            swap(nums,two,i);
        }
    }
}

private void swap(int[] nums,int i,int j){
    int tmp =nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}