阅读量:2
归并排序
二路归并属于迭代式算法。每步迭代中，只需比较两个待归并向量的首元素，将小者取出并追加到输出向量的末尾，该元素在原向量中的后继则成为新的首元素。如此往复，直到某一向量为空。最后，将另一非空的向量整体接至输出向量的末尾。
void mergeSort(int* arr, int lo, int hi) { if (hi - lo < 2) return;//一个元素时就可以不分了 int mi = lo + ((hi - lo) >> 1); mergeSort(arr, lo, mi); mergeSort(arr, mi, hi); merge(arr, lo, mi, hi); } void merge(int* arr, int lo, int mi, int hi) { int p1 = lo; int p2 = mi; int* temp = new int[hi - lo]; int i = 0; while ((p1 < mi) && (p2 < hi )) { if (arr[p1] < arr[p2]) { temp[i++] = arr[p1++]; } else { temp[i++] = arr[p2++]; } } while (p1 < mi) { temp[i++] = arr[p1++]; } while (p2 < hi) { temp[i++] = arr[p2++]; } for (int j = 0; j < hi - lo; j++) arr[lo + j] = temp[j]; delete[] temp; } 