思路
数组排序主要分为两个部分:划分数组和归并排序。
划分数组:
-
将待排序的无序数组分为左右两个部分,如果无序数组的起始元素下标为first,最后一个元素的下标为last,那么左右两部分之间的临界点下标mid=(first+last)/2,这两部分分别是arr[first … mid]和arr[mid+1 … last];
-
将上面得到的两部分数组继续按照步骤(1)进行划分,直到划分的数组长度为1。
归并排序:
-
申请空间,空间大小为两个已经排序数组之和,该空间用来存放合并后的数组;
-
设定两个指针,最初位置分别为两个已经排序数组的起始位置;
-
比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;
-
重复步骤(3)直到某一指针超出数组尾,将另一数组剩下的所有元素直接复制到合并数组尾。
代码
public void mergeSort(int[] arr, int first, int last) {
int mid;
if (first < last) {
mid = (first + last) / 2;
mergeSort(arr, first, mid);
mergeSort(arr, mid + 1, last);
merge(arr, first, mid, last);
}
}
private void merge(int[] arr, int first, int mid, int last) {
int i, j;
int[] temp = new int[arr.length];
int left_first = first;
int right_first = mid + 1;
for (i = 0; left_first <= mid && right_first <= last; i++) {
if (arr[left_first] <= arr[right_first]) {
temp[i] = arr[left_first++];
} else {
temp[i] = arr[right_first++];
}
}
if (left_first <= mid) {
for (j = left_first; j <= mid; j++) {
temp[i++] = arr[j];
}
}
if (right_first <= last) {
for (j = right_first; j <= last; j++) {
temp[i++] = arr[j];
}
}
for (j = 0; j < last - first + 1; j++) {
arr[first + j] = temp[j];
}
}
标签:归并,Java,arr,int,mid,数组,last,排序,first
From: https://www.cnblogs.com/liu-im/p/17676401.html