Android面试题目之4: 归并排序
Android面试题目之四: 归并排序
归并的核心思想是归并。归并的速度直接影响到算法的快慢。
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