归并排序的Java实现
程序员文章站
2024-03-16 12:21:04
...
题目:对于一个int数组,请编写一个归并排序算法,对数组元素排序。给定一个int数组A及数组的大小n,请返回排序后的数组。
算法思路:
- 先用递归方法,默认排序方法为2路归并排序。看下图应该能立即理解:
- 先使每个子序列有序,再将两个已经排序的序列合并成一个序列的操作。若将两个已经排序的有序表合并成一个有序表,称为二路归并。
public class MergeSort {
public int[] mergeSort(int[] A) {
//归并排序,递归做法,分而治之
mSort(A, 0, A.length-1);
return A;
}
public void mSort(int[] A, int low, int high) {
if(low < high) {
int mid = (low+mid)/2;//中点
mSort(A, low, mid);
mSort(A, mid+1, high);
merge(A, low, mid, high);
}
}
public void merge(int[] A, int low, int mid, int high) {
//辅助数组
int[] temp =new int[A.length];
//左子序列的下标
int i = low;
//右子序列的下标
int j = mid+1;
//辅助数组的下标
int tempIndex = low;
while(i <= mid && j <= high) {
if(A[i] < A[j]) {
temp[tempIndex++] = A[i++];
} else {
temp[tempIndex++] = A[j++];
}
}
for(; i <= mid; i++) {
temp[copyIndex++] = A[i];
}
for(; j <= high; j++) {
temp[copyIndex++] = A[j];
}
//复制已排好序的数组至原数组
for(int v = low; v <= high; v++) {
A[v] = temp[v];
}
}
}