从零开始SpringCloud Alibaba实战(78)——归并排序
前言思想1(正着想):将一个大的无序数组有序,我们可以把大的数组等分成两个,然后对这两个数组分别进行排序,之后在把这两个数组合并成一个有序的数组。思想2(反着想):待排序的n个元素,可以看作n个待合并的有序序列,每个序列只有一个元素。每次将两个相邻的序列合并为一个大的有序序列,重复合并过程直到剩下一个序列。两种其实核心思想是一样的只是理解不同。代码package Sort;/*** @Descri
·
前言
思想1(正着想):将一个大的无序数组有序,我们可以把大的数组等分成两个,然后对这两个数组分别进行排序,之后在把这两个数组合并成一个有序的数组。
思想2(反着想):待排序的n个元素,可以看作n个待合并的有序序列,每个序列只有一个元素。每次将两个相邻的序列合并为一个大的有序序列,重复合并过程直到剩下一个序列。两种其实核心思想是一样的只是理解不同。
代码
package Sort;
public class MergeSort {
public static void mergeSort(int[] arr){
if(arr == null || arr.length < 2){
return;
}
process(arr,0, arr.length-1);
}
public static void process(int[] arr, int L,int R){
if(L == R){
return;
}
int mid = L + ((R-L) >> 1);
process(arr, L, mid);
process(arr, mid + 1, R);
merge(arr, L, mid, R);
}
public static void merge(int[] arr, int L, int M, int R){
int[] help = new int[R-L+1];
int i = 0;
int p1 = L;
int p2 = M + 1;
while (p1 <= M && p2 <= R){
help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= M){
help[i++] = arr[p1++];
}
while (p2 <= R){
help[i++] = arr[p2++];
}
for(i = 0; i < help.length; i++){
arr[L+i] = help[i];
}
}
public static void main(String[] args) {
int[] arr = new int[]{9,8,7,6,5,4,3,2,1};
mergeSort(arr);
for(int i:arr){
System.out.println(i);
}
}
}
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
已为社区贡献3条内容
所有评论(0)