【程序5-1】分治法SolutionType DandC(ProblemType P){ProblemType P1，P2， ，P k。
if (Small(P)) return S(P)。
//子问题P足够小，用S(P)直接求解else {Divide(P，P1，P2， ，P k)。
//将问题P分解成子问题P1, P2, …,P k Return Combine(DandC(P1)，DandC(P2)，…，DandC(P k))。
//求解子问题，并合并解}}【程序5-2】一分为二的分治法SolutionType DandC(int left，int right){if (Small(left，right)) return S(left，right)。
else {int m=Divide(left，right)。
//以m为界将问题分解成两个子问题Return Combine(DandC(left，m)，DandC(m+1，right))。
//分别求解子问题，并合并解}}【程序5-3】可排序表类template <class K, class D>struct E{ //可排序表中元素的类型operator K()const { return key。
} //重载类型转换运算符K key。
//关键字可以比较大小D data。
//其他数据}。
template <class T>class SortableList{ //可排序表类public:SortableList(int mSize) //构造函数{maxSize=mSize。
l=new T[maxSize]。
n=0。
}~SortableList(){delete []l。
}//析构函数private:T *l 。
//动态生成一维数组int maxSize。
//线性表的最大表长int n。
//线性表的实际长度}。
【程序5-4】求最大最小元template <class T>void SortableList<T>::MaxMin(T& max, T& min)const{if (n==0)return。
max=min=l[0]。
for (int i=1。
i<n。
i++) {if(l[i]>max) max=l[i]。
if(l[i]<min) min=l[i]。
}}【程序5-5】分治法求最大、最小元template <class T>void SortableList<T>::MaxMin(int i, int j, T& max, T& min) const{ //前置条件：i和j，0≤i≤j＜表长，是表的下标范围的界T min1, max1。
if (i==j) max=min=l[i]。
//表中只有一个元素时else if (i==j-1) //表中有两个元素时if (l[i]<l[j]) {max=l[j]。
min=l[i]。
}else {max=l[i]。
min=l[j]。
}else {//表中多于两个元素时int m=(i+j)/2。
//对半分割MaxMin(i, m, max, min)。
//求前半部子表中的最大、最小元MaxMin(m+1, j, max1, min1)。
//求后半部子表中的最大、最小元if (max<max1) max=max1。
//两子表最大元的大者为原表最大元if (min>min1) min=min1。
//两子表最小元的小者为原表最小元}}【程序5-6】二分搜索算法框架template <class T>int SortableList<T>::BSearch(const T& x, int left, int right)const{if (left<=right){int m=Divide(left, right)。
//按照某种规则求分割点mif (x<l[m]) return BSearch(x, left, m-1)。
else if (x>l[m]) return BSearch(x, m+1, right)。
else return m。
//搜索成功}return -1。
//搜索失败}【程序5-7】对半搜索递归算法template <class T>int SortableList<T>::BSearch(const T& x, int left, int right)const{if (left<=right){//若表（子表）非空int m=(left+right)/2。
//对半分割if (x<l[m]) return BSearch(x, left, m-1)。
//搜索左半子表else if (x>l[m]) return BSearch(x, m+1, right)。
//搜索右半子表else return m。
//搜索成功}return-1。
//搜索失败}【程序5-8】对半搜索的迭代算法template <class T>int SortableList<T>::BSearch1(const T& x)const{int m,left=0,right=n-1。
while (left<=right){m=(left+right)/2。
if (x<l[m]) right=m-1。
else if (x>l[m]) left=m+1。
else return m。
//搜索成功}return-1。
//搜索失败}【程序5-9】 Merge函数template <class T>void SortableList<T>::Merge(int left,int mid,int right){T* temp=new T[right-left+1]。
int i=left,j=mid+1,k=0。
while (( i<=mid )&& (j<=right))if (l[i]<=l[j]) temp[k++]=l[i++]。
else temp[k++]=l[j++]。
while (i<=mid) temp[k++]=l[i++]。
while (j<=right) temp[k++]=l[j++]。
for (i=0,k=left。
k<=right。
) l[k++] = temp[i++]。
}【程序5-10】两路合并排序template <class T>void SortableList<T>::MergeSort(){MergeSort(0, n-1)。
}template <class T>void SortableList<T>::MergeSort(int left, int right){if (left<right) { //若序列的长度超过1，则划分成两个子序列int mid = (left+right)/2。
//将待排序的序列一分为二MergeSort(left, mid)。
//对左子序列排序MergeSort(mid+1, right)。
//对右子序列排序Merge(left, mid, right)。
//将两个有序子序列合并成一个有序序列}}【程序5-11】分划函数template <class T>int SortableList<T>::Partition(int left,int right){//前置条件：left rightint i=left,j=right+1。
do{do i++。
while (l[i]<l[left])。
do j--。
while (l[j]>l[left])。
if (i<j) Swap(i,j)。
//交换两个元素l[i]和l[j]}while (i<j)。
Swap(left,j)。
return j。
}【程序5-12】快速排序template <class T>void SortableList<T>::QuickSort(){QuickSort(0, n-1)。
}template <class T>void SortableList<T>::QuickSort(int left, int right){if(left<right){ //当序列长度大于1时，需进行分割int j=Partition(left, right)。
//对[left,right]范围内的序列进行分划QuickSort(left, j-1)。
//对左子序列实施快速排序QuickSort(j+1, right)。
//对右子序列实施快速排序}}【程序5-13】 Select函数template <class T>ResultCode SortableList<T>::Select1(T& x, int k){if(n<=0||k>n||k<=0) return OutOfBounds。
int left=0, right=n。
l[n] = INFTY。
//INFTY是一个大值do {//条件：left≤rightint j=rand()% (right-left+1)+left。
//随机选择主元Swap(left, j)。
//将主元交换至位置left处j=Partition(left, right)。
//执行分划操作if (k==j+1) {x=l[j]。
return Success。
}else if (k<j+1) right=j。
//注意此处right=j，而不是j-1else left=j+1。
} while (true)。
}【程序5-14】线性时间选择算法ResultCode SortableList<T>::Select(T& x,int k){if(n<=0||k>n||k<=0) return OutOfBounds。
int j=Select(k,0,n-1,5)。
x=l[j]。
return Success。
}template <class T>int SortableList<T>::Select(int k, int left, int right, int r){int n=right-left+1。