歸併的核心思想是歸併。歸併的速度直接影響到演算法的快慢。

1. 簡單插入歸併

public static class MergeSorter1 implements Sorter {
public void sort(int[] values) {
int step = 1;
while (step <= values.length) {
int index = 0;
while (index < values.length) {
int low, high, end = 0;
if (index + step < values.length) {
low = index;
high = index + step;
if (index + step + step < values.length) {
end = index + step + step;
} else {
end = values.length;
}
merge(values, low, high, end);
index = end;
} else {
break;
}
}
step = 2 * step;
}
}

private void merge(int[] values, int low, int high, int end) {
while (high < end) {
while (low < high) {
if (values[low] <= values[high]) {
low++;
} else {
break;
}
}
if (low != high) {
int temp = values[high];
for (int i = low; i <= high; ++i) {
int _temp = values[i];
values[i] = temp;
temp = _temp;
}
}
high++;
}
}
}

簡單插入歸併的性能列印：

.... take time: 654

2. 額外建立一個臨時數組歸併：

public static class MergeSorter2 implements Sorter {
public void sort(int[] values) {
int step = 1;
while (step <= values.length) {
int index = 0;
while (index < values.length) {
merge(values, index, index + step, index + step + step);
index = index + step + step;
}
step = 2 * step;
}
}

private void merge(int[] values, int low, int high, int end) {
if (low >= values.length) {
return;
}
if (high > values.length) {
high = values.length;
}
if (end > values.length) {
end = values.length;
}

int originLow = low;
int originHigh = high;
int originEnd = end;
int tempValues = new int[end - low];
int p = 0;
while (p < tempValues.length) {
if (low < originHigh) {
if (high == originEnd || values[low] <= values[high]) {
tempValues[p] = values[low];
low++;
p++;
}
}
if (high < originEnd) {
if (low == originHigh || values[low] >= values[high]) {
tempValues[p] = values[high];
high++;
p++;
}
}
}

for (int i = 0; i < tempValues.length; ++i) {
values[originLow + i] = tempValues[i];
}
}
}

性能列印：

.... take time: 1520

3. 使用公用臨時數組歸併

public static class MergeSorter3 implements Sorter {
public int tempValues;

public void sort(int[] values) {
boolean isInTemp = false;
int originValues = values;
tempValues = new int[values.length];
int step = 1;
while (step <= values.length) {
int index = 0;
while (index < values.length) {
merge(values, index, index + step, index + step + step);
index = index + step + step;
}
// printValues(tempValues);
int _tempValues = tempValues;
tempValues = values;
values = _tempValues;
isInTemp = !isInTemp;
step = 2 * step;
}
if (isInTemp) {
for (int i = 0; i < values.length; ++i) {
originValues[i] = values[i];
}
}
}

private void merge(int[] values, int low, int high, int end) {
if (low >= values.length) {
return;
}
if (high > values.length) {
high = values.length;
}
if (end > values.length) {
end = values.length;
}
int pLow = low;
int pHigh = high;
int pMerged = low;
while (pMerged < end) {
if (pLow < high) {
if (pHigh >= end) {
tempValues[pMerged] = values[pLow];
pLow++;
pMerged++;
} else if (values[pLow] < values[pHigh]) {
tempValues[pMerged] = values[pLow];
pLow++;
pMerged++;
} else if (values[pLow] == values[pHigh]) {
tempValues[pMerged] = values[pLow];
pLow++;
pMerged++;
tempValues[pMerged] = values[pHigh];
pHigh++;
pMerged++;
}
}
if (pHigh < end) {
if (pLow >= high) {
tempValues[pMerged] = values[pHigh];
pHigh++;
pMerged++;
} else if (values[pLow] > values[pHigh]) {
tempValues[pMerged] = values[pHigh];
pHigh++;
pMerged++;
} else if (values[pLow] == values[pHigh]) {
tempValues[pMerged] = values[pLow];
pLow++;
pMerged++;
tempValues[pMerged] = values[pHigh];
pHigh++;
pMerged++;
}
}
}
}
}

時間列印:

.... take time: 784

4. 在演算法3基礎上進行優化

public static class MergeSorter4 implements Sorter {
public int tempValues;

public void sort(int[] values) {
boolean isInTemp = false;
int originValues = values;
tempValues = new int[values.length];
int step = 1;
while (step <= values.length) {
int index = 0;
while (index < values.length) {
int end = index + step + step;
merge(values, index, index + step, end);
index = end;
}
// printValues(tempValues);
int _tempValues = tempValues;
tempValues = values;
values = _tempValues;
isInTemp = !isInTemp;
step = 2 * step;
}
if (isInTemp) {
for (int i = 0; i < values.length; ++i) {
originValues[i] = values[i];
}
}
}

private void merge(int[] values, int low, int high, int end) {
if (low >= values.length) {
return;
}
if (high > values.length) {
high = values.length;
}
if (end > values.length) {
end = values.length;
}
int pLow = low;
int pHigh = high;
int pMerged = low;
while (pLow < high && pHigh < end) {
if (values[pLow] <= values[pHigh]) {
tempValues[pMerged++] = values[pLow++];
} else {
tempValues[pMerged++] = values[pHigh++];
}
}
while (pLow < high) {
tempValues[pMerged++] = values[pLow++];
}
while(pHigh< end) {
tempValues[pMerged++] = values[pHigh++];
}
}
}

列印時間：

.... take time: 573

5. Java SDK歸併

public static class SDKSorter implements Sorter {
public void sort(int[] values) {
Arrays.parallelSort(values);
}
}

時間列印：

.... take time: 338

可見android SDK的歸併效率很高，值得使用。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！