分治算法:
用分治策略实现n个元素进行排序的方法。
基本思想:
将待排序元素分成大小大致相同的两个子集合,分别对两个子集合进行排序,最终排好序的子集合合并成所要求的排好序的集合。
源码:
/*
* mergeSort.cpp
* 合并排序算法,算法导论P.17
* Created on: 2011-12-21
* Author: LiChanghai
*/
//#include <iostream>
#include <vector>
#include <iostream>
#include <iterator>
using namespace std;
#define FLT_MAX 1.0E38 //定义一个很大的值作为哨兵
//对于待排序的数组 A[p...r], 其子数组A[p...q],A[q+1...r]已排好序
//函数 subMerge(A, p, q, r), 将两个已排好序的子数组A[p...q],A[q+1...r]
//合并成一个有序的数组代替当前的数组A[p...r]
template<typename T>
void subMerge(vector<T> &array,
typename vector<T>::iterator iterBegin,
typename vector<T>::iterator iterBarrier,
typename vector<T>::iterator iterEnd)
{
//创建两个数组,分别存放以iterBarrier为界线的array的左边部分和右边部分
vector<T> arrayLeft(iterBegin, iterBarrier+1);
vector<T> arrayRight(iterBarrier+1, iterEnd);
//在两个数组尾部分别放一个“哨兵”
T temp = T(FLT_MAX);
arrayLeft.push_back(temp);
arrayRight.push_back(temp);
//定义分别指向两个数组的迭代器
typename vector<T>::iterator iterLeft = arrayLeft.begin();
typename vector<T>::iterator iterRight = arrayRight.begin();
//定义指向原数组array的迭代器
typename vector<T>::iterator iterArray = iterBegin;
for(; iterArray != iterEnd; ++iterArray)
if(*iterLeft < *iterRight) //如果左边小,将左边的值放入原数组
{
*iterArray = *iterLeft;
++iterLeft;
}
else //如果右边小,将右边的值放入原数组
{
*iterArray = *iterRight;
++iterRight;
}
return;
}
//函数 mergeSort(A, p, r) 调用subMerge对任意数组排序,p, r为下标
//mergeSort(A, p, r)首先将数组A分为两部分
//然后递归调用其本身对这两部分 分别排序
//依次递归下去,直到只剩2个数的时候完成这两个数的排序
//然后再层层返回调用处,将已排好序的子序列合并成更大的有序序列
//最后一次调用subMerge时完成数组的排序
template<typename T>
void mergeSort(vector<T> &vec,
typename vector<T>::iterator iterHead,
typename vector<T>::iterator iterTail)
{
//测试 mergeSort 调用了多少次
//static int times_mergeSort=0;
//cout<<"the "<<++times_mergeSort<<" call mergeSort()"<<endl;
//测试 subMerge 调用了多少次
//static int times_subMerge=0;
if(iterHead < iterTail-1)
{
//数组长度的一半(错误的方法)
//typename vector<T>::size_type halfLength = (vec.size()-1)/2;
//数组长度的一半(正确方法)
typename vector<T>::difference_type halfLength=( (iterTail-iterHead)-1)/2;
//定义一个迭代器指向数组 vec 中间位置
typename vector<T>::iterator iterDivide = iterHead + halfLength;
mergeSort(vec, iterHead, iterDivide+1); //递归调用自身对前半段排序
mergeSort(vec, iterDivide+1, iterTail); //递归调用自身对后半段排序
//cout<<"the "<<++times_subMerge<<" call subMerge()"<<endl;
subMerge(vec, iterHead, iterDivide, iterTail); //将上面排好序的两段合并
}
return;
}
int main()
{
vector<int> vec;
vec.push_back(0);
vec.push_back(9);
vec.push_back(8);
vec.push_back(7);
vec.push_back(6);
vec.push_back(5);
vec.push_back(4);
vec.push_back(3);
vec.push_back(2);
vec.push_back(1);
int size = vec.size();
int *phead = &vec[0];
int *ptail = &vec[size];
mergeSort(vec,phead,ptail);
for(int i=0;i<10;i++)
cout<<vec[i]<<" ";
cout<<endl;
return 0;
}
运行结果: