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

书籍源码

开发平台:

Visual C++

  1. /* 6.7  希尔排序(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. //此处是纯面向对象的方法
  18. #include<iostream>
  19. #include<string>
  20. using namespace std;
  21. template <typename T,int size>class Orderedlist{
  22. int maxsize;
  23. int last;
  24. T slist[size];
  25. void Shellinsert(const int);
  26. public:
  27. int getlast(){return last;}
  28. T getslist(int k){return slist[k];}
  29. void putslist(T t,int k){slist[k]=t;}
  30. Orderedlist(){last=-1;maxsize=size;}
  31. bool Insert(T & elem,int i);
  32. void print();
  33. void Shellsort();
  34. // 无关成员函数省略,缺省的=等不必定义
  35. };//再次指出分号不可少
  36. template <typename T,int size> bool Orderedlist<T,size>::Insert(T & elem ,int i){
  37. if (i<0||i>last+1||last==maxsize-1) return false;
  38. else{
  39. for (int j=last;j>i;j--) slist[j]=slist[j-1];
  40. slist[i]=elem;
  41. last++;
  42. return true;
  43. }
  44. }
  45. template <typename T,int size> void Orderedlist<T,size>::print(){
  46. int i;
  47. for(i=0;i<=last;i++){
  48. cout<<slist[i];
  49. if(i%5==4) cout<<endl;
  50. else cout<<'t';
  51. }
  52. cout<<endl;
  53. }
  54. template <typename T,int size> void Orderedlist<T,size>::Shellsort(){//成员函数
  55. int gap=(last+1)/2;
  56. while(gap){
  57. Shellinsert(gap);//一趟排序
  58. gap/=2;
  59. }
  60. }
  61. template <typename T,int size> void Orderedlist<T,size>::Shellinsert(const int gap){
  62. int i,j;
  63. T temp;
  64. //注意每一趟排序包含若干子序列,其中第一个子序列第一个元素是0号,第二个元素是gap号,
  65. //插入排序认为单个元素是排好序的,所以从每个子序列的第二个元素开始插入排序。
  66. for(i=gap;i<=last;i++){//从第一个子序列开始直接插入排序,但不是完成一个子序列,
  67. //再做下一个子系列,而是先做每个子序列的第一步,再做每个子序列的第二步,等等,穿插完成。
  68. //直接插入排序总是从后逐个向前,找到第一个比待插元素大的,则插在前面。
  69. temp=slist[i];//待插元素放temp中
  70. j=i;
  71. while(j>=gap&&temp<slist[j-gap]){//升序
  72. slist[j]=slist[j-gap];//找的元素,只要比temp大,就后移,空出位置
  73. j-=gap;
  74. }
  75. slist[j]=temp;//将temp插入正确的空位
  76. }
  77. }
  78. int main(){
  79. const int h=8;
  80. int i;
  81. Orderedlist<string,100> ordlist;
  82. string n[h];
  83. char sp[h][10]={"南京大学","东南大学","交通大学","清华大学","天津大学","复旦大学",
  84. "浙江大学","同济大学"};
  85. for(i=0;i<h;i++)  n[i]=sp[i];
  86. for(i=0;i<h;i++)  ordlist.Insert(n[i],i); //建立顺序表
  87. cout<<"未排序表:"<<endl;
  88. ordlist.print();
  89. ordlist.Shellsort();
  90. cout<<"已排序表:"<<endl;
  91. ordlist.print();
  92. return 0;
  93. }
  94. /*本题希尔排序是成员函数,是C++的标准用法,标准模板库(STL)就是如此用的。*/