数据结构基础(5) --归并排序

归并排序的基本思想：

    将两个或两个以上的有序子序列”归并”为一个有序序列:假定待排序表含有n个记录, 则可以看成是n个有序的子表, 每个子表长度为1, 然后两两归并, 得到[n/2]个长度为2或1的有序表,; 再量量归并, ...., 如此重复, 直到合并成为一个长度为n的有序表为止, 这种排序方法称为2-路归并排序.如图为一个2-路归并排序的一个示例:

/**说明:将有序的记录序列 initList[left:mid] 和 initList[mid+1:right]归并为有序的记录序列 initList[left:right]initList: 原始的有序序列[分为两段]tmpList: 合并过程中需要的中间序列left: initList最左边元素的下标mid: 指向第一个有序序列的最后一个元素的下标right: initList最右边元素的下标 */ template <typename Type> int Merge(Type *initList, Type *tmpList, int left, int mid, int right) {//先将待归并的数组复制到tmpList中去std::copy(initList+left, initList+right+1, tmpList+left); // 同下: // for (int i = left; i <= right; ++i) // { // tmpList[i] = initList[i]; // }int s1 = left, s2 = mid+1;int iResult = left;while (s1 <= mid && s2 <= right){if (tmpList[s1] <= tmpList[s2]){initList[iResult ++] = tmpList[s1 ++];}else{initList[iResult ++] = tmpList[s2 ++];}}int *end;if (s1 <= mid)end = std::copy(tmpList+s1, tmpList+mid+1, initList+iResult);if (s2 <= right)end = std::copy(tmpList+s2, tmpList+right+1, initList+iResult);return end - (initList+left);// 同下:其实这两个循环只有一个会执行 // while (s1 <= mid) // { // initList[iResult ++] = tmpList[s1 ++]; // } // while (s2 <= right) // { // initList[iResult ++] = tmpList[s2 ++]; // } // // return iResult; } //二路归并排序-递归算法 template <typename Type> void mergeSort(Type *initList, Type *tmpList, int left, int right) {if (left >= right)return;int mid = (left+right)/2;mergeSort(initList, tmpList, left, mid); //先将左边元素排序mergeSort(initList, tmpList, mid+1, right); //后将右边元素排序Merge(initList, tmpList, left, mid, right); //合并 }

可以看出对n个记录进行归并排序的时间复杂度为Ο(nlogn)。即:

    (1)每一趟归并(合并)的时间复杂度为 O(n);

    (2)总共需进行[logn]趟。

总结

以上是生活随笔为你收集整理的数据结构基础(5) --归并排序的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。