您的位置 首页 java

java模拟归并排序merge sort

/**

* 模拟归并排序merge sort

* 思路是将一个数组分成两半 每一半再继续分半 递归的拆分直至每个范围内只有一个元素 从最小的单元开始排序、返回上一层变为更大的单元排序再返回上一层变成更大的单元 最后完成整个数组的排序

*/

public class TestMergeSort {

public static void sort (int[] arr){

//先重载一个给整个数组排序的方法 不用手动输入low=0 high=length-1 方便使用更易懂

sort(arr, 0, arr.length-1);

//最高位是length-1

}

public static void sort(int[] arr,int low,int high){

if (low<high){

//当low=high即范围内只有一个数的时候不执行直接结束迭代 两个数及以上才需要排序

int mid = (high+low)/2;

sort(arr,low,mid);

sort(arr,mid+1,high);

//将当前范围分割成左右两部分 分别进行排序 这里会一层一层迭代 直到子范围内只有一个数的时候结束迭代 然后返回上一层依次进行后续运算

//最下层两个子范围都是一个数 结束迭代 回到上一层往下执行运算 将两个子范围排序 执行完就得到了范围=2的有序集合

// 执行完结束 返回上一层 用范围=2的有序集合和另外一个有序集合排序 执行完再返回上一层 层层执行、返回 直到最高层

//最高层是数组的整个左半边和整个右半边 两个半边内部都是排好序的 再将这两部分执行下面的运算

int[] b = new int[high-low+1];

//new一个数组 长度和现在要排序的范围的长度一致

int i = 0;

int left = low;

//左半边范围的首位 用于左边的索引

int right = mid+1;

//右半边范围的首位 用于右边的索引

while (left<mid+1&&right<high+1){

b[i++] = (arr[left]<arr[right])?arr[left++]:arr[right++];

//因为左半边范围和右半边范围都是从小到大排序好的 所以每次都比较两个范围内最左侧的那个元素 哪个小就放入b[i]中并将这边的索引+1

//等号左侧也可以++ 条件运算符内也可以++

//当左边或者右边取完了即left<mid+1&&right<high+1 为false时结束循环 因为每次循环只会取左边或者右边一位数 所以不可能两侧同时取完 还没取出的部分要继续取

}

while (left<mid+1){

//如果右边取完了 左边没取完 这时b[]中所有存在的元素都比没取完的小 没取完的又是有序的 所以遍历剩余的依次存到b中

b[i++] = arr[left++];

}

while (right<high+1){

//如果左边取完了 右边没取完

b[i++] = arr[right++];

}

//到这时左右两边都取完了 b也填满了

for (i = 0;i<b.length;i++){

arr[low++] = b[i];

//将b遍历 存回arr的范围中 即完成对当前范围的排序

}

}

}

public static void main(String[] args) {

int[] a = {7,82,4,6,35,1,19,32,2};

sort(a);

System.out.println(Arrays.toString(a));

//结果[1, 2, 4, 6, 7, 19, 32, 35, 82]

/*

第一步 7,82,4,6,35 1,19,32,2

第二步 7,82,4 6,35 1,19,32,2

第三步 7,82 4 6,35 1,19,32,2

第四步 7 82 4 6,35 1,19,32,2

第五步 7,82 4 6,35 1,19,32,2

第六步 4,7,82 6,35 1,19,32,2

第七步 4,7,82 6 35 1,19,32,2

第八步 4,7,82 6,35 1,19,32,2

第九步 4,6,7,35,82 1,19,32,2

第十步 4,6,7,35,82 1,19 32,2

十一步 4,6,7,35,82 1 19 32,2

十二步 4,6,7,35,82 1,19 32,2

十三步 4,6,7,35,82 1,19 32 2

十四步 4,6,7,35,82 1,19 2,32

十五步 4,6,7,35,82 1,2,19,32

十六步 1,2,4,6,7,19,32,35,82

*/

}

}

文章来源:智云一二三科技

文章标题:java模拟归并排序merge sort

文章地址:https://www.zhihuclub.com/188262.shtml

关于作者: 智云科技

热门文章

网站地图