ep6_7_0.cpp
上传用户:wxcui2006
上传日期:2022-07-12
资源大小:1274k
文件大小:3k
- /* 6.17 希尔排序(shell sort),又称缩小增量排序(diminishing increment sort)。
- 其思想如下:
- 设线性表L长度为n,取增量gap=n/2,即以L[0]和L[gap]为一组,L[1]和L[gap+1]为一组,
- L[2]和L[gap+2]为一组,……,L[n-gap]和L[n]为一组,分别进行插入排序。再取
- gap=gap/2,则分组成为L[0],L[gap],L[2gap],……为一组,L[1],L[gap+1],L[2gap+1],
- ……为一组,等等,分别进行插入排序。直到gap=1,这时分组成为整个表,并只有一个组,
- 再插入排序,完成全部任务。参见下图:
- 初始 20 26 49 21 15 6
- 1 20 - - 21 分组1,gap=3
- 26 - - 15 分组2
- 49 - - 6 分组3
- 20 15 6 21 26 49 结果
- 2 20 15 6 21 26 49 gap=1
- 6 15 20 21 26 49 结果
- 全部采用函数模板,包括希尔插入子程序。分组直接用增量控制在原线性表中进行插入排序。*/
- //此处不是纯面向对象的方法
- #include<iostream>
- #include<string>
- using namespace std;
- template <typename T,int size>class Orderedlist{
- int maxsize;
- int last;
- T slist[size];
- public:
- int getlast(){return last;}
- T getslist(int k){return slist[k];}
- void putslist(T t,int k){slist[k]=t;}
- Orderedlist(){last=-1;maxsize=size;}
- bool Insert(T & elem,int i);
- void print();
- // 无关成员函数省略,缺省的=等不必定义
- };//再次指出分号不可少
- template <typename T,int size> bool Orderedlist<T,size>::Insert(T & elem ,int i){
- if (i<0||i>last+1||last==maxsize-1) return false;
- else{
- for (int j=last;j>i;j--) slist[j]=slist[j-1];
- slist[i]=elem;
- last++;
- return true;
- }
- }
- template <typename T,int size> void Orderedlist<T,size>::print(){
- int i;
- for(i=0;i<=last;i++){
- cout<<slist[i];
- if(i%5==4) cout<<endl;
- else cout<<'t';
- }
- cout<<endl;
- }
- template <typename T,int size> void Shellsort(Orderedlist<T,size> & list){//非成员函数,仅以表模板类为参数
- int gap=(list.getlast()+1)/2;
- while(gap){
- Shellinsert(list,gap);//一趟排序
- gap/=2;
- }
- }//int size必须保留
- template <typename T,int size> void Shellinsert(Orderedlist<T,size> & list,const int gap){
- int i,j;
- T temp;
- //注意每一趟排序包含若干子序列,其中第一个子序列第一个元素是0号,第二个元素是gap号,
- //插入排序认为单个元素是排好序的,所以从每个子序列的第二个元素开始插入排序。
- for(i=gap;i<=list.getlast();i++){//从第一个子序列开始直接插入排序,但不是完成一个子序列,
- //再做下一个子系列,而是先做每个子序列的第一步,再做每个子序列的第二步,等等,穿插完成。
- //直接插入排序总是从后逐个向前,找到第一个比待插元素大的,则插在前面。
- temp=list.getslist(i);//待插元素放temp中
- j=i;
- while(j>=gap&&temp<list.getslist(j-gap)){//升序
- list.putslist(list.getslist(j-gap),j);//找的元素,只要比temp大,就后移,空出位置
- j-=gap;
- }
- list.putslist(temp,j);//将temp插入正确的空位
- }
- }
- int main(){
- const int h=8;
- int i;
- Orderedlist<string,h> ordlist;
- string n[h];
- char sp[h][10]={"南京大学","东南大学","交通大学","清华大学","天津大学","复旦大学",
- "浙江大学","同济大学"};
- for(i=0;i<h;i++) n[i]=sp[i];
- for(i=0;i<h;i++) ordlist.Insert(n[i],i); //建立顺序表
- cout<<"未排序表:"<<endl;
- ordlist.print();
- Shellsort(ordlist);
- cout<<"已排序表:"<<endl;
- ordlist.print();
- return 0;
- }
- /*本题希尔排序是独立的函数,而线性类模板作为形参,也是一种常见的用法。*/