1.归并排序
先回顾一下归并排序
归并排序中归和并的意义:
归:递归。递归的将输入数组进行分割至长度为1.
并:合并。将各长度为1的数组顺序合并,完成归并排序。
归并排序的整体思想为分治,主体算法为:
public void mergeSort(int[]arr, intbegin, intend) {if (begin != end) {int mid = (begin + end) /2;mergeSort(arr,begin, mid);mergeSort(arr,mid + 1, end);mergeArr(arr,begin, mid, end);}}
对{3,1,0,4}执行归并排序的示意图:
数组{3,1,0,4}先递归的被划分为{3},{1},{0},{4},之后被合并为{1,3},{0,4},最后合并为{0,1,3,4}
2.利用归并排序求逆序对
逆序对数的求解发生在mergeArr过程中:
I.{3}与{1}合并时,3>1,为逆序对。{0}与{4}合并时,0<1,不是逆序对
II.{1,3}与{0,4}合并时:
1.先看{1,3}中的{1}和{0,4}中的{0}。由于0<1,因此0应放入merge后的第一个位置。此时{1,3}与{0}的逆序对数为2.将0放入第一个位置
2.将{1,3}中的1与{0,4}中的4比较,1<4,不存在逆序对。将1放入第二个位置。
3.将{1,3}中的3与{0,4}中的4比较,,3<4,不存在逆序对。将1放入第三个位置。
4.将4放入第四个位置,完成mergeArr。
逆序对计算在
while (i <= m && j <= n) {if (arr[i] < arr[j])temp[k++] = arr[i++];else {iResult += j – k;temp[k++] = arr[j++];}}
中执行
Code:
public class SSS {static int[] temp;static int iResult = 0;public static void mergeArr(int[] arr, int begin, int mid, int end,int[] temp) {int i = begin, j = mid + 1;int m = mid, n = end;int k = 0;while (i <= m && j <= n) {if (arr[i] < arr[j])temp[k++] = arr[i++];else {iResult += j – k;temp[k++] = arr[j++];}}while (i <= m)temp[k++] = arr[i++];while (j <= n)temp[k++] = arr[j++];for (i = 0; i < k; ++i)arr[begin + i] = temp[i];}public static void mergeSort(int[] arr, int begin, int end, int[] temp) {if (begin != end) {int mid = (begin + end) / 2;mergeSort(arr, begin, mid, temp);mergeSort(arr, mid + 1, end, temp);mergeArr(arr, begin, mid, end, temp);}}public static void main(String[] args) {// TODO Auto-generated method stubint[] arr = { 3, 1, 0, 4 };temp = new int[arr.length];mergeSort(arr, 0, arr.length – 1, temp);for (int i : arr)System.out.println(i);System.out.println("Result:" + iResult);}}
版权声明:本文为博主原创文章,未经博主允许不得转载。
人生的大部份时间里,承诺同义词是束缚,奈何我们向往束缚。