Application of merging and sorting thought

​ Preface

    When learning sorting algorithm , First acquaintance merge sort , How can this sort be so difficult from the amount of code . In fact, the idea of merging and sorting is very simple : Put two （ Or more than two ） An ordered table is merged into a new ordered table , That is, the sequence to be sorted is divided into several subsequences , Every subsequence is ordered . Then we combine the ordered subsequences into the whole ordered sequences . Merge sort is an effective sort algorithm based on merge operation . The algorithm adopts Divide and conquer method （Divide and Conquer） A very typical application . The following is a systematic learning with a programming example .

    Time complexity ：O(nlogn)

    Spatial complexity :O(n)

    stability : Stable

Reverse pairs in arrays

      Title Description

    Two numbers in an array , If the number in front is greater than the number in the back , Then these two numbers form a reverse order pair . Enter an array , Find the total number of reverse pairs in this array P. And will P Yes 1000000007 The output of the result of taking the mold . The output P%1000000007.

      Input description :

      Make sure that the same number is not in the input array

      Data range ：

      about %50 The data of ,size<=10^4

      about %75 The data of ,size<=10^5

       about %100 The data of ,size<=2*10^5

      Input example :

     1,2,3,4,5,6,7,0

      Output example :

     7

    The solution idea here is : First, divide the array into subarrays , Count the number of inverse pairs in the word array ; Then count the number of reverse pairs between two adjacent sub arrays . In the process of statistical reverse pairing , You also need to sort the arrays . It's not hard to find out , This sort process is actually merge sort .

    Recursion is used in merging and sorting , In fact, I'm not interested in recursion . Recursion makes the code look cleaner and simpler , But because it uses the stack , The memory size of the stack is certain , Therefore, when the recursion depth is too large , There will be stack overflow StackOverflow Abnormal conditions of . The recursive method can be replaced by the non recursive or circular method .

package cn.edu.ujn.offersword;public class C5_36_InversePairs {/** * @date 2016-09-16 * @number 03 * @author SHQ */public static void main(String[] args) {int [] array = {1,2,3,4,5,6,7,0};System.out.println(InversePairs(array));}    private static int InversePairs(int [] array) {        if(array == null || array.length == 0)        {            return 0;        }        int len = array.length;        int[] copy = new int[len];	//  Set an auxiliary array , Used to store sorting results         for(int i = 0; i < len; i++)        {            copy[i] = array[i];        }        int count = InversePairsCore(array, copy, 0, len-1);        return count;    }        private static int InversePairsCore(int[] array, int[] copy,int low, int high)    {        if(low == high)        {            return 0;        }        int mid = (low + high) >> 1;// Use the shift left operator  >>, The operation speed is higher than that of the division operator         int leftCount = InversePairsCore(array, copy, low, mid) % 1000000007;        int rightCount = InversePairsCore(array, copy, mid+1, high)% 1000000007;        int count = 0;        int i = mid;        int j = high;        int locCopy = high;        while(i >= low && j > mid)        {            if(array[i] > array[j])            {                count += j - mid;                copy[locCopy--] = array[i--];                if(count >= 1000000007) //  The value is too large for remainder                 {                    count %= 1000000007;                }            }            else            {                copy[locCopy--] = array[j--];            }        }        for(; i >= low; i--)        {            copy[locCopy--] = array[i];        }        for(; j > mid; j--)        {            copy[locCopy--] = array[j];        }        for(int s = low; s <= high; s++)        {            array[s] = copy[s];        }        return (leftCount + rightCount + count) % 1000000007;    }}

Merge sort original algorithm

package cn.edu.ujn.offersword; import java.util.Arrays; public class MergeSort {      /**     *  Merge sort      *  brief introduction : Put two （ Or more than two ） An ordered table is merged into a new ordered table   That is, the sequence to be sorted is divided into several subsequences , Every subsequence is ordered .     *  Then we combine the ordered subsequences into the whole ordered sequences      *  The time complexity is O(nlogn)     *  The space complexity is O(n)     *  Stable sorting      * @param nums  Sorted array      * @return  Output ordered array      */      public static int[] sort(int[] nums, int low, int high) {          int mid = (low + high) / 2;          if (low < high) {              //  On the left               sort(nums, low, mid);              //  On the right               sort(nums, mid + 1, high);              //  About merging               merge(nums, low, mid, high);          }          return nums;      }        public static void merge(int[] nums, int low, int mid, int high) {          int[] temp = new int[high - low + 1];          int i = low;//  Left pointer           int j = mid + 1;//  Right pointer           int k = 0;          //  Move the smaller number into the new array first           while (i <= mid && j <= high) {              if (nums[i] < nums[j]) {                  temp[k++] = nums[i++];              } else {                  temp[k++] = nums[j++];              }          }            //  Move the rest of the left into the array           while (i <= mid) {              temp[k++] = nums[i++];          }            //  Move the rest of the right-hand side into the array           while (j <= high) {              temp[k++] = nums[j++];          }            //  Overwrite the Numbers in the new array nums Array           for (int k2 = 0; k2 < temp.length; k2++) {              nums[k2 + low] = temp[k2];          }      }            //  The realization of merging and sorting       public static void main(String[] args) {          int[] nums = { 2, 7, 8, 3, 1, 6, 9, 0, 5, 4 };          MergeSort.sort(nums, 0, nums.length-1);          System.out.println(Arrays.toString(nums));    }  }

  When calculating the length of the linked list , Do not appear the following statement . A null pointer exception will be thrown .

    	int len1 = 0;    	int len2 = getLength(pHead2);    	int difLen = 0;    	// pHeadTmp1 Point to a long linked list     	ListNode pHeadLong = pHead1;    	while(pHeadLong != null){    	len1++;    	pHeadLong = pHeadLong.next;    	}    	// pHeadTmp2 Point to a shorter linked list     	ListNode pHeadShort = pHead2;    	if(len1 > len2){    	difLen = len1 - len2;    	}else{//  Exceptions will be thrown here ( There is no local exception )    	pHeadLong = pHead2;    	pHeadShort = pHead1;    	difLen = len2 - len1;    	}

Corresponding , A function can be implemented separately to calculate the length of the linked list , as follows :

    private static int getLength(ListNode pHead){    	int len = 0;    	while(pHead != null){    	len++;    	pHead = pHead.next;    	}    	return len;    }

​