C++STL之归并排序
2018-07-20 来源:open-open
/****************************** *mergeSort ******************************/ #include "stdafx.h" #include <vector> using namespace std; template <typename T> void mergeSort(vector<T>& vec) { vector<T> tempVec(vec.size()); mergeSort(vec, tempVec, 0, vec.size()- 1); } template <typename T> void mergeSort(vector<T>& vec, vector<T> tempVec, int left, int right) { if (left < right) { int center = (left + right)/2; mergeSort(vec, tempVec, left, center); mergeSort(vec, tempVec, center+1, right); mergeFunc(vec, tempVec, left, center+1 , right); //合并 } }; //合并函数 template <typename T> void mergeFunc(vector<T>& vec, vector<T> tempVec, int left, int Pos,int right) { int leftPos = left; //左边序列的位置,初始为左序列起点 int leftEnd = Pos-1 ; //左边序列的终点 int rightPos = Pos; //右边序列的位置,初始为右序列起点 int rightEnd = right; //右边序列的终点 int tempPos = left; //临时数组的位置,初始为临时数组的起点 int numElements = right - left + 1; //数组元素的个数 //两段数组合并 //两段数组已有序 while (leftPos <= leftEnd && rightPos <= rightEnd) //左边数组和右边数组都没有到终点 { //比较左边数组和右边数组值的大小 //把较小者放入临时数组 if (vec[leftPos] <= vec[rightPos]) { tempVec[tempPos++] = vec[leftPos++]; } else tempVec[tempPos++] = vec[rightPos++]; } // 只剩一个序列时,直接复制到临时数组 while (leftPos <= leftEnd) { tempVec[tempPos++] = vec[leftPos++]; } while (rightPos <= rightEnd) { tempVec[tempPos++] = vec[rightPos++]; } //将临时数组的值复制回源数组 int i = 0; for (; i< numElements; i++, rightEnd--) //这里从后向前复制,因为前面有很多垃圾数据 { vec[rightEnd] = tempVec[rightEnd]; } }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点!
本站所提供的图片等素材,版权归原作者所有,如需使用,请与原作者联系。
上一篇:C#获取机器硬件信息
下一篇:生成随机密码的C代码实现
最新资讯
热门推荐