ep6_7_0.cpp
上传用户:wxcui2006
上传日期:2022-07-12
资源大小:1274k
文件大小:3k
源码类别:

书籍源码

开发平台:

Visual C++

  1. /* 6.17  希尔排序(shell sort),又称缩小增量排序(diminishing increment sort)。
  2. 其思想如下:
  3. 设线性表L长度为n,取增量gap=n/2,即以L[0]和L[gap]为一组,L[1]和L[gap+1]为一组,
  4. L[2]和L[gap+2]为一组,……,L[n-gap]和L[n]为一组,分别进行插入排序。再取
  5. gap=gap/2,则分组成为L[0],L[gap],L[2gap],……为一组,L[1],L[gap+1],L[2gap+1],
  6. ……为一组,等等,分别进行插入排序。直到gap=1,这时分组成为整个表,并只有一个组,
  7. 再插入排序,完成全部任务。参见下图:
  8. 初始 20 26 49 21 15 6
  9. 1     20 - - 21 分组1,gap=3
  10.     26 - - 15 分组2
  11.     49 - - 6 分组3
  12.     20 15 6 21 26 49 结果
  13. 2     20 15 6 21 26 49 gap=1
  14.     6 15 20 21 26 49 结果
  15. 全部采用函数模板,包括希尔插入子程序。分组直接用增量控制在原线性表中进行插入排序。*/
  16. //此处不是纯面向对象的方法
  17. #include<iostream>
  18. #include<string>
  19. using namespace std;
  20. template <typename T,int size>class Orderedlist{
  21. int maxsize;
  22. int last;
  23. T slist[size];
  24. public:
  25. int getlast(){return last;}
  26. T getslist(int k){return slist[k];}
  27. void putslist(T t,int k){slist[k]=t;}
  28. Orderedlist(){last=-1;maxsize=size;}
  29. bool Insert(T & elem,int i);
  30. void print();
  31. // 无关成员函数省略,缺省的=等不必定义
  32. };//再次指出分号不可少
  33. template <typename T,int size> bool Orderedlist<T,size>::Insert(T & elem ,int i){
  34. if (i<0||i>last+1||last==maxsize-1) return false;
  35. else{
  36. for (int j=last;j>i;j--) slist[j]=slist[j-1];
  37. slist[i]=elem;
  38. last++;
  39. return true;
  40. }
  41. }
  42. template <typename T,int size> void Orderedlist<T,size>::print(){
  43. int i;
  44. for(i=0;i<=last;i++){
  45. cout<<slist[i];
  46. if(i%5==4) cout<<endl;
  47. else cout<<'t';
  48. }
  49. cout<<endl;
  50. }
  51. template <typename T,int size> void Shellsort(Orderedlist<T,size> & list){//非成员函数,仅以表模板类为参数
  52. int gap=(list.getlast()+1)/2;
  53. while(gap){
  54. Shellinsert(list,gap);//一趟排序
  55. gap/=2;
  56. }
  57. }//int size必须保留
  58. template <typename T,int size> void Shellinsert(Orderedlist<T,size> & list,const int gap){
  59. int i,j;
  60. T temp;
  61. //注意每一趟排序包含若干子序列,其中第一个子序列第一个元素是0号,第二个元素是gap号,
  62. //插入排序认为单个元素是排好序的,所以从每个子序列的第二个元素开始插入排序。
  63. for(i=gap;i<=list.getlast();i++){//从第一个子序列开始直接插入排序,但不是完成一个子序列,
  64. //再做下一个子系列,而是先做每个子序列的第一步,再做每个子序列的第二步,等等,穿插完成。
  65. //直接插入排序总是从后逐个向前,找到第一个比待插元素大的,则插在前面。
  66. temp=list.getslist(i);//待插元素放temp中
  67. j=i;
  68. while(j>=gap&&temp<list.getslist(j-gap)){//升序
  69. list.putslist(list.getslist(j-gap),j);//找的元素,只要比temp大,就后移,空出位置
  70. j-=gap;
  71. }
  72. list.putslist(temp,j);//将temp插入正确的空位
  73. }
  74. }
  75. int main(){
  76. const int h=8;
  77. int i;
  78. Orderedlist<string,h> ordlist;
  79. string n[h];
  80. char sp[h][10]={"南京大学","东南大学","交通大学","清华大学","天津大学","复旦大学",
  81. "浙江大学","同济大学"};
  82. for(i=0;i<h;i++)  n[i]=sp[i];
  83. for(i=0;i<h;i++)  ordlist.Insert(n[i],i); //建立顺序表
  84. cout<<"未排序表:"<<endl;
  85. ordlist.print();
  86. Shellsort(ordlist);
  87. cout<<"已排序表:"<<endl;
  88. ordlist.print();
  89. return 0;
  90. }
  91. /*本题希尔排序是独立的函数,而线性类模板作为形参,也是一种常见的用法。*/