综合实践课程《创新思维-程序设计（高级班）》（论文）排序算法摘要排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程叫做排序。假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。很多题目，当获取信息后，需要将信息进行排序处理，这样才便于对这些信息的利用，所以，也可以说，排好序是处理好一个题目第一步的关键。关键词：稳定排序；不稳定排序；快速排序；时间复杂度.目录一、常见的排序算法1.排序的分类2.常见排序（1）冒泡排序（2）快速排序（3）桶排序二、排序算法的应用1.例1.2.例2.3.优缺点三、总结1.致谢2.参考文献一、常见的排序算法1.排序的分类（1）分类◆稳定排序：假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在用某种排序法排序后，若这些相同关键字的元素的相对次序仍然不变，则这种排序方法是稳定的。其中冒泡，插入，基数，归并属于稳定排序，选择，快速，希尔，堆属于不稳定排序。◆就地排序：若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间为O（1）,则称为就地排序。（2）常见排序不稳定排序算法：快速排序、希尔排序、选择排序……稳定排序算法：冒泡排序、直接插入排序、归并排序……2.常见排序（1）冒泡排序简介：冒泡排序是一种较简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。冒泡排序十分稳定，但速度慢，时间复杂度为O（n^2）。Pascal代码框架：fori:=1ton-1dobegink:=iforj:=i+1tondoifa[j]>a[i]thenbegintmp:=a[i];a[i]:=a[j];a[j]:=tmp;end；end;（2）快速排序简介：快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序是已知排序中，速度最快的一种，二分的思想，能让大部分时间节省，时间复杂度最快达O（nlog2n），但如果遇到最坏情况，就会退化成冒泡。但你的运气不可能那么好，所以，我个人推荐使用快排。Pascal代码框架：procedureqs(l,r:integer);vari,j,m,t:integer;begini:=l;j:=r;m:=a[(l+r)div2];repeatwhilea[i]mdodec(j);ifi<=jthenbegint:=a[i];a[i]:=a[j];a[j]:=t;inc(i);dec(j);end;untili>j;ifl0dobeginwrite(i:6);a[i]:=a[i]-1;end;二、排序算法的应用例1：明明的随机数【问题描述】明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。输入：第1行为1个正整数，表示所生成的随机数的个数：N；第2行有N个用空格隔开的...
