学校如何重视校园网站建设,网站框架地图,如何做企业网站小程序,网站开发用php还是.net好一:简单介绍
归并排序排序就是利用归并的思想实现的排序方法 它的原理是将初始化序列划分成n个记录,则可以看成是n个有序的子序列,每个子序列的长度为1,然后两两归并#xff0c;得到(n/2)个长度为1或者2的有序子序列;然后再两两合并…不断重复 直到最后 得到一个长度为n的有序…一:简单介绍
归并排序排序就是利用归并的思想实现的排序方法 它的原理是将初始化序列划分成n个记录,则可以看成是n个有序的子序列,每个子序列的长度为1,然后两两归并得到(n/2)个长度为1或者2的有序子序列;然后再两两合并…不断重复 直到最后 得到一个长度为n的有序序列为止。
关键词: 将初始化序列划分成n个记录 每次合并的都是有序序列
二:图示 详解最后一步的合并:
三:上码 public class mergeSort1 {public static void main(String[] args) {int arr[] {5,4,3,2,1};int temp[] new int[5];mergeSort2(arr,temp,0,4);for (int i : arr) {System.out.println(i);}}/*** param arr :待排序列* param arrTemp:这个是临时数组,可以存放每次合并完的数据,再这个合并完后再复制到我们的arr里面* param left:每次分解的序列的最左边* param right:每次分解的序列的最右边*/public static void mergeSort2 (int arr[],int arrTemp[],int left,int right) {//如果只剩下一个元素的话,那么就不需要继续划分,只有一个元素的话,那么本身就是有序的直接归并// [left,right]表示的是一个范围if (left right) {int mid (left right) / 2;//递归分解左半部分mergeSort2(arr,arrTemp,left,mid);// 比如 0 1 2进行划分 那么 mid 1,那么左半部分[0,1] 右半部分[2,2]//递归分解右半部分mergeSort2(arr,arrTemp,mid1,right);//合并merge(arr,arrTemp,left,mid,right);}}//合并private static void merge(int arr[], int[] arrTemp, int left, int mid,int right) {//标记左半部分第一个元素的下标int l_pos left;//标记右半部分第一个元素的下标int r_pos mid 1;//临时数组的下标int pos left;//合并while (l_pos mid r_pos right) {if (arr[l_pos] arr[r_pos]) { //左边第一个元素元素最小arrTemp[pos] arr[l_pos];} else { //右边第一个元素最小arrTemp[pos] arr[r_pos];}}//合并左半部分剩余的元素,(举例一种情况就是 比如右半部分都比左半部分小 那么最终就剩下左半部分了)while (l_pos mid) {arrTemp[pos] arr[l_pos];}//合并右半部分剩余的部分while (r_pos right) {arrTemp[pos] arr[r_pos];}//将临时数组的值复制到arr中while (left right) {//这里的left还是最初的left 上方操作的只是临时变量arr[left] arrTemp[left];left;}}}
