解题报告

ACM解题报告

班级：191131 学号：20131000806 姓名：陈渊

日期：2014年8月28日

题号：1040

题目：As Easy As A+B 类型：排序算法

问题描述：

输入包含多次测试，每次测试给你一些整数（个数大于1，小于1000个），将它们按升序排列并输出

解题思路：这是个排序算法题，排序算法有很多种，冒泡排序、直接插入排序、希尔排序。。。。。。还可以调用库函数达到目的。此处使用希尔排序算法，并使用面向对象编程思想：

设计希尔排序类模板，具有int maxsize; int last; T slist[size];三个属性包含希尔排序的成员函数。

核心希尔排序算法实现思想为：线性表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，这时分组成为整个表，并只有一个组，再插入排序，完成全部任务。

程序流程图：

输入测试个数 输入当次需要排序的整数 列，存入希尔类线性表 调用希尔类成员函数 将线性表中的数列按 升序排序

输出排序结果

否

判断是否测试完成

是

退出

源代码： *#include #include using namespace std;

template class Orderedlist{ int maxsize; int last; T slist[size]; void Shellinsert(const int); 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(); void Shellsort(); };

template bool Orderedlist::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 void Orderedlist::print(int n){ for(int i=0;i

template void Orderedlist::Shellsort(){//成员函数 int gap = (last + 1) / 2; while (gap){ Shellinsert(gap);//一趟排序 gap /= 2; } }

template void Orderedlist::Shellinsert(const int gap){ int i, j;

T temp;

//注意每一趟排序包含若干子序列,其中第一个子序列第一个元素是0号,第二个元素是gap号， //插入排序认为单个元素是排好序的，所以从每个子序列的第二个元素开始插入排序。 for (i = gap; i <= last; i++) { //从第一个子序列开始直接插入排序，但不是完成一个子序列， //再做下一个子系列，而是先做每个子序列的第一步，再做每个子序列的第二步，等等， //穿插完成。直接插入排序总是从后逐个向前，找到第一个比待插元素大的，则插在前面。 temp = slist[i];//待插元素放temp中 j = i;

while (j >= gap&&temp

slist[j] = temp;//将temp插入正确的空位 } }

int main() { int n=0; int num,j; Orderedlist ordlist; cin>>j; for(int k=0;k>n&&n) { for(int i=0;i>num; ordlist.Insert(num, i); //建立顺序表 } }

ordlist.Shellsort();//排序 ordlist.print(n); } }

return 0;