转载

数据结构（3）归并排序

归并排序

归并排序原理

归并排序（Merging Sort）就是利用归并的思想实现的排序方法。它的原理是假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]个长度为2或1的有序子序列，再两两归并，直至得到一个长度为n的有序序列为止，这种排序方法成为2路归并排序。

先看代码

package Sort;  class MergeSort {   public static void main(String[] args) {      int[] list = {80,40,50,30,60,70,10,90,20};;   MergeSort ms = new MergeSort();    ms.MSort(list);   System.out.println("");   System.out.println("最终结果：");   ms.printArrry(list);  }     private void printArrry(int[] a){   for(int k = 0; k <= a.length-1; k++){    System.out.print(a[k]);   }  }  private void MSort(int[] list) {   mergeSort(list, 0, list.length-1);  }    private void mergeSort(int [] list,int a, int b){    int mid;   if (a == b){    //System.out.println("执行到最底层：");    //printArrry(list);    return;    }   else {    mid = (a+b)/2;    mergeSort(list, a, mid);    mergeSort(list, mid+1, b);    Merge(list, a, mid, b);    System.out.println("/n"+"left:"+a+" mid:"+mid+" right:"+b);    System.out.println("此时数组为：");    printArrry(list);   }  }    private void Merge(int [] list, int left, int mid, int right){   int a,b,c,d;   a = left;   b = mid+1;   c = left;   d = left;   int[] tempaddr = new int[list.length];   while (a<=mid && b<=right) {    if (list[a] <= list[b]) {     tempaddr[c++] = list[a++];    }    else {     tempaddr[c++] = list[b++];    }   }   while (a<=mid) {    tempaddr[c++] = list[a++];   }   while (b<=right) {    tempaddr[c++] = list[b++];   }   while (d <= right){    list[d] = tempaddr[d++];   }  } }

mergeSort()分析

private void mergeSort(int [] list,int a, int b){   int mid;   /*当拆分至最小单元时，则跳出*/   if (a == b){    return;    }   else {    mid = (a+b)/2;    /*将上一次拆分后的数组list的前半部分再进行拆分*/    mergeSort(list, a, mid);    /*将上一次拆分后数组list的后半部分再进行拆分*/    mergeSort(list, mid+1, b);    /*将拆分至list最小单元的前半部分和后半部分进行归并*/    Merge(list, a, mid, b);    System.out.println("/n"+"left:"+a+" mid:"+mid+" right:"+b);    System.out.println("此时数组为：");    printArrry(list);   }  }

Merge()分析

private void Merge(int [] list, int left, int mid, int right){   int a,b,c,d;   a = left;   b = mid+1;   c = left;   d = left;   int[] tempaddr = new int[list.length];   /*将两个有序的数组，从头开始比较，较小值存入tempaddr[]*/   while (a<=mid && b<=right) {    if (list[a] <= list[b]) {     tempaddr[c++] = list[a++];    }    else {     tempaddr[c++] = list[b++];    }   }   /*将前半部分还有剩余的数组取出，存入tempaddr[]*/   while (a<=mid) {    tempaddr[c++] = list[a++];   }   /*将后半部分还有剩余的数组取出，存入tempaddr[]*/   while (b<=right) {    tempaddr[c++] = list[b++];   }   /*将已经归并好的数组，传给list，使得list原有的对应于list[left..right]的部分有序*/   while (d <= right){    list[d] = tempaddr[d++];   }  }

输出结果

left:0 mid:0 right:1 此时数组为： 408050306070109020 left:0 mid:1 right:2 此时数组为： 405080306070109020 left:3 mid:3 right:4 此时数组为： 405080306070109020 left:0 mid:2 right:4 此时数组为： 304050608070109020 left:5 mid:5 right:6 此时数组为： 304050608010709020 left:7 mid:7 right:8 此时数组为： 304050608010702090 left:5 mid:6 right:8 此时数组为： 304050608010207090 left:0 mid:4 right:8 此时数组为： 102030405060708090 最终结果： 102030405060708090

原理图示

数据结构（3）归并排序红色部分显示的是，此时操作的数组的区间，黑色部分，则是未被操作的区间。

通过这张图可以看出，因为mid=(a+b)/2，mergeSort(list, a, mid)，所以list数组一路向下拆分，从0-8，到0-4，到0-2，到0-1，最后到0-0，此时得到return，返回递归上一层，此时mid为0，mergeSort(list, mid+1, b)，也可以得到return，然后就执行Merge(list, a, mid, b)。这句话就是把此时(a,mid,b)=(0,0,1)进行了归并，使得list[0..1]有顺序。

以此类推，接下来依次是(a,mid,b)=(0,1,2)，(a,mid,b)=(0,2,4)，....，(a,mid,b)=(5,6,8)，(a,mid,b)=(0,4,8)

原文 http://www.cnblogs.com/danbing/p/5147917.html

正文到此结束