算法归纳（一）

（1）、给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)

public class Demo1 {
    /***
     * 给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，
     * 大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)
     */
    public static void main(String[] args) {
        Sort(new int[]{5, 6, 3, 4, 5, 7, 8}, 5);
    }

    public static void Sort(int[] arr, int num) {
        int point = -1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] <= num) {
                swap(arr, ++point, i);
            }
        }
        print(arr);
    }

    public static void swap(int[] arr, int l, int r) {
        if(l == r){
            return;
        }
        arr[l] = arr[l] + arr[r];
        arr[r] = arr[l] - arr[r];
        arr[l] = arr[l] - arr[r];
        System.out.println(arr[l]+"\t"+arr[r]);
    }

    public static void print(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "\t");
        }
    }
}

（2）、给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)

public class Demo2 {
    /***
     * 给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在
     * 数组的中间，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)
     */
    public static void main(String[] args) {
        sort(new int[]{5, 2, 3, 6, 5, 9, 8, 10, 15, 5}, 6);
    }

    public static void sort(int arr[], int num) {
        int left = -1, right = arr.length;
        int i = 0;
        while (i < right) {
            if (arr[i] < num) {//如果被分析的数小于用来比较的数值，则把这个数与其指针left指向的下一个数值交换，因为指针指向的下一个值是被分析过的，所以交换后不需要分析直接i++
                swap(arr, i++, ++left);
            } else if (arr[i] > num) {
                swap(arr, i, --right);//被交换过的数字没有被分析过，所以i指向不变
            } else{
                i++;//比较的两个数相等则直接跳向下一个
            }
        }
        print(arr);
    }

    public static void swap(int[] arr, int l, int r) {
        if (l == r) {
            return;
        }
        //运用的原理是a^a的值是0，0^ b的值是 b
        arr[l] = arr[l] ^ arr[r];//左右
        arr[r] = arr[l] ^ arr[r];//左右右=左
        arr[l] = arr[l] ^ arr[r];//左右左=右
        //arr[l]+arr[r]可能会超过int的范围
        /*arr[l]=arr[l]+arr[r];
        arr[r]=arr[l]-arr[r];
        arr[l]=arr[l]-arr[r];*/
    }

    public static void print(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "\t");
        }
    }
}

（3）、小和问题

public class Demo3 {
    /***
     * 在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组
     * 的小和。
     * 解法一：双层循环，时间复杂度O(N^2)
     * 解法二：利用归并排序
     */
    public static void main(String[] args) {
        System.out.println(smallSum(new int[]{1, 3, 4, 2, 5}));
    }

    public static int smallSum(int arr[]) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        return mergeSort(arr, 0, arr.length - 1);
    }

    public static int mergeSort(int[] arr, int left, int right) {
        if (left == right) {
            return 0;
        }
        int middle = left + ((right - left) >> 1);//求出中间的数值
        //每一步榨取出一小部分的数值，保证每次左边部分的数组只需要被右部分榨取即可
        return mergeSort(arr, left, middle) + mergeSort(arr, middle + 1, right) + merge(arr, left, middle, right);
    }

    public static int merge(int[] arr, int left, int middle, int right) {
        int[] p = new int[right - left + 1];//用来存放排好序的数字序列的临时数组
        int i = 0;
        int p1 = left;//指向左部分数组的第一个数值
        int p2 = middle + 1;//指向右部分数组的第一个数值
        int sum = 0;//小和存储
        while (p1 <= middle && p2 <= right) {//左部分或者右部分有一方已经全部复制排序到了临时数组则退出该循环
            sum += arr[p1] < arr[p2] ? (right - p2 + 1) * arr[p1] : 0;//如果左面的数组当前值小于右边的数组则小和增加
            p[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];//左右数组经过依次比较必然有一个数进入临时数组
        }
        //下面两个循环必有一个执行，用于将未完全拷贝的数组依次按序拷贝进新数组
        while (p1 <= middle) {
            p[i++] = arr[p1++];
        }
        while (p2 <= right) {
            p[i++] = arr[p2++];
        }
        i = 0;
        //将临时数组中的数据拷贝进新数组
        while (i < p.length) {
            arr[left + i] = p[i++];
        }
        return sum;
    }
}

（4）、逆序对问题

在一个数组中，左边的数如果比右边的数大，则折两个数构成一个逆序对，请打印所有逆序对。

public class Demo4 {
    public static void main(String[] args) {
        inverse(new int[]{4, 3, 2, 1});
    }

    public static void inverse(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        mergeSort(arr, 0, arr.length - 1);
    }

    public static void mergeSort(int[] arr, int left, int right) {
        if (left == right) {
            return;
        }
        int middle = left + ((right - left) >> 1);
        mergeSort(arr, left, middle);
        mergeSort(arr, middle + 1, right);
        merge(arr, left, middle, right);
    }

    public static void merge(int[] arr, int left, int middle, int right) {
        int[] p = new int[right - left + 1];
        int i = 0;
        int p1 = left;
        int p2 = middle + 1;
        while (p1 <= middle && p2 <= right) {
            if (arr[p1] > arr[p2]) {
                print(arr, arr[p1], p2, right);
            }
            p[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];//左右数组经过依次比较必然有一个数进入临时数组
        }
        while (p1 <= middle) {
            p[i++] = arr[p1++];
        }
        while (p2 <= right) {
            p[i++] = arr[p2++];
        }
        i = 0;
        while (i < p.length) {
            arr[left + i] = p[i++];
        }
    }

    public static void print(int[] arr, int num, int left, int right) {
        while (left <= right) {
            System.out.println("逆序对：" + num + "," + arr[left++]);
        }
    }
}