燕山大学结课论文说明书课程：C++面向对象程序设计B题目：排序问题学院（系）：理学院年级专业：2010计算数学学号： ************学生姓名：***指导教师：***教师职称：目录摘要...................................................................... (2)一、论文背景简介 (2)二、程序代码............................................................................... (3)三、结果及分析......................................................................... (11)四、参考文献............................................................................... (12)摘要随着科技的不断发展，计算机的应用领域越来越广，但由于计算机硬件的速度和存储空间的有限性，如何提高计算机速度并节省存储空间一直成为软件编制人员努力的方向，在众多措施中，排序操作成为程序设计人员考虑的因素之一，排序方法选择得当与否直接影响程序执行的速度和辅助存储空间的占有量，进而影响整个软件的性能。

课程背景一个排序算法是稳定的，就是当有两个有相等关键的纪录R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。

当相等的元素是无法分辨的，比如像是整数，稳定度并不是一个问题。

然而，假设以下的数对将要以他们的第一个数字来排序。

（4,1）（3,1）（3,7）（5,6）在这个状况下，有可能产生两种不同的结果，一个是依照相等的键值维持相对的次序，而另外一个则没有：（3,1）（3,7）（4,1）（5,6）（维持次序) （3,7）（3,1）（4,1）（5,6）（次序被改变) 不稳定排序算法可能会在相等的键值中改变纪录的相对次序，但是稳定排序算法从来不会如此。

不稳定排序算法可以被特别地实现为稳定。

作这件事情的一个方式是人工扩充键值的比较，如此在其他方面相同键值的两个对象间之比较，就会被决定使用在原先数据次序中的条目，当作一个同分决赛。

然而，要记住这种次序通常牵涉到额外的空间负担。

在计算机科学所使用的排序算法通常被分类为：a)计算的复杂度（最差、平均、和最好性能），依据列表（list）的大小（n）。

一般而言，好的性能是O(nlog n)，且坏的性能是O(n平方)。

对于一个排序理想的性能是O(n)。

仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要O(nlog n)。

b)存储器使用量（空间复杂度）（以及其他电脑资源的使用）c)稳定度：稳定排序算法会依照相等的关键（换言之就是值）维持纪录的相对次序。

d)一般的方法：插入、交换、选择、合并等等。

交换排序包含冒泡排序和快速排序。

插入排序包含希尔排序，选择排序包括堆排序等。

排序的算法有很多，对空间的要求及其时间效率也不尽相同。

下面列出了一些常见的排序算法。

这里面插入排序和冒泡排序又被称作简单排序，他们对空间的要求不高，但是时间效率却不稳定；而后面三种排序相对于简单排序对空间的要求稍高一点，但时间效率却能稳定在很高的水平。

基数排序是针对关键字在一个较小范围内的排序算法。

插入排序冒泡排序选择排序快速排序堆排序归并排序基数排序希尔排序。

程序代码#include<iostream>using namespace std;const int maxsize=100;int num=0;//定义全局变量，为每一趟的输出做准备int x=0;template<class type>class sortlist{private:int currentsize;//数据表中数据元素的个数public:type *arr;//存储数据元素的向量（排序表）sortlist():currentsize(0){arr=new type[maxsize];}//构造函数sortlist(int n){arr=new type[maxsize];currentsize=n;}void insert(int i,type x){arr[i]=x;}~sortlist(){delete []arr;}//析构函数void swap(type &x,type &y)//数据元素x和y交换位置{type temp=x;x=y;y=temp;}void bubblesort();//冒泡排序void quicksort(int low,int high);//快速排序void insertionsort();//直接插入排序void binaryinsertsort();//折半插入排序void selectsort();//简单选择排序void heapsort();//堆排序void mergesort(sortlist<type> &table);//归并排序void filterdown(const int start);//建立最大堆void mergepass(sortlist<type>&sourcetable,sortlist<type>&mergedtable,const int len);//一趟归并void merge(sortlist<type>&sourcetable,sortlist<type>&mergedtable,const int left,const int mid,const int right);//两路归并算法};template <class type>//直接插入排序void sortlist<type>::insertionsort(){type temp;int j;for(int i=1;i<=currentsize-1;i++){temp=arr[i];j=i-1;while(j>=0&&temp<arr[j]){arr[j+1]=arr[j];j--;}arr[j+1]=temp;cout<<"第"<<++num<<"趟排序结果为:";for(int t=0;t<currentsize;t++)cout<<arr[t]<<" ";cout<<endl;}num=0;}template <class type>//折半插入排序void sortlist<type>::binaryinsertsort(){type temp;int left,right;for(int i=1;i<currentsize;i++){left=0;right=i-1;temp=arr[i];while(left<=right)//找插入位置{int mid=(left+right)/2;if(temp<arr[mid])right=mid-1;else left=mid+1;}for(int k=i-1;k>=left;k--)//向后移动arr[k+1]=arr[k];arr[left]=temp;cout<<"第"<<++num<<"趟排序结果为:";for(int t=0;t<currentsize;t++)cout<<arr[t]<<" ";cout<<endl;}num=0;}template <class type>//冒泡排序void sortlist<type>:: bubblesort(){int i=1;int finish=0;//0表示还没有排好序while(i<currentsize &&!finish){finish=1;//排序结束标志置为,假定已经排好序for(int j=0;j<currentsize-i;j++)if(arr[j]>arr[j+1])//逆序{swap(arr[j],arr[j+1]);//相邻元素交换位置finish=0;}//排序结束标志置为,表示本趟发生了交换，说明还没有排好序i++;cout<<"第"<<++num<<"趟排序结果为:";for(int t=0;t<currentsize;t++)cout<<arr[t]<<" ";cout<<endl;}num=0;}template <class type>void sortlist<type>::selectsort()//简单选择排序{int k;for(int i=0;i<currentsize-1;i++){k=i;for(int j=i+1;j<currentsize;j++)if(arr[j]<arr[k])k=j;//k 指示当前序列中最小者的位置if(k!=i)//最小关键字的数据元素位置不等于iswap(arr[i],arr[k]);cout<<"第"<<++num<<"趟排序结果为:";for(int t=0;t<currentsize;t++)cout<<arr[t]<<" ";cout<<endl;}num=0;}template <class type>//快速排序void sortlist<type>::quicksort(int low,int high)//在待排序区间[low,high]上，递归地进行快速排序{int i=low,j=high;type temp=arr[low];//取区间第一个位置为基准位置if(i<j){while(i<j){while(i<j&&temp<arr[j])j--;if(i<j){swap(arr[i],arr[j]);i++;}while(i<j&&temp>=arr[i])i++;if(i<j){swap(arr[i],arr[j]);j--;}}arr[i]=temp;//将基准元素就位cout<<"第"<<++x<<"趟排序结果为:";for(int t=0;t<currentsize;t++)cout<<arr[t]<<" ";cout<<endl;quicksort(low,i-1);//在左子区间递归进行快速排序quicksort(i+1,high);//在右子区间递归进行快速排序}}template <class type>//建立最大堆void sortlist<type>::filterdown(const int start){//向下调整使从start开始到currentsize-1为止的子表成为最大堆int i=start,j=2*i+1;//j为i的左孩子int tablesize=currentsize;type temp=arr[i];while(j<=currentsize-1){if(j<currentsize-1 && arr[j]<arr[j+1])j++;//在两个孩子中选关键字较大者if(temp>=arr[j])break;else{arr[i]=arr[j];i=j;j=2*j+1;}}arr[i]=temp;}template <class type>void sortlist<type>::heapsort(){int tablesize=currentsize;for(int i=(currentsize-2)/2;i>=0;i--)filterdown(i); //初始建堆for(int j=currentsize-1;j>=1;j--){swap(arr[0],arr[j]);//堆顶元素和最后一个元素交换currentsize--;filterdown(0);//重建最大堆cout<<"第"<<++num<<"趟排序结果为:";for(int t=0;t<tablesize;t++)cout<<arr[t]<<" ";cout<<endl;}num=0;currentsize=tablesize;}template <class type>void sortlist<type>::merge(sortlist<type>&sourcetable,sortlist<type>&mergedtable,const int left,const int mid,const int right){int i=left,j=mid+1,k=left;//指针初始化//i是前一段的当前元素位置，j是后一段的当前元素位置，k是辅助数组的当前位置while(i<=mid&&j<=right)if(sourcetable.arr[i]<=sourcetable.arr[j]){mergedtable.arr[k]=sourcetable.arr[i];i++;k++;}else{mergedtable.arr[k]=sourcetable.arr[j];j++;k++;}if(i<=mid)for(int p=k,q=i;q<=mid;p++,q++)mergedtable.arr[p]=sourcetable.arr[q];//把前一段复制到mergedtable elsefor(int p=k,q=j;q<=right;p++,q++)mergedtable.arr[p]=sourcetable.arr[q];//把后一段复制到mergedtable}template <class type>void sortlist<type>::mergepass(sortlist<type>&sourcetable,sortlist<type>&mergedtable,const int len){int i=0;while(i+2*len<=currentsize-1)//表示至少有个子序列{merge(sourcetable,mergedtable,i,i+len-1,i+2*len-1);i+=2*len;}if(i+len<=currentsize-1)//若只有最后两个子序列merge(sourcetable,mergedtable,i,i+len-1,currentsize-1);else//若只有最后一个子序列for(int j=i;j<=currentsize-1;j++)mergedtable.arr[j]=sourcetable.arr[j];if(len<=currentsize-1){if(num<currentsize){cout<<"第"<<++num<<"趟排序结果为:";for(int t=0;t<currentsize;t++)cout<<mergedtable.arr[t]<<" ";cout<<endl;}}}template <class type>void sortlist<type>::mergesort(sortlist<type> &table ){//按数据元素关键字非递减的顺序对排序表table中数据元素进行递归排序sortlist<type> temptable;int len=1;while(len<currentsize){mergepass(table,temptable,len);len*=2;mergepass(temptable,table,len);len*=2;}num=0;}int main()//主函数{cout<<"***********************************************************************"<<en dl;cout<<" 排序问题"<<endl; cout<<"********************************************************************* **"<<endl<<endl<<endl;int c=1;char ch;int n1=0;while(c!=0){cout<<"\n================================================================= ======"<<endl;cout<<"======================可供选择的排序方法=============================="<<endl;cout<<" 1 直接插入排序 2 折半插入排序"<<endl; cout<<" 3 冒泡排序 4 简单选择排序"<<endl; cout<<" 5 快速排序 6 堆排序"<<endl; cout<<" 7 归并排序0 退出排序程序"<<endl; cout<<"=================================================================== ===="<<endl;cout<<"\n 请输入您需要的排序种类:";cin>>ch;if(ch=='0') {cout<<" 您已成功退出该系统!"<<endl;system("pause"); return 0;} int n,number;if(ch>='0'&&ch<='7'){cout<<"\n 输入您要进行排序的数的个数：";cin>>n;cout<<"\n 请输入"<<n<<"个数：";sortlist<int>table(n);for(int i=0;i<n;i++){cin>>number;table.insert(i,number);}switch(ch){case '1':cout<<"\n *******您选择的是直接插入排序*******\n"<<endl;table.insertionsort();break;system("pause");break;case '2':cout<<"\n *******您选择的是折半插入排序*******\n"<<endl;table.binaryinsertsort();break;system("pause");break;case '3':cout<<"\n *******您选择的是冒泡排序*******\n"<<endl;table.bubblesort();break;system("pause");break;case '4':cout<<"\n *******您选择的是简单选择排序*******\n"<<endl;table.selectsort();break;system("pause");break;case '5':cout<<"\n *******您选择的是快速排序*******\n"<<endl;table.quicksort(0,n-1);break;system("pause");break;case '6':cout<<"\n *******您选择的是堆排序*******\n"<<endl;table.heapsort();break;system("pause");break;case '7':cout<<"\n *******您选择的是归并排序*******\n"<<endl;table.mergesort(table);break;system("pause");break;}}}system("pause");return 0;}结果及分析：参考文献[1]王晓东 C++程序设计简明教程中国水利水电出版社 2008。