排序算法简单问题（Java）

问题：以尽量快的效率求出一个乱序数组中按数值顺序的第k小的元素。

  解法一：先用快排进行排序，然后在找到第k+1个元素，时间复杂度为nlg(n)   
  解法二：用快排划分为俩个子序列，找到主元素的下标,该下标+1=x即为主元素在该数组的第x小元素，判断k与x的大小缩小范围，时间复杂度期望O(n),最差O(n^2)

 下面只说了解法二：

public class Test2 {
    public static void main(String[] args) {
        int[] arr = new int[]{2,4,5,6,7,1,9,8,3};
        System.out.println(f2(arr,6,0,arr.length-1));
    }

    static int f2(int[] arr,int k,int p,int r){
        int q = partition(arr,p,r);  //此时q前面的数都比q小，后面的数都比q大，所以该数为第q+1大的数
        if(q-p < k-1){
            return f2(arr,k-1-q+p,q+1,r);
        }else if(q-p > k-1){
            return f2(arr,k,p,q-1);
        }else{
            return arr[q];
        }
    }
    //双向扫描，快排
    static int partition(int[] arr,int p,int r){
        int pivot=arr[p];
        int left=p+1;
        int right=r;
        while(left<=right){
            while(left<=right && arr[left]<=pivot) left++;
            while(left<=right && arr[right]>pivot) right--;
            if(left<right)
                swap(arr,left,right);
        }
        swap(arr,p,right);
        return right;
    }
    static void swap(int[] arr,int l,int r) {
        int t = arr[l];
        arr[l] = arr[r];
        arr[r] = t;
    }
}

问题：找出无序数组中出现次数超过一半的元素

  方法一： 排序后，中间下标元素就是我们要找的,时间复杂度nlg(n)
  方法二： 顺序统计，数组长度为n，求第n/2大的元素，时间复杂度：n

  方法三： 数不相同count就减一，count为0就改变cur值，最后一定只有出现次数最多的元素的count>0

但如果不允许挪动数组中元素的位置呢？

方法三：

public class Test2 {
    public static void main(String[] args) {
        int[] arr = new int[]{2,4,5,6,7,1,9,8,3};
        System.out.println(f2(arr,6,0,arr.length-1));
    }

    static int f3(int[] arr){
        //方法三 数不相同count就减一，count为0就改变cur值，最后一定只有出现次数最多的元素的count>0
        int cur=arr[0],count=1;
        for(int i=1;i<arr.length;i++){
            if(cur != arr[i]){
                count--;
            }else{
                count++;
            }
            if(count==0){
                cur=arr[i];
                count=1;
            }
        }
        return cur;
    }
}

那此题目，在不允许挪动数组中元素的位置的情况下，缩小次数，出现次数最多的元素的出现次数恰好为数组长度的一半呢?

解决：在方法三的基础上加点条件即可：新增无序数组中最后一个元素的计数器
如果最后一位为所求元素，遍历完后，最后一个元素的计数器的值一定为数组长度的一半。
如果最后一位不为所求元素，当要遍历最后一个元素时，
此时方法三中的count值一定为1，因为如果不算最后一个元素的话，满足所求元素出现次数超过数组长度一半，所以此时cur值一定为所求元素。
然后因为最后一个元素的计数器的值不为数组长度的一半，所以cur值即为所求

public class Test2 {
    public static void main(String[] args) {
        int[] arr = new int[]{2,4,5,6,7,1,9,8,3};
        System.out.println(f2(arr,6,0,arr.length-1));
    }

    static int f4(int[] arr) {
        int cur=arr[0],count=0;
        int countLast=0,lastNum=arr[arr.length-1];
        for(int i=0;i<arr.length;i++) {
            if (cur != arr[i]) {
                count--;
            } else {
                count++;
            }
            if (arr[i] == lastNum) {
                countLast++;
            }
            if (i == arr.length - 1) {
                if (countLast == arr.length / 2) {
                    return lastNum;
                } else {
                    return cur;
                }
            }
            if (count == 0) {
                cur = arr[i];
                count=1;
            }
        }
        return cur;
    }
}

问题：最小可用ID：在非负数组（乱序）中找到最小可分配的id（从1开始编号），数据量1000000。
就是在乱序数组（数组大小不超过1000000）中找出最小的从未出现过的数（1～1000000）。

解法一：开辟一个等大+1的数组helper，遍历一遍原数组，在helper相应位置打上标记，然后遍历一遍helper，时间复杂度2n；

public class Test2 {
    public static void main(String[] args) {
        int[] arr = new int[]{3,4,5,1,6,7,8,13,9,27,40,20,2};
        System.out.println(f1(arr));
    }

    static int f1(int[] arr){
        int[] helper = new int[arr.length+1];
        for(int i=0;i<arr.length;i++){
            if(arr[i]<=arr.length){ //如果有元素大于数组长度，说明1～arr.length之间一定不连续，所求的数在该范围内。
                helper[arr[i]]++;
            }
        }
        for(int i=1;i<helper.length;i++){
            if(helper[i]!=1)
                return i;
        }
        return helper.length;
    }
}

解法二：不采用辅助空间，采用求第k小元素的方法
选取一个元素作为主元素，判断主元素的值是否等于其下标值，若等于，则所求在右侧，若主元素值大于其下标则所求在左侧，主元素值不可能小于下标值

public class Test2 {
    public static void main(String[] args) {
        int[] arr = new int[]{3,4,5,1,6,7,8,13,9,27,40,20,2};
        System.out.println(f2(arr,0,arr.length-1));
    }

    static int f2(int[] arr,int p,int r){
        if(p>=r)return p+2; //p为小于所求数的最大数的下标，p+1为所求数的下标，p+2为所求数
        int partition = partition(arr, p, r);
        if(partition +1< arr[partition]){
            return f2(arr,p,partition-1);
        }else {
            return f2(arr,partition+1,r);
        }
    }

    static int partition(int[] arr,int p,int r){
        int pivot=arr[p];
        int left=p+1;
        int right=r;
        while(left<=right){
            while(left<=right && arr[left]<=pivot)left++;
            while(left<=right && arr[right]>pivot)right--;
            if(left<right)
                swap(arr,left,right);
        }
        swap(arr,p,right);
        return right;
    }
    static void swap(int[] arr,int l,int r) {
        int t = arr[l];
        arr[l] = arr[r];
        arr[r] = t;
    }
}

  问题：一个数列，如果左边数大，右边数小，则称这俩个数位为一个逆序对，求一个数列中有多少个逆序对
比如：2 5 1 3 4中逆序对有 2、1 ； 5，1 ；5，3 ；5，4
  解法：类似于归并数组，把数组前后分为俩部分，然后不断细分，直到剩俩个元素，然后升序排序，然后在对俩部分数组a(前半部分)，b(后半部分)中第一个数进行比较，如果b小，那么b数列中的这个元素拥有a数组中元素个数 个逆序对 ，每次比较取走最小的。

public class Test2 {
    public static void main(String[] args) {
        int[] arr = new int[]{2,6,7,8,9,3,1,4,5};
        helper = new int[arr.length];
        System.out.println(f4(arr));
    }

    static int f4(int[] arr){
        sort1(arr,0,arr.length-1);
        return niXuCount;
    }
    static void sort1(int[] arr,int low,int high){
        if(low<high){
            int mid = low+((high-low)>>1);
            sort1(arr,low,mid);
            sort1(arr,mid+1,high);
            merge1(arr,low,mid,high);
        }
    }
    static int[] helper;
    static int niXuCount=0;
    static void merge1(int[] arr,int low,int mid,int high){
        //把arr中数据拷贝到helper中
        for(int i=low;i<=high;i++){
            helper[i]=arr[i];
        }
        int left =low; //左侧队伍的头指针，指向待比较的元素
        int right =mid+1; //右侧队伍的头指针，指向待比较的元素
        int current=low; //原数组指针，指向待填入元素的位置
        while(left<=mid && right<=high){ //俩个队伍都没走完
            if(helper[left]<=helper[right]){
                arr[current]=helper[left];
                left++;
            }else{
                arr[current]=helper[right];
                right++;

                niXuCount+=mid+1-left;  //此时前半部分数组的大小
            }
            current++;
        }
        while(left<=mid){
            arr[current]=helper[left];
            left++;
            current++;
        }
        while(right<=mid){
            arr[current]=helper[right];
            right++;
            current++;
        }
    }
}