JAVA_算法_归并排序
思想：
把一个大的数组细分成两个不同的数组， 循环这个过程。直到数组中的元素只有1或0个元素。
当数组中的只有两个元素时，比较两个元素的大小，前一个大于后一个就交换。
然后把细分成两个或一个元素的数组合并，合并的方法是从两个数组中每次取最前面的元素比较，每次都取一个小的放在新数组的前面，新数组的自变量++。这里要定义3个临时变量用于数组的交换。
重复上述方法直到合并所有元素。
————————————我是分割线——————————————
以下是代码：
<span style="white-space:pre"> </span>public static void merge(int []arr,int left,int center,int right){int []ar=new int [arr.length];int mid=center+1;//why add one?数组中的mid就是在center的位置int third=left;int tmp=left;while(left<=center&&mid<=right){if(arr[left]<=arr[mid])ar[tmp++]=arr[left++];//k会不会越界？elsear[tmp++]=arr[mid++];}while(mid<=right){ar[tmp++]=arr[mid++];}while(left<=center){//ar[tmp++]=arr[left++];}while(third<=right){arr[third]=ar[third++];}}public static void binarysort(int []arr,int left,int right){if(left>=right)return ;int center=(left+right)/2;binarysort(arr,left,center);binarysort(arr,center+1,right);merge(arr,left,center,right);print(arr);}public static void print(int[] data) {for (int i = 0; i < data.length; i++) {System.out.print(data[i] + "\t");}System.out.println();}
以上是用到的三个方法
在merge中分别用left,tmp,third三个变量来定义数组中的位置。游标是数组中方法的第二个参数的值加一作为下标时的值。
如果左边的值不大于（小于等于）游标的值，新数组存储这个值。否则存储游标的值。
对比作为left和mid下标时的数组中的值的大小，谁小就存储谁。
当不满足条件时就是left>center或者mid>right时，当left>center时，表示左边的数组已经取完了。当mid>center时，表示右边的值都取完了。
无论是哪种情况，都会有另外一边的数组还没有完全取完。
于是我们用了两个while循环来把剩余的值给取完。
在第三个while循环中，我们的third终于排上了用场。用来对数组的重新复制，即把原数组中的值排序后给了新数组，排好序后新数组中的值再重新给原来的数组。
在binarysort方法中，第一个条件时为了结束循环。
两个递归函数是为了让left和center和right的值能得到确认，当left<right时就会返回空。那就会在调用这个函数的函数里面继续向下运行。第一个循环结束后
第一次对最左边的排序，接着对第二个数组排序，合并后。对第三个数组排序，对第四个数组排序后（不排）合并。这时候只有两个数组了。
再对这两个数组进行一次排序，然后排好了。
这样的排序方式简直是完美的排序。充满了排序时的美感。
平均运行次数是nlogn次。
对于底数10为例，log（10）k，k=100（n次方）n=1,2,3,4’’’’’’∞时，值却是+1+1+1+1+1’’’’’’’’’
因此这种排序方式充满了让人心里感到满足的美感。
在主函数中调用：binarysort(array,0,array.length-1); 就能进行一次完整的排序
以上是排序的过程。
待我称王封你为后i
系统管理员
小鱼儿
迷南。
╰+哭是因爲堅強的太久メ
还没有评论，来说两句吧...