常用排序算法之-------------归并排序
程序员文章站
2022-03-24 14:09:22
...
递归实现
package sort;
public class MergeSort {
public static void main(String[] args) {
int[] arr = {2,4,1,5,6,3,9};
mergeSort(arr);
print(arr);
}
/**
* x归并排序的递归方法,先取mid,二分,分到L=R为止,即只剩一个数,
* x然后往上依次合并,借助额外数组,合并时,将两个分别有序部分中较小的数值依次放入额外数组
* x最后额外数组的值拷贝回原数组
* @param arr
* x时间复杂度为O(NlogN),空间复杂度为O(N)
*/
private static void mergeSort(int[] arr) {
// TODO Auto-generated method stub
if(arr == null || arr.length < 2)
return;
sortProcess(arr, 0, arr.length-1);
}
private static void sortProcess(int[] arr, int L, int R) {
// TODO Auto-generated method stub
if(L == R)
return;
int mid = L + ((R - L) >> 1);
sortProcess(arr, L, mid);
sortProcess(arr, mid + 1, R);
merge(arr, L, mid, R);
}
private static void merge(int[] arr, int L, int mid, int R) {
// TODO Auto-generated method stub
int[] help = new int[R - L + 1];
int i = 0;
int p1 = L;
int p2 = mid + 1;
while (p1 <= mid && p2 <= R) {
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while(p1 <= mid)
help[i++] = arr[p1++];
while(p2 <= R)
help[i++] = arr[p2++];
for (int j = 0; j < help.length; j++) {
arr[L + j] = help[j];
}
}
private static void print(int[] arr) {
for (int i : arr) {
System.out.print(i+"\t");
}
}
}
非递归实现
package sort;
public class MergeSort_2 {
public static void main(String[] args) {
int[] arr = {2,4,1,5,6,3,9,1,2,3,5,56,0,23,8};
mergeSort(arr);
print(arr);
}
private static void mergeSort(int[] arr) {
if(arr == null || arr.length < 2)
return;
int span = 1;
int[] temp = new int[arr.length];
while (span < arr.length) {
merge_method(arr, span, arr.length);
span *= 2;
}
}
private static void merge_method(int[] arr, int span, int length) {
// TODO Auto-generated method stub
int index = 0,j;
while(index + 2*span - 1 < length) {
merge(arr, index, index+span-1, index+2*span-1);
index = index + 2*span;
}
//处理剩下的不能构成完整的两组的
if(index + span - 1 < length)
merge(arr, index, index + span - 1, length - 1);
}
private static void merge(int[] arr, int L, int mid, int R) {
// TODO Auto-generated method stub
int[] help = new int[R - L + 1];
int i = 0;
int p1 = L;
int p2 = mid + 1;
while (p1 <= mid && p2 <= R) {
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while(p1 <= mid)
help[i++] = arr[p1++];
while(p2 <= R)
help[i++] = arr[p2++];
for (int j = 0; j < help.length; j++) {
arr[L + j] = help[j];
}
}
private static void print(int[] arr) {
for (int i : arr) {
System.out.print(i+"\t");
}
}
}