归并排序整体就是一个简单的递归，左边排好序、右边排好序、让其整体有序。
方法一
这里让其整体有序的过程用了排外序方法。
代码实现：
public static void mergeSort(int[] arr , int l , int r){
if(l >= r)
return;
int mid = l + ((r - l) >> 1);
mergeSort(arr,l,mid);
mergeSort(arr,mid + 1,r);
merge(arr,l,mid,r);
}
private static void merge(int[] arr , int l , int mid , int r){
int[] temp = new int[r - l + 1];
int i = l;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= r){
if(arr[i] > arr[j]){
temp[k++] = arr[j++];
}else {
temp[k++] = arr[i++];
}
}
while (i <= mid){
temp[k++] = arr[i++];
}
while (j <= r){
temp[k++] = arr[j++];
}
for (int m = 0; m < temp.length; m++) {
arr[l + m] = temp[m];
}
}
方法二：
代码实现：
public static int[] mergeSort1(int[] arr){
int l = 0 , r = arr.length - 1;
if(l >= r)
return arr;
int mid = l + ((r - l) >> 1);
int[] left = new int[mid + 1];
int[] right = new int[r - mid];
for (int i = 0 ; i <= mid ; i ++ ){
left[i] = arr[i];
}
for( int i = 0 ; i < right.length ; i ++ ){
right[i] = arr[i + mid + 1];
}
left = mergeSort1(left);
right = mergeSort1(right);
return merge1(left,right);
}
private static int[] merge1(int[] left , int[] right){
int lenl = left.length;
int lenr = right.length;
int[] result = new int[lenl + lenr];
int i = 0 , j = 0, k = 0;
while (i < lenl && j < lenr){
if(left[i] <= right[j]){
result[k++] = left[i++];
}else {
result[k++] = right[j++];
}
}
while (i < lenl){
result[k++] = left[i++];
}
while (j < lenr){
result[k++] = right[j++];
}
return result;
}
完整代码：
public class MyMergeSort {
//整体就是一个简单的递归，左边排好序、右边排好序、让其整体有序
//让其整体有序的过程里用了排外序方法
public static void mergeSort(int[] arr , int l , int r){
if(l >= r)
return;
int mid = l + ((r - l) >> 1);
mergeSort(arr,l,mid);
mergeSort(arr,mid + 1,r);
merge(arr,l,mid,r);
}
private static void merge(int[] arr , int l , int mid , int r){
int[] temp = new int[r - l + 1];
int i = l;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= r){
if(arr[i] > arr[j]){
temp[k++] = arr[j++];
}else {
temp[k++] = arr[i++];
}
}
while (i <= mid){
temp[k++] = arr[i++];
}
while (j <= r){
temp[k++] = arr[j++];
}
for (int m = 0; m < temp.length; m++) {
arr[l + m] = temp[m];
}
}
public static int[] mergeSort1(int[] arr){
int l = 0 , r = arr.length - 1;
if(l >= r)
return arr;
int mid = l + ((r - l) >> 1);
int[] left = new int[mid + 1];
int[] right = new int[r - mid];
for (int i = 0 ; i <= mid ; i ++ ){
left[i] = arr[i];
}
for( int i = 0 ; i < right.length ; i ++ ){
right[i] = arr[i + mid + 1];
}
left = mergeSort1(left);
right = mergeSort1(right);
return merge1(left,right);
}
private static int[] merge1(int[] left , int[] right){
int lenl = left.length;
int lenr = right.length;
int[] result = new int[lenl + lenr];
int i = 0 , j = 0, k = 0;
while (i < lenl && j < lenr){
if(left[i] <= right[j]){
result[k++] = left[i++];
}else {
result[k++] = right[j++];
}
}
while (i < lenl){
result[k++] = left[i++];
}
while (j < lenr){
result[k++] = right[j++];
}
return result;
}
private static boolean isSorted(int[] arr){
int len = arr.length - 1;
for (int i = 0 ; i < len; i ++ ){
if(arr[i] > arr[i + 1])
return false;
}
return true;
}
public static void main(String[] args) {
MyMergeSort myMergeSort = new MyMergeSort();
int N = 1000000;
int[] arr = new int[N];
int rangL = 0;
int rangR = 100000;
for (int i = 0 ; i < N ; i ++ ){
arr[i] = (int)(Math.random() * (rangR - rangL + 1));
}
int[] temp = arr.clone();
Long startTime = System.currentTimeMillis();
myMergeSort.mergeSort(arr,0,arr.length - 1);
Long endTime = System.currentTimeMillis();
System.out.println("mergeSort: " + (endTime - startTime) / 1000.0 + "s");
System.out.println("arr is sorted: " + isSorted(arr));
System.out.println("temp is sorted: " + isSorted(temp));
startTime = System.currentTimeMillis();
temp = myMergeSort.mergeSort1(temp);
endTime = System.currentTimeMillis();
System.out.println("mergeSort1: " + (endTime - startTime) / 1000.0 + "s");
System.out.println("temp is sorted: " + isSorted(temp));
}
}
测试结果：
N = 1000000
mergeSort: 0.251s
arr is sorted: true
temp is sorted: false
mergeSort1: 0.273s
temp is sorted: true
归并排序的扩展
1.小和问题
在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和，
求一个数组的小和。
例：[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。
相等的时候，先拷贝右组的数，这是唯一和经典归并排序不同的地方， 为什么要先拷贝右组的数？
就是为了让左组的每一个数方便知道，右边到底右多少个数比他大，归并排序优秀的地方，通过比较变成了有序的部分，左组的每一个数，去求解当前的右组有多少个数比左组当前这个数大的时候，就获得了方便。 归并排序为什么可以加速求解小和的过程？
正是因为归并排序可以把比较行为变成有序的部分，所以每一个左组的数在和每一个更大的右组的数合并的时候，可以通过下标计算的方式，很快速的算出，此时它面临的这个右组，这个范围的右组，有多少个数比我大，然后这个数和当前的右组，就合成了统一的一个大组，继续和下一个右组比较进行分批统计，周而复始。
代码实现：
public class Solution {
//相等的时候，先拷贝右组的数，这是唯一和经典归并排序不同的地方，
//为什么要先拷贝右组的数？
//就是为了让左组的每一个数方便知道，右边到底右多少个数比他大
//归并排序优秀的地方，通过比较变成了有序的部分
//左组的每一个数，去求解当前的右组有多少个数比左组当前这个数大的时候，就获得了方便
//归并排序为什么可以加速求解小和的过程？
//正是因为归并排序可以把比较行为变成有序的部分，
//所以每一个左组的数在和每一个更大的右组的数合并的时候，
//可以通过下标计算的方式，很快速的算出，此时它面临的这个右组，
//这个范围的右组，有多少个数比我大，
//然后这个数和当前的右组，就合成了统一的一个大组，继续和下一个右组比较进行分批统计，周而复始。
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 l, int r){
if(l >= r)
return 0;
int mid = l + ((r - l) >> 1);
return process(arr,l,mid) +
process(arr,mid + 1, r) +
merge(arr,l,mid,r);
}
private static int merge(int[] arr, int l, int mid, int r){
int[] temp = new int[r - l + 1];
int i = l;
int j = mid + 1;
int k = 0;
int sum = 0;
while(i <= mid && j <= r){
if(arr[i] < arr[j]){
sum += (arr[i] * (r - j + 1));
temp[k++] = arr[i++];
}else {
temp[k++] = arr[j++];
}
}
while(i <= mid){
temp[k++] = arr[i++];
}
while(j <= r){
temp[k++] = arr[j++];
}
for (int m = 0 ; m < temp.length; m ++ ){
arr[l + m] = temp[m];
}
return sum;
}
private static int[] getRandomArray(int n, int rangeL, int rangeR){
if(rangeL > rangeR){
return new int[0];
}
int[] result = new int[n];
for (int i = 0 ; i < n ; i ++ ) {
result[i] = (int)(Math.random() * (rangeR - rangeL + 1) + rangeL);
}
return result;
}
private static int logarithmicDetector(int[] arr){
int result = 0;
for (int i = 0 ; i < arr.length ; i ++ ){
for (int j = i + 1; j < arr.length ; j ++ ){
if(arr[j] > arr[i])
result += arr[i];
}
}
return result;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] num = new int[]{1,3,4,2,5};
//int[] num = new int[]{1,3,4,2,5,4,5,6,7,4,1,2,3,4,5,6,7,8};
System.out.println(solution.logarithmicDetector(num));
System.out.println(solution.smallSum(num));
int n = 10000;
int rangeL = 0;
int rangeR = 100;
for (int i = 0 ; i < 10 ; i ++ ){
int[] arr = getRandomArray(n,rangeL,rangeR);
int num1 = logarithmicDetector(arr);
System.out.println(num1);
int num2 = smallSum(arr);
System.out.println(num2);
System.out.println(num1 == num2);
}
}
}
测试结果：
16
16
808033293
808033293
true
818814835
818814835
true
827167065
827167065
true
824091447
824091447
true
801285841
801285841
true
808444796
808444796
true
808242863
808242863
true
817181237
817181237
true
805007216
805007216
true
817418809
817418809
true
2.逆序对问题
在一个数组中，左边的数如果比右边的大，则两个数构成一个逆序对，请返回逆序对的数量。
代码实现：
public class Solution {
public static int reversePairs(int[] arr){
if(arr == null || arr.length < 2)
return 0;
return process(arr,0,arr.length - 1);
}
private static int process(int[] arr, int l, int r){
if(l >= r)
return 0;
int mid = l + ((r - l) >> 1);
return process(arr, l, mid) +
process(arr, mid + 1, r) +
merge(arr,l , mid , r);
}
//降序
private static int merge(int[] arr, int l, int mid, int r){
int[] temp = new int[r - l + 1];
int i = l;
int j = mid + 1;
int k = 0;
int count = 0;
while (i <= mid && j <= r){
if(arr[i] <= arr[j]){
temp[k++] = arr[j++];
}else {
count += (r - j + 1);
temp[k++] = arr[i++];
}
}
while(i <= mid){
temp[k++] = arr[i++];
}
while(j <= r){
temp[k++] = arr[j++];
}
for (int m = 0 ; m < temp.length ; m ++ ){
arr[l + m] = temp[m];
}
return count;
}
private static int[] getRandomArray(int n, int rangeL, int rangeR){
if(rangeL > rangeR){
return new int[0];
}
int[] result = new int[n];
for (int i = 0 ; i < n ; i ++ ) {
result[i] = (int)(Math.random() * (rangeR - rangeL + 1) + rangeL);
}
return result;
}
private static int logarithmicDetector(int[] arr){
int result = 0;
for (int i = 0 ; i < arr.length ; i ++ ){
for (int j = i + 1; j < arr.length ; j ++ ){
if(arr[j] < arr[i])
result ++;
}
}
return result;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] num = new int[]{7,5,6,4};
System.out.println(solution.reversePairs(num));
int n = 10000;
int rangeL = 0;
int rangeR = 100;
for (int i = 0 ; i < 10 ; i ++ ){
int[] arr = getRandomArray(n,rangeL,rangeR);
int num1 = logarithmicDetector(arr);
System.out.println(num1);
int num2 = reversePairs(arr);
System.out.println(num2);
System.out.println(num1 == num2);
}
}
}
测试结果：
N = 10000
5
24707588
24707588
true
24781602
24781602
true
24832799
24832799
true
25092348
25092348
true
24940354
24940354
true
24945276
24945276
true
24641166
24641166
true
24527443
24527443
true
24781029
24781029
true
24685034
24685034
true
评论 null 条