基本思想:归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表。即,把待排序序列分为若干个子序列,每个子序列是有序的,然后再把有序子序列合并为整体有序序列。
private void mergeSort(int[] pArr, int pLeft, int pRight) {
if (pArr.length < 2) {
return;
}
if (pLeft < pRight) {
int mid = pLeft + (pRight - pRight) / 2;
mergeSort(pArr, pLeft, mid);
mergeSort(pArr, mid + 1, pRight);
merge(pArr, pLeft, mid, pRight);
}
}
private void merge(int[] pArr, int pLeft, int pMid, int pRight) {
int[] temp = new int[pRight - pLeft + 1];
// 左边数组起始指针
int i = pLeft;
// 右边数组起始指针
int j = pMid + 1;
// 临时数组起始指针
int k = 0;
// 先把较小的数放到数组中
while (i <= pMid && j <= pRight) {
if (pArr[i] < pArr[j]) {
temp[k++] = pArr[i++];
} else {
temp[k++] = pArr[j++];
}
}
// 把左边剩余的数放到数组中
while (i <= pMid) {
temp[k++] = pArr[i++];
}
// 把右边剩余的数放到数组中
while (j <= pRight) {
temp[k++] = pArr[j++];
}
// 把原始数组中相应位置的数据覆盖掉
for (int l = 0; l < temp.length; l++) {
pArr[pLeft + l] = temp[l];
}
}
网友评论