1, the introduction
Merge sort is an efficient sorting algorithm based on merge operation. This algorithm is a very typical application of Divide and Conquer. Merge the ordered subsets to get a completely ordered set. That is, first order each subset, and then order between subsets. If two ordered sets are merged into one ordered set, it is called 2-way merging.
2, analysis,
- Divide the input set of length N into two subsets of length N /2;
- Merge sort is used for these two subsets respectively.
- Merge the two sorted subsets into a final sorted set.
Merge to order the whole thing
3, implementation,
3.1, the recursion
/ * * *@description: merge sort - recursive implementation *@author: erlang
* @since: "* / 2020-09-28
public class MergeSort {
/** * recursively sort **@paramArr Array to be sorted */
public static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
process(arr, 0, arr.length - 1);
}
/ * * *@paramArr Array to process *@paramLeft Left border *@paramRight has boundaries */
private static void process(int[] arr, int left, int right) {
if (left == right) {
return;
}
int mid = left + ((right - left) >> 1);
process(arr, left, mid);
process(arr, mid + 1, right);
merge(arr, left, mid, right);
}
/** * merge **@paramArr handles arrays *@paramLeft Left border *@paramMid Indicates the middle boundary *@paramRight right border */
public static void merge(int[] arr, int left, int mid, int right) {
int[] help = new int[right - left + 1];
int index = 0;
int p1 = left;
int p2 = mid + 1;
while (p1 <= mid && p2 <= right) {
help[index++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
}
// Store the rest of the elements in [left, mid] or [mid + 1, right] into the help array
while (p1 <= mid) {
help[index++] = arr[p1++];
}
while (p2 <= right) {
help[index++] = arr[p2++];
}
// Put the elements in help back into the [left, right] range of arR
for (int i = 0; i < help.length; i++) { arr[left + i] = help[i]; }}public static void main(String[] args) {
ArraySortUtils.testSort(MergeSort::mergeSort, 100.100); }}Copy the code3.2, iterations,
/ * * *@description: merge sort - iterative implementation *@author: erlang
* @since: the 2020-09-28 22:55 * /
public class MergeSort {
public static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int n = arr.length;
// Currently ordered, left length
int mergeSize = 1;
while (mergeSize < n) {
int left = 0;
while (left < n) {
int mid = left + mergeSize - 1;
if (mid >= n) {
break;
}
int right = Math.min(mid + mergeSize, n - 1);
merge(arr, left, mid, right);
left = right + 1;
}
// If mergeSize is greater than half the array length, the array is completely sorted
Prevent mergeSize << 1 from exceeding the length of int
if (mergeSize > (n >> 1)) {
break;
}
// Double each time
mergeSize <<= 1; }}/** * merge **@paramArr handles arrays *@paramLeft Left border *@paramMid Indicates the middle boundary *@paramRight right border */
public static void merge(int[] arr, int left, int mid, int right) {
int[] help = new int[right - left + 1];
int index = 0;
int p1 = left;
int p2 = mid + 1;
while (p1 <= mid && p2 <= right) {
help[index++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= mid) {
help[index++] = arr[p1++];
}
while (p2 <= right) {
help[index++] = arr[p2++];
}
for (int i = 0; i < help.length; i++) { arr[left + i] = help[i]; }}public static void main(String[] args) {
ArraySortUtils.testSort(MergeSort::mergeSort, 100.100); }}Copy the code4, in actual combat
4.1 decimals and
4.4.1, description,
In an array, the sum of the smaller numbers to the left of a number is called the sum of the smallest numbers, and the sum of the smallest numbers is called the sum of the array. Find the small sum of arrays.
Example:,3,4,2,5 [1]
- The number to the left of 1 less than 1: none
- The number to the left of 3 less than 3:1
- Numbers to the left of 4 less than 4:1, 3
- The number to the left of 2 less than 2:1
- Numbers less than 5 to the left of 5:1, 3, 4, 2
- So the small sum of the array is 1+1+3+1+1+3+4+2=16
4.1.2, implementation,
/ * * *@description: small and *@author: erlang
* @since: the 2020-10-13 21:49 * /
public class SmallSum {
public static int smallSum(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
return process(arr, 0, arr.length - 1);
}
private static int process(int[] arr, int left, int right) {
if (left == right) {
return 0;
}
int mid = left + ((right - left) >> 1);
return process(arr, left, mid)
+
process(arr, mid + 1, right)
+
merge(arr, left, mid, right);
}
private static int merge(int[] arr, int left, int mid, int right) {
int[] help = new int[right - left + 1];
int index = 0;
int p1 = left;
int p2 = mid + 1;
int sum = 0;
while (p1 <= mid && p2 <= right) {
sum += arr[p1] < arr[p2] ? (right - p2 + 1) * arr[p1] : 0;
help[index++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= mid) {
help[index++] = arr[p1++];
}
while (p2 <= right) {
help[index++] = arr[p2++];
}
for (int i = 0; i < help.length; i++) {
arr[left + i] = help[i];
}
return sum;
}
// for test
public static int comparator(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
int res = 0;
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
res += arr[j] < arr[i] ? arr[j] : 0; }}return res;
}
// for test
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 10;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = ArraySortUtils.generateRandomArray(maxSize, maxValue);
int[] arr2 = ArraySortUtils.copyArray(arr1);
int smallSum = smallSum(arr1);
int comparator = comparator(arr2);
if(smallSum ! = comparator) { System.out.println("smallSum ==> " + smallSum);
System.out.println("comparator ==> " + comparator);
succeed = false;
ArraySortUtils.printArray(arr1);
ArraySortUtils.printArray(arr2);
break;
}
}
System.out.println(succeed ? "Nice!" : "Fail!"); }}Copy the code4.2,Pairs of inversions in an array
2, description,
Two digits in an array form a reverse pair if the preceding digit is larger than the following digit. Enter an array and find the total number of inversions in the array.
Example 1:
Input:,5,6,4 [7]
Output: 5
4.2.2, implementation,
class Solution {
public int reversePairs(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
return process(nums, 0, nums.length - 1);
}
private static int process(int[] arr, int left, int right) {
if (left == right) {
return 0;
}
int mid = left + ((right - left) >> 1);
return process(arr, left, mid)
+
process(arr, mid + 1, right)
+
merge(arr, left, mid, right);
}
private static int merge(int[] arr, int left, int mid, int right) {
int[] help = new int[right - left + 1];
int index = 0;
int p1 = left;
int p2 = mid + 1;
int sum = 0;
while (p1 <= mid && p2 <= right) {
sum += arr[p1] > arr[p2] ? (right - p2 + 1) : 0;
help[index++] = arr[p1] > arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= mid) {
help[index++] = arr[p1++];
}
while (p2 <= right) {
help[index++] = arr[p2++];
}
for (int i = 0; i < help.length; i++) {
arr[left + i] = help[i];
}
returnsum; }}Copy the code5. Tool classes
5.1, MergeSortUtils
/ * * *@description: merge sort utility class *@author: erlang
* @since: the 2020-10-12 22:32 * /
public class MergeSortUtils {
/** * merge **@paramArr handles arrays *@paramLeft Left border *@paramMid Indicates the middle boundary *@paramRight right border */
public static void merge(int[] arr, int left, int mid, int right) {
int[] help = new int[right - left + 1];
int index = 0;
int p1 = left;
int p2 = mid + 1;
while (p1 <= mid && p2 <= right) {
help[index++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= mid) {
help[index++] = arr[p1++];
}
while (p2 <= right) {
help[index++] = arr[p2++];
}
for (int i = 0; i < help.length; i++) { arr[left + i] = help[i]; }}}Copy the code5.2, ArraySortUtils
import java.util.Arrays;
import java.util.function.Consumer;
/ * * *@description: Array sort tool *@author: erlang
* @since: the 2020-08-29 and * /
public class ArraySortUtils {
/** * Randomly generates the array to be tested **@paramMaxSize Maximum array length *@paramMaxValue The largest value * in the array@returnReturns the generated array */
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
/** * outputs the element ** of the array@paramArray arr * /
public static void printArray(int[] arr) {
System.out.println("");
System.out.println("+++++++++++++++++++++++++++++++++++++++++++++++++++START");
for (int value : arr) {
System.out.print(value + "");
}
System.out.println("");
System.out.println("+++++++++++++++++++++++++++++++++++++++++++++++++++END");
}
public static void comparator(int[] arr) {
Arrays.sort(arr);
}
/** * re-copy a new array **@paramArr Array to copy *@returnReturns the copied new array */
public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
int[] res = new int[arr.length];
System.arraycopy(arr, 0, res, 0, arr.length);
return res;
}
/** * compares whether the elements of two arrays are equal **@paramArr1 Array 1 * to be compared@paramArr2 The array to compare 2 star@returnReturns the verification result true/false */
public static boolean isEqual(int[] arr1, int[] arr2) {
if (arr1 == null && arr2 == null) {
return true;
}
if (arr1 == null || arr2 == null) {
return false;
}
if(arr1.length ! = arr2.length) {return false;
}
for (int i = 0; i < arr1.length; i++) {
if(arr1[i] ! = arr2[i]) {return false; }}return true;
}
/** * Test whether the sorting result of the sorting method is correct **@paramThe consumer calls back the user - defined sorting method *@paramMaxSize Maximum array length *@paramMaxValue Specifies the largest number in the array, i.e. 0-maxValue */
public static void testSort(Consumer<int[]> consumer, int maxSize, int maxValue) {
int testTime = 5000;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
// Generate a new array
int[] arr1 = ArraySortUtils.generateRandomArray(maxSize, maxValue);
// Copy the new array
int[] arr2 = copyArray(arr1);
// Call back the user-defined sort method to sort arri1
consumer.accept(arr1);
// Use the system's own sorting method to sort arr2
comparator(arr2);
// Compare the results of the two treatments
if(! isEqual(arr1, arr2)) { succeed =false;
printArray(arr1);
printArray(arr2);
break; }}// Outputs test results
System.out.println(succeed ? "Nice!" : "Fail!"); }}Copy the code