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

 

可见android SDK的归并效率很高，值得使用。