- 三、归并排序及其应用
- 1、归并排序递归实现
- 2、求小和
- 2.1 两层for循环，O(n2)时间复杂度
- 2.2 通过归并求小和O(N*log2N)
- 3、逆序对
- 4、将逆序对的定义改为i和j为下标，若i < j 时，arr[i] > 2 *arr[j] 就称这是一个逆序对，寻找所有逆序对
- 假设桌子上有两沓顺序排好的手牌，每次取两边较小的一个，这样最后的手牌总体就是有序的。归并排序就是这样的思想，假设数组分为左右两部分别有序，新建立一个数组，每次取较小的数放入新数组中，这样最终的数组就是有序的。
package merge;
public class MergeSort {
public static void sort(int[] arr){
if(arr == null || arr.length == 0){
return;
}
mergeSort(arr,0,arr.length - 1);
}
private 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,R,mid + 1);
}
private static void merge(int[] arr,int L,int R,int mid){
int[] newArr = new int[R - L + 1];
int leftBegin = L;
int rightBegin = mid;
int k = 0;
//哪边小就放入新数组，这里 arr[leftBegin] <= arr[rightBegin] 可以让排序稳定
while (leftBegin < mid && rightBegin <= R){
newArr[k++] = arr[leftBegin] <= arr[rightBegin] ? arr[leftBegin++] : arr[rightBegin++];
}
//如果右边放完而左边没有放完则把左边剩余的放进新数组
while (leftBegin < mid){
newArr[k++] = arr[leftBegin++];
}
//如果左边放完而右边没有放完则把右边边剩余的放进新数组
while ((rightBegin <= R)){
newArr[k++] = arr[rightBegin++];
}
//将合并好的数组拷贝回原数组
for(int i = 0;i < newArr.length;i++){
arr[L + i] = newArr[i];
}
}
}
2、求小和
- 给定一个整型数组，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和
- 例子 arr = [2,4,1,6]
- 对于2，左边比他小的没有
- 对于4，左边2比他小
- 对于3，左边没有比他小的
- 对于6，左边2、4、1都比它小
- 所有返回 2 + 2 + 4 + 1 = 9
- 很显然两层for循环可以搞定这个问题。外循环依次遍历数组，内循环从数组起始位置到当前位置，所有比它小的加起来就行。
public static int smallSumFor(int[] arr){
if(arr == null || arr.length == 0){
return 0;
}
int sum = 0;
for(int i = 1;i < arr.length;i++){
for(int j = 0;j <= i;j++){
if(arr[j] < arr[i]){
sum += arr[j];
}
}
}
return sum;
}
2.2 通过归并求小和O(N*log2N)
- 每次在归并的过程中，只要左边当前位置的元素的比右边前位置的元素小，那么左边的这个数就会对右边部分 当前位置向右的所有数产生小和，那么记录右边数组到右边当前的位置之差乘上左边部分当前的值，就是在这次归并中左边该数产生的小和。因为每次都是局部归并，小和每次归并只对右边部分产生，但是归并会两两合并，小归并到大归并，那么在往顶部的归并中产生的所有小和都会被统计起来。因为每次只比较左右两部分，所有在前一次归并中右边部分的小和不会再被记录，直接看图可能比较好理解。
public static int smallSumMergeSort(int[] arr){
if(arr == null || arr.length == 0){
return 0;
}
return mergeSort(arr,0,arr.length - 1);
}
public static int mergeSort(int[] arr, int L, int R){
if(L == R){
return 0;
}
int mid = L + ( (R - L) >> 1);
return mergeSort(arr,L,mid) +
mergeSort(arr,mid + 1,R) +
merge(arr,L,mid + 1,R);
}
public static int merge(int[] arr,int L,int mid,int R){
int[] newArr = new int[R - L + 1];
int leftBegin = L;
int rightBegin = mid;
int k = 0;
int result = 0;
while (leftBegin < mid && rightBegin <= R){
//当左右相等时先放右边，因为左边的当前位置还会对右边的下一位置产生小和
result += arr[leftBegin] < arr[rightBegin] ? (R - rightBegin + 1) * arr[leftBegin] : 0;
newArr[k++] = arr[leftBegin] < arr[rightBegin] ? arr[leftBegin++] : arr[rightBegin++];
}
while (leftBegin < mid){
newArr[k++] = arr[leftBegin++];
}
while ((rightBegin <= R)){
newArr[k++] = arr[rightBegin++];
}
//将合并好的数组拷贝回原数组
for(int i = 0;i < newArr.length;i++){
arr[L + i] = newArr[i];
}
return result;
}
3、逆序对
- 对于数组中的元素，i和j为下标，若i < j 时，arr[i] > arr[j] 就称这是一个逆序对。
- 给定一个数组，返回数组中多少个逆序对
- 两层for循环，不在赘述。
- 同上题一样，可以用归并排序。在归并排序中每次统计逆序对，最后结果加起来就是结果
- 如果左边的当前位置和右边当前位置为逆序对，那么左边当前位置往后的所有位置都与右边当前位置是逆序对，因为数组两部分都是有序的。
- 这里不在详细解释，思路都差不多，只不过统计方式需要改变，这种局部到全局的统计思路都大体相同。
package merge;
public class Reverse {
public static int reverse(int[] arr){
if(arr == null || arr.length == 0){
return 0;
}
return mergeSort(arr,0,arr.length - 1);
}
public static int mergeSort(int[] arr,int L,int R){
if(L == R){
return 0;
}
int mid = L + ( (R - L) >> 1);
return mergeSort(arr,L,mid) +
mergeSort(arr,mid + 1,R) +
merge(arr,L,mid + 1,R);
}
private static int merge(int[] arr,int L,int mid,int R){
int[] newArr = new int[R - L + 1];
int leftBegin = L;
int rightBegin = mid;
int k = 0;
int result = 0;
while (leftBegin < mid && rightBegin <= R){
//当左右相等时先放左边，因为右边的当前位置还会对左边的下一位置产生逆序对
result += arr[leftBegin] > arr[rightBegin] ? (mid - leftBegin) : 0;
newArr[k++] = arr[leftBegin] <= arr[rightBegin] ? arr[leftBegin++] : arr[rightBegin++];
}
while (leftBegin < mid){
newArr[k++] = arr[leftBegin++];
}
while ((rightBegin <= R)){
newArr[k++] = arr[rightBegin++];
}
//将合并好的数组拷贝回原数组
for(int i = 0;i < newArr.length;i++){
arr[L + i] = newArr[i];
}
return result;
}
}
4、将逆序对的定义改为i和j为下标，若i < j 时，arr[i] > 2 *arr[j] 就称这是一个逆序对，寻找所有逆序对
- 原理同上一个题目差不多，只需要修改判断条件
- 但是这里的结果统计和归并不可以一起进行，因为这种判断和归并条件不同，所以可以先统计结果再进行归并
- 因此可以扩展，对于不同的要求，都可以先统计结果再进行归并
package merge;
public class BigThanRightTwice {
public static int bigThanRightTwice(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
return mergeSort(arr, 0, arr.length - 1);
}
public static int mergeSort(int[] arr, int L, int R) {
if (L == R) {
return 0;
}
int mid = L + ((R - L) >> 1);
return mergeSort(arr, L, mid) +
mergeSort(arr, mid + 1, R) +
merge(arr, L, mid + 1, R);
}
private static int merge(int[] arr, int L, int mid, int R) {
int[] newArr = new int[R - L + 1];
int leftBegin = L;
int rightBegin = mid;
int k = 0;
int result = 0;
//只统计结果不进行归并
while (leftBegin < mid && rightBegin <= R) {
if(arr[leftBegin] > 2 * arr[rightBegin]){
result += mid - leftBegin;
rightBegin++;
}else {
leftBegin++;
}
}
leftBegin = L;
rightBegin = mid;
while (leftBegin < mid && rightBegin <= R) {
newArr[k++] = arr[leftBegin] <= arr[rightBegin] ? arr[leftBegin++] : arr[rightBegin++];
}
while (leftBegin < mid) {
newArr[k++] = arr[leftBegin++];
}
while ((rightBegin <= R)) {
newArr[k++] = arr[rightBegin++];
}
//将合并好的数组拷贝回原数组
for (int i = 0; i < newArr.length; i++) {
arr[L + i] = newArr[i];
}
return result;
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）