代码如下:
private void merge(int[] array, int left, int mid, int right) {
int i = left;
int j = mid;
int length = right - left;
int[] extra = new int[length];
int k = 0;
while(i < mid && j < right) {
if(array[i] <= array[j]) {
extra[k++] = array[i++];
} else {
extra[k++] = array[j++];
}
}
while (i < mid) {
extra[k++] = array[i++];
}
while (j < right) {
extra[k++] = array[j++];
}
// 从 extra 搬移回 array
for (int t = 0; t < length; t++) {
// 需要搬移回原位置,从 low 开始
array[left + t] = extra[t];
}
}
递归实现操作:
public void mergeSort(int[] array) {
mergeSortInternal(array, 0, array.length);
}
private void mergeSortInternal(int[] array, int left, int right) {
if(left >= right - 1)
return;
int mid = (left + right) >>> 1;
mergeSortInternal(array, left, mid);
mergeSortInternal(array, mid, right);
merge(array, left, mid, right);
}
public void mergeSort(int[] array) {
for (int i = 1; i < array.length; i = i * 2) {
for (int j = 0; j < array.length; j = j + 2 * i) {
int low = j;
int mid = j + i;
if (mid >= array.length) {
continue;
}
int high = mid + i;
if (high > array.length) {
high = array.length;
}
merge(array, low, mid, high);
}
}
}
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。