外贸网站制作时间及费用百度竞价ocpc
归并排序（英语：Merge sort，或mergesort），是建立在归并操作上的一种有效的排序算法，效率为O(n*log n)} 。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
import java.util.Arrays;
import java.util.Random;
public class C02_MergeSort {merge sortpublic static void mergeSort(int[] a) {if (a == null || a.length < 2) {return;}process(a, 0, a.length - 1);}public static void process(int[] a, int left, int right) {if (left >= right) {return;}// int mid = (left + right)/2;int mid = left + ((right - left) >> 1);process(a, left, mid);process(a, mid + 1, right);merge(a, left, mid, right);}public static void merge(int a[], int left, int mid, int right) {int[] help = new int[right - left + 1];int i = left;int j = mid + 1;int p = 0;while (i <= mid && j <= right) {if (a[i] <= a[j]) {help[p++] = a[i++];} else if (a[i] > a[j]) {help[p++] = a[j++];} //help[p++] = a[i] < a[j] ? a[i++] : a[j++];//也可以是这句}while (i <= mid) {help[p++] = a[i++];}while (j <= right) {help[p++] = a[j++];}// 复制数组for (int k = 0; k < help.length; k++) {a[left++] = help[k];}}/// for testpublic static int[] getArray(int len, int val) {int arr[] = new int[len];Random random = new Random();for (int i = 0; i < arr.length; i++) {arr[i] = random.nextInt(val);}return arr;}public static void printArr(int[] arr) {for (int i : arr) {System.out.print(i + " ");}System.out.println();}private static boolean isEqual(int[] arr, int[] arr2) {if(arr==null||arr2==null||arr.length!=arr2.length){return false;}boolean isSame = true;for (int i = 0; i < arr2.length; i++) {if(arr[i]!=arr2[i]){isSame = false;break;}}return isSame;}public static void main(String[] args) {int len = 50;int val = 100;int times = 100000;int arr[];int arr2[];boolean isSame = true;while(times-->0){arr = getArray(len, val);arr2 = Arrays.copyOf(arr, len);Arrays.sort(arr);mergeSort(arr2);isSame = isEqual(arr,arr2);if(!isSame){printArr(arr);break;}}System.out.println(isSame);}
}
/* 小和问题在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。例子：[1,3,4,2,5]1左边比1小的数，没有；3左边比3小的数，1；4左边比4小的数，1、3；2左边比2小的数，1；5左边比5小的数，1、3、4、2；所以小和为1+1+3+1+1+3+4+2=16*/
import java.util.Random;
public class C03_LittleSum {public static int sum(int[] a) {if (a == null || a.length < 2) {return 0;}return process(a, 0, a.length - 1);}public static int process(int[] a, int left, int right) {if (left >= right) {return 0;}int mid = left + ((right - left) >> 1);return process(a, left, mid) + process(a, mid + 1, right) + merge(a, left, mid, right);}public static int merge(int[] a, int left, int mid, int right) {int[] help = new int[right - left + 1];int i = left;int j = mid + 1;int p = 0;int res = 0;while (i <= mid && j <= right) {res += a[i] < a[j] ? a[i] * (right - j + 1) : 0;help[p++] = a[i] < a[j] ? a[i++] : a[j++];}while (i <= mid) {help[p++] = a[i++];}while (j <= right) {help[p++] = a[j++];}for (int k = 0; k < help.length; k++) {a[left++] = help[k];}return res;}/// for testpublic static int[] getArray(int len, int val) {int arr[] = new int[len];Random random = new Random();for (int i = 0; i < arr.length; i++) {arr[i] = random.nextInt(val);}return arr;}public static void printArr(int[] arr) {for (int i : arr) {System.out.print(i + " ");}System.out.println();}public static void main(String[] args) {int arr[] = getArray(10, 10);printArr(arr);System.out.println(sum(arr));}
}
在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，请打印所有逆序对
也就是一个无序数组，输出左边大于右边的数，与小和问题相反
import java.util.Random;
public class C04_InvertedSeq {public static void inSeq(int[] a) {if (a == null || a.length < 2) {return;}process(a, 0, a.length - 1);}public static void process(int a[], int left, int right) {if (left == right) {return;}int mid = left + ((right - left) >> 1);process(a, left, mid);process(a, mid+1, right);merge(a, left, mid, right);}public static void merge(int[] a, int left, int mid, int right) {int[] help = new int[right - left + 1];int i = left;int j = mid + 1;int p = 0;while (i <= mid && j <= right) {if(a[i] > a[j]){for (int k = i; k <= mid; k++) {System.out.println(a[k]+","+a[j]);}help[p++]= a[j++];}else {help[p++] = a[i++];}}while (i <= mid) {help[p++] = a[i++];}while (j <= right) {help[p++] = a[j++];}for(int k = 0;k<help.length;k++){a[left++] = help[k];}}/// for testpublic static int[] getArray(int len, int val) {int arr[] = new int[len];Random random = new Random();for (int i = 0; i < arr.length; i++) {arr[i] = random.nextInt(val);}return arr;}public static void printArr(int[] arr) {for (int i : arr) {System.out.print(i + " ");}System.out.println();}public static void main(String[] args) {int arr[] = getArray(5, 10);printArr(arr);inSeq(arr);printArr(arr);}
}