C++——算法基础之排序——二路归并排序

今天，大白跟大家说一说，二路归并排序

二路归并排序：是一种比较快的排序方法。

思想：将序列切半分开，然后对左右进行递归切半，直至最小单元序列内元素个数为1。然后依次将两个序列有序合并为一个序列，直至所有元素都在一个序列内。

步骤：

1，递归将序列分割。

2，合并两个序列：利用等大小的临时储存空间，将两个序列从左到右依次比较，将较小的元素存入临时储存空间中。再将两个序列中剩下的元素依次存入临时储存空间中，在将临时储存空间中的元素按对应位置copy到原来的序列中。

#include <functional> #include <algorithm> #include <numeric> #include <stack> #include <queue> #include <vector> #include <string> #include <cstring> #include <sstream> using namespace std; void Merge (int sourceArr[], int tempArr[], int startIndex, int midIndex, int endIndex) { int i = startIndex; int j = midIndex + 1; int k = startIndex; while(i != midIndex + 1 && j != endIndex + 1) { if(sourceArr[i] >= sourceArr[j]) { tempArr[k++] = sourceArr[j++]; } else { tempArr[k++] = sourceArr[i++]; } } while(i != midIndex + 1) { tempArr[k++] = sourceArr[i++]; } while(j != endIndex + 1) { tempArr[k++] = sourceArr[j++]; } for(i = startIndex; i <= endIndex; i++) { sourceArr[i] = tempArr[i]; } } void MergeSort (int sourceArr[], int tempArr[], int startIndex, int endIndex) { int midIndex; if(startIndex < endIndex) { midIndex = (startIndex + endIndex) / 2; MergeSort (sourceArr, tempArr, startIndex, midIndex); MergeSort (sourceArr, tempArr, midIndex + 1, endIndex); Merge (sourceArr, tempArr, startIndex, midIndex, endIndex); } } int keys[] = { 88, 22, 13, 69 }; int main () { int tempkeys[10]; MergeSort (keys, tempkeys, 0, 3); for(int i = 0; i < 10; i++) { cout << " " << keys[i]; } cout << endl; return 0; }