所谓算法是指解题方案的准确而完整的描述。排序是数据处理的重要内容。所谓排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。排序的方法有很多，根据待排序的规模以及对数据处理的要求，可以采用不同的排序方法。排序算法是计算机算法运算中最重要的，一个好的排序不仅可以使信息查找的效率提高，而且直接影响计算机的工作效率。排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。在排序算法与性能比较这个程序里，将冒泡排序、简单选择排序、直接插入排序和快速排序这四种排序算法放在一个界面里，对这四种排序算法的时间复杂度，平均次数和平均移动次数进行研究。这个程序是在visual C++ 6.0这个系统开发的。
第一章 绪论
1.1排序算法研究意义
排序是计算机科学中最重要的研究问题之一。2000年被列为20世纪对科学和工程计算的研究与实践影响最大的十大问题之一。设想若字典中的词不是以字母的顺序排列，那么使用这样的字典将是何等困难；同样的，存在计算机存储器中的条款的次序，对于处理这些条款的算法的速度及简便性，也经常有深远的影响。排序算法是计算机算法运算中最重要的，一个好的排序不仅可以使信息查找的效率提高，而且直接影响计算机的工作效率。排序是计算机科学中最重要的研究问题之一。排序算法是一种基本并且常用的算法。
作为计算机科学中一项复杂而重要的技术，排序一直是计算机领域内人们感兴趣的课题，寻找速度快、附加存储空间开销小的高效排序算法也一直是人们追寻的目标。排序问题在计算机的诸多研究领域都具有重要的意义，例如在编译、操作系统、数据库管理系统、路由、置换网络等领域均涉及到和排序有关的问题。据估计，计算机所完成的所有工作中，有25％～50％与数据的排序有关。因此，对排序问题的研究具有广泛的实用价值和重要的理论意义。对冒泡排序、简单选择排序、直接插入排序和快速排序这四种排序算法的研究，有利于我们更好地使用它。本文通过对几种常用排序算法的讨论，并予以编程实现，采取对数据的测试与比较，验证算法的优越。
1.2排序算法的发展
对于今天排序技术的探索可以追溯到19世纪，美国人口统计局的Herman Hollerith发明了第一批具有排序装置的制表机，成功地应用到1890年的美国人口普查。关于Hollerith及其制表机的故事，Leon E. Truesdell曾在【The Development of Punch Card Tabulation（Washington: U. S. Bureau of the Census， 1965）】中进行了有趣而详尽地描述。排序例程曾经是为存储程序式计算机编写的第一个程序，因为它集中体现了计算机潜在的非数值应用。冯•诺伊曼在1954年为了检验EDVAC计算机指令代码的适用性以及评价他所建议的计算机组织的优点，编写了内部归并排序程序，Knuth在【Computing Surveys 2(1970)， 247~260】中描述了这个发展细节。
在德国，K. Zuse于1945年独立编写了用于直接插入排序的程序，作为他的Plankalkul语言中线性表操作的例子之一，这一开创性的工作推迟了近30年才发表。1946年在穆尔学校举行的有关计算的专题讨论会上，John Mauchly作了“排序和整理”的演讲，是第一个公开发表的关于计算机排序的讨论，包括直接插入排序和折半插入排序。到1952年左右，内部排序的许多方法已在程序设计领域广为流传，但理论上的研究却相对很少。Daniel Goldenberg用Whirlwind计算机编写了5个不同方法的排序程序，分别就最好情况和最坏情况进行了分析。由Howard B. Demuth于1956年撰写的博士论文【Electronic Data Sorting. Stanford University，1956】可以说是一篇非常值得关注的论文，因为这篇论文有助于奠定计算复杂性理论的基础。论文利用循环的、线性的以及随机的存储器，考虑了排序问题的3个抽象模型，并对每个模型提出了最优（或接近最优）的方法。Demuth的论文建立了如何把理论同实践相联系的重要思想。
事实上，计算的大多数早期历史都出现在比较难以得到的报告中，因为那时仅有少数人同计算机打交道。有关排序文献的第一次付印是在1955年，用的是三篇重要的综述性文章。第一篇文章是由J. C. Hosken撰写的【Proc.Eastern Joint Computer Conference 8(1955)，39~55】，综述了在计算机上进行排序的方法，以及所有可利用的专用设备，文中的54项参考文献大多数是以厂家的手册为基础的。第二篇文章是由E. H. Friend撰写的【Sorting on Electronic Computer Systems. Journal of the ACM 3(1956)， 134~168】是排序技术发展史的一个重要里程碑，Friend对相当多的内部和外部排序算法给出了细致的描述。第三篇文章是由D. W. Davies撰写的【Proc. Inst. Elec. Engineers 103B，Supplement 1(1956)，87~93】。1962年11月ACM主持召开了一次关于排序的研讨会，在会上宣读的大多数论文都发表在COMMUNICATIONS OF THE ACM1963年5月的刊物上，这些论文是当时技术发展水平的很好代表。
 
第二章 设计简介
排序的算法有很多，对空间的要求及其时间效率也不尽相同。下面列出了一些常见的排序算法。这里面插入排序和冒泡排序又被称作简单排序，他们对空间的要求不高，但是时间效率却不稳定。为了比较各种排序算法的优劣，要分析算法的时间复杂度和稳定性，评价排序的另一个主要标准是招待算法所需要的附加空间[1]。下面从它们的性能方面来说说几种排序。　
2.1算法的性能　
2.1.1时间性能 
一个程序的时间复杂度是程序运行从开始到结束所需的时间[2]。程序的运行时间与实例的特征无关。使用相同的排序算法对100个元素进行排序与对10000个元素进行排序所需的时间显然是不同的。当然，算法自身的好坏直接影响程序所需的运行时间。不同的排序算法对同一组元素（即相同的实例）进行排序，程序运行的时间一般是不相同的。
按平均的时间性能来分，有三类排序方法： 时间复杂度为O(nlogn)的方法有：快速排序、堆排序和归并排序，其中以快速排序为最好；时间复杂度为O(n2)的有：直接插入排序、起泡排序和简单选择排序，其中以直接插入为最好，特别是对那些对关键字近似有序的记录序列尤为如此。当待排记录序列按关键字顺序有序时，直接插入排序和起泡排序能达到O(n)的时间复杂度;而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为O(n2)，因此是应该尽量避免的情况。 值的注意的是，简单选择排序的时间性能不随记录序列中关键字的分布而改变。
2.1.2空间性能
一个程序的空间复杂度是指程序运行从开始到结束所需的存储量[2]。程序运行所需的存储空间包括两部分，即固定部分和可变部分。其中，固定部分空间与所处理数据的大小和个数无关，或者称与问题的实例的特征无关，主要包括程序代码、常量、简单变量、定长成分的结构变量所占的空间。面可变部分空间大小与算法在某次执行中处理的特定数据的大小和规模有关。例如，分别为100个元素的两个数组相加，与分别为10个元素的两个数组相加，所需的存储空间显然是不同的。这部分存储空间包括数据元素所占的空间，以及算法执行所需的额外空间，如递归栈所用的空间。
算法的空间复杂度的讨论类似于时间复杂度，并且一般说来，空间复杂度的计算比起时间复杂度的计算来得容易。此外，应当注意的是空间复杂度一般按最坏情况来分析。空间性能指的是排序过程中所需的辅助空间大小。所有的简单排序方法(包括：直接插入、冒泡和简单选择)和堆排序的空间复杂度都为O(1)；快速排序为O(log2n)，为栈所需的辅助空间;
2.1.3排序方法的稳定性能资源出自bysj999.com蓝天工作室
若待排序的序列中，存在多个具有相同关键字的记录，经过排序，这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对 次序发生了改变，则称该算法是不稳定的。假定在待排序的记录序列中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ki=kj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的;否则称为不稳定的。
稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，对基于比较的排序算法而言，元素交换的次数可能会少一些。对于不稳定的排序方法，只要能举出一个实例说明即可。快速排序是不稳定的排序方法。
2.2各种排序算法的比较
插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。反而在这种情况下，快速排序反而慢了。当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。若待排序的记录的关键字在一个明显有限范围内时，且空间允许是用桶排序。当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。当n较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下。宜用归并排序。当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序。

首先，从表头开始扫描，在扫描的过程中逐次比较相邻两个元素的大小。以图4-1为例，4与8进行比较，4小于8，4的位置不变；8与9进行比较，8小于9，8的位置不变；9与7进行比较，9大于7，7移到9的位置；5再与9进行比较，5小于9，5移到9的位置；下面的以此类推，直到按顺序排列。
4.2简单选择排序
排序是计算机程序设计中的一种重要操作，在基于交换排序的技术中，选择法排序以其算法简单而成为目前最为读者熟悉且实用而有效的方法之一。下面我们来看看简单选择排序的代码。
void select (int data[])
for(int i=0;i<SIZE;i++){
for(int j=i+1;j<SIZE+1;j++){
if(data[i]>data[j]){
int temp;
temp=data[i];
data[i]=data[j];
data[j]=temp;}
}
for (int k=0;k<=SIZE-1;k++)
cout<<data[k]<<'\t';
cout<<endl;}
cout<<endl;
}

扫描所有的数据，从中选出最小的元素，将它交换到表的最前面（即它应有的位置）；然后对剩下的子表采用同样的方法，直到数据按顺序排列为止。对于长度为n的序列，选择排序需要扫描n-1遍，每一遍扫描均从剩下的未排序的数据中选出最小的元素，然后将最小的元素与它应放的位置的元素进行交换。简单选择排序法在最坏情况下需要比较n(n-1)/2次。
4.3直接插入排序
插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。它的代码如下：
void sort(int data[]){
int r;
for(int i=1;i<SIZE;i++){
if(data[i]<data[i-1]){
r=data[i];
data[i]=data[i-1];
for(int j=i-1;r<data[j];j--)
data[j+1]=data[j];
data[j+1]=r;}
for (int t=0;t<=SIZE-1;t++)
cout<<data[t]<<'\t';
cout<<endl;}
}

所谓插入排序，是指将无序序列中的各元素依次插入到已经有序的数据中。将最小的元素直接放在合适的位置上。每一趟的排序都以此类推，直到排序为有序序列的元素。在简单插入排序法中，每一次比较后最多移掉一个逆序，因此，这种排序方法的效率与冒泡排序法相同。在最坏情况下，简单插入排序需要n(n-1)/2次比较。
4.4快速排序
快速排序是所有排序算法中最高效的一种。它采用了分治的思想：先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序，这样整个列表就有序了[4]。下面，我们来看快速排序各趟排序代码，及它实现的效果如图4-4所示.
void run(int* pData，int left，int right){
int i，j;
int middle，iTemp;
i = left;
j = right;
middle = pData[(left+right)/2];
do{
while((pData[i]<middle) && (i<right)) 
i++;
while((pData[j]>middle) && (j>left))
j--;
x4++;
if(i<=j){
iTemp = pData[i];
pData[i] = pData[j];
pData[j] = iTemp;
i++;
j--;
a4=+3;}
}while(i<=j); 
if(left<j)
run(pData，left，j); 
if(right>i)
run(pData，i，right);}
void QuickSort(int* pData，int Count){
run(pData,0,Count-1);}

快速排序是利用数据的第一个元素，中间的一个元素和最后一个元素，从这三个元素中，选择中项，设为p(data）,left和right分别指向表的起始和表的最后的位置。反复操作right逐渐减少，并逐次比较p(right)与p(data），直到发现了一个p(right)< p(data）为止，将p(right)移到 p(left)的位置上；left逐渐增加，并逐次比较p(left)与p(data），直到发现了一个p(left)>p(data）为止，将p(right)移到 p(left)的位置上,直到数据排序为一个有序序列。
 
总   结
这是我们第一次做课程设计，这个课程设计花了我们两个星期的时间。做了这次课程设计，我觉得课程设计这种形式真的是我们需要的，可以让我们学到很多，包括书上的、书外的。理论永远!=实际。通过这个程序，我们可以了解到，在冒泡排序、简单快速排序、直接插入排序和快速排序这四种排序中，简单排序中直接插入最好，快速排序最快，当文件为正序时，直接插入和冒泡均最佳。
在写程度时遇到了很多问题，我参考的是大一学的C程序设计这本书，这相对的写程序会比较简单。但在编程去实现各种算法的时候，却不是一次就成功的，总会出点差错，循环的边界条件啊，排序表的设计啊，等等，只得一次次改，等到程序终于正确运行的时候，才算真正会了这些算法，理论和实际永远差那么一点，不去做是体会不出来的。只有真正坐在电脑前让你自己写程序去实现它的时候，你才能真正知道自己会不会。在写程序的过程中，我想到了一个问题，那就是几种排序算法的时间复杂度是否一样是一样的，是什么影响时间复杂度。当情况不同时，选择哪种排序更为快捷？而想到这个问题是我再写几种算法的时间复杂度时想到的。如果是在平时，我会自己算一下，但是我会不确定我的答案是否一定是正确的，而我更相信我自己写的程序的演示结果。通过上机我利用编写的程序，察看演示结果，然后再观察当数据量大小一致时它们的时间复杂度，运行的速度，平均移动次数等，当当数据量大小不一致时，它们的时间复杂度，运行的速度，平均移动次数这些问题。
我为什么要研究这一课题呢？因为我认为排序在我们日常生活中运用的很广泛，它很普遍，随处都可以看见，也需要运用到它。研究它可以让我们加深对它的了解，当我们要运用到它的时候，我们要在使用的过程中具体问题具体分析，找出一个最佳的算法，节省我们的时间，更充分地利用它。
 
致   谢
感谢学校给我们提供的这个做课程设计的机会；炎炎夏日，即使什么也不会，也会觉得这样高的气温让人心情烦燥，更何况是机房，几十台电脑的运行会让人热的受不了。感谢学校给我们提供有空调的机房，让我们有一个舒适的机房可以上机；再一次感谢学校给我们提供的良好的环境，可以让我们在高温下愉快地学习
感谢胡老师对我们的指导;这个六月真的是很热；感谢胡老师在这样炎烈的日子里帮我们解决我们编程中遇到的问题，感谢他利用他自己的私人时间，帮我们检查我们论文中的错误；感谢他对我们的严格要求，让我们第一次做课程设计就不放松对自己的要求，对我们以后做课程设计打下了良好的基础！
众人拾柴，薪火高。在我程序出现错误，而我自己又找不出来的时候，我就会觉得郁闷，就没有了继续下去的力量。感谢同班同学帮我找出错误：感谢班上的同学在我懈怠时给予的提醒：感谢他们的帮助和支持！
 
参考文献
[1] 严蔚明，吴伟民．数据结构[M]．北京：清华大学出版社，1997
[2] 陈慧南．数据结构[M]．北京：人民邮电出版社，2008
[3] 李晓林，张俊．程序设计基础[M]．北京：中国铁道出版社，2008
[4] 廖贵荣．数据结构与算法[M]．北京：清华大学出版社，2004
[5] 张俊，张彦铎．C++面向对象程序设计[M]．北京：中国铁道出版社，2008