c语言排序算法
-
2023年3月16日发(作者：考研英语新题型)《高级语言程序设计》
课程设计报告
题目：排序算法
专业：
班级：
姓名：
指导教师：
成绩：
计算机与信息工程系
2015年3月26日
学号
2014-2015学年第2学期
目录
引言...............................................................1
需求分析............................................................1
第一章程序内容及要求...............................................1
1.1冒泡排序...................................................1
1.2选择排序...................................................2
1.3插入排序...................................................3
第二章概要设计.....................................................4
2.1冒泡排序.....................................................4
2.2选择排序.....................................................5
2.3插入排序.....................................................6
第三章程序的比较及其应用...........................................7
3.1时间复杂度...................................................7
3.2空间复杂度...................................................7
3.3稳定程度.....................................................7
3.4应用及其改进.................................................8
第四章程序设计结果.................................................9
附录................................................................9
参考文献...........................................................13
计算机与信息工程系《高级语言程序设计》课程设计报告
1
引言
伴随着社会的发展，数据也变得越来越庞大。如何将庞大的数据进行很好
的排序，使用户更加方便的查找资料，成了一件越来越重要的问题。对于程序员
来说，这将是一个挑战。
经常查找资料的朋友都会知道，面对海量的资料，如果其查找资料没有进
行排序，那么其查找资料将会是一家非常痛苦的事情。针对这一问题，我们自此
通过一个课程设计来解决它。
理论上排序算法有很多种，不过本课程设计只涉及到三种算法。这三种算
法包括：冒泡排序，选择排序，直接插入排序。
本课程设计通过对这三种算法的运行情况进行对比，选择最优秀的算法出
来。希望通过我的努力能解决一些问题，带来一些方便。
需求分析
本课程题目是排序算法的实现，由于各方面的原因，本科程设计一共需要
设计三种排序算法。这三种算法包括：冒泡排序，选择排序，直接插入排序。三
种排序算法各有独到之处，因此我们要通过各种调试分析来比较其优劣长短。
由于使用的调试软件及操作系统不一样。因此个别程序在不同的软件上可
能会报错。
本课程软件运行的的操作系统为Windows764位操作系统。所使用的软件
为MicrosoftVisualC++6.0以及TurboC2.0
第一章程序内容及要求
1.1冒泡排序
冒泡排序（BubbleSort，台湾译为：泡沫排序或气泡排序）是一种简单
的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺
序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，
也就是说该数列已经排序完成。这个算法的名字由来是因为越大的元素会经由交
换慢慢“浮”到数列的顶端，故名。
计算机与信息工程系《高级语言程序设计》课程设计报告
2
冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数
放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放
前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继
续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的
数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第
3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一
直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒
数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此
下去，重复以上过程，直至最终完成排序。用二重循环实现，外循环变量设为i，
内循环变量设为j。假如有10个数需要进行排序，则外循环重复9次，内循环
依次重复9，8，...，1次。每次进行比较的两个元素都是与内循环j有关的，
它们可以分别用a[j]和a[j+1]标识，i的值依次为1,2,...,9，对于每一个i,j
的值依次为1,2,...10-i。冒泡排序算法的性能
1.2选择排序
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放
在已排好序的数列的最后，直到全部待排序的数据元素排完。选择排序是不稳
定的排序方法。
基本思想:
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：
①初始状态：无序区为R[1..n]，有序区为空。
②第1趟排序在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区
的第1个记录R[1]交换，
使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1
个的新无序区。„„③
第i趟排序第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(1
≤i≤n-1)。
该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个
记录R交换，
使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新
计算机与信息工程系《高级语言程序设计》课程设计报告
3
无序区。
这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
选择排序法的第一层循环从起始元素开始选到倒数第二个元素,主要是在每次进
入的第二层循环之前,
将外层循环的下标赋值给临时变量,接下来的第二层循环中,如果发现有比这个
最小位置处的元素更小的
元素,则将那个更小的元素的下标赋给临时变量,最后,在二层循环退出后,如果
临时变量改变,则说明,
有比当前外层循环位置更小的元素,需要将这两个元素交换
1.3插入排序
有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一
个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法
--插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数
据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，
时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部
分:第一部分包含了这个数组的所有元素，但将最后一个元素除外(让数组多一个
空间才有插入的位置)，而第二部分就只包含这一个元素(即待插入元素)。在第
一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。插入排序
的基本思想是:每步将一个待排序的纪录，按其关键码值的大小插入前面已经排
序的文件中适当位置上，直到全部插入完为止。
⒈从有序数列和无序数列{a2,a3，„，an}开始进行排序；
⒉处理第i个元素时（i=2,3，„，n），数列{a1,a2，„，ai-1}是已有序
的，而数列{ai,ai+1，„，an}是无序的。用ai与ai-1，ai-2，„，a1进行比
较，找出合适的位置将ai插入；
⒊重复第二步，共进行n-i次插入处理，数列全部有序。
计算机与信息工程系《高级语言程序设计》课程设计报告
4
第二章概要设计
2.1冒泡排序
在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对
相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每
当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
for(i=0;i<10;i++)第一轮循环，输入十个数据。
scanf(“%d”,&a[i]);
printf(“n”);
for(j=0;j<9;j++)挨个判断输入的书的大小，第二轮循环
for(i=0;i<9-j;i++)
if(a[i]>a[i+1]
{
t=a[i];进行数的调换，把大的数据调到后面。
计算机与信息工程系《高级语言程序设计》课程设计报告
5
a[i]=a[i+1];
a[i+1]=t;
2.2选择排序
简单选择排序，每趟循环只能确定一个元素排序后的定位。我们可以考
虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排
序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即
可。
voidselect_sort(inta[],intn)//n为数组a的元素个数
{//进行N-1轮选择
for(inti=0;i {intmin_index=i; //找出第i小的数所在的位置 for(intj=i+1;j {if(a[j] 计算机与信息工程系《高级语言程序设计》课程设计报告 6 {min_index=j; } } //将第i小的数，放在第i个位置；如果刚好，就不用交换 if(i!=min_index) { inttemp=a[i]; a[i]=a[min_index]; a[min_index]=temp; 2.3插入排序 将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1 的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2 个记录逐个进行插入，直至整个序列有序为止。 { inttemp; for(inti=1;i { 计算机与信息工程系《高级语言程序设计》课程设计报告 7 temp=arr[i];//记录当前的元素 intj=i-1; while(j>=0&&temp 经排序好的序列元素进行挨个比较 { arr[j+1]=arr[j];//已经排序好的序列整体向后移 动 --j; } arr[j+1]=temp;//插入当前的元素 第三章程序的比较及其应用 3.1时间复杂度 冒泡排序算法的最差时间复杂度为O(n2)，平均时间复杂度为O(n2)。选 择排序算法的最差时间复杂度为O(n2)，平均时间复杂度为O(n2)。插入排序算法 的最差时间复杂度为O(n2)，平均时间复杂度为O(n2)。冒泡排序和插入排序时间 复杂度最好的情况下是O(n)，而选择排序时间复杂度最好的情况下是O(n2)。从 时间复杂度比较来看。选择排序的时间复杂度在以下情况下是没有冒泡排序和插 入排序的好。 3.2空间复杂度 冒泡排序，选择排序，以及插入排序是空间复杂度都是O(1)。从空间 复杂度来看，三者也没有什么可以区分开来的。并不能直观的看出优劣。 3.3稳定程度 冒泡排序和插入排序的稳定程度都是比较稳定的，只有选择排序是不稳 定的。那么综合上面的比较来看，选择排序是最不好的，而冒泡排序以及插入排 序是比较好的。冒泡排序是最慢的，但是也是最容易懂得。插入排序是比较快的， 但是对于自身的能力有一定的要求。当然，这只是相对而言。 计算机与信息工程系《高级语言程序设计》课程设计报告 8 3.4应用及其改进 三种排序算法都可以应用于一些简单排列数据的程序。也可以作为C 语言初学者的练手的课题。对于我们学习C语言也是一个不小的帮助。同时可以 加深我们对于循环和数组的理解及其应用。同时我们可以对冒泡排序进行一点点 的改进，使其更加的完善。 冒泡算法的改进，当排序的数据比较多时排序的时间会明显延长。改进 方法：快速排序：具体做法：任意选取某一记录（通常取第一个记录），比较其 关键字与所有记录的关键字，并将关键字比它小的记录全部放在它的前面，将比 它大的记录均存放在它的后面，这样，经过一次排序之后，可将所有记录以该记 录所在的分界点分为两部分，然后分别对这两部分进行快速排序，直至排序完。 在冒泡排序中，一趟扫描有可能无数据交换，也有可能有一次或多次数据交换， 在传统的冒泡排序算法及近年来的一些改进的算法中，只记录一趟扫描有无数据 交换的信息，对数据交换发生的位置信息则不予处理。为了充分利用这一信息， 可以在一趟全局扫描中，对每一反序数据对进行局部冒泡排序处理，称之为局部 冒泡排序。局部冒泡排序与冒泡排序算法具有相同的时间复杂度，并且在正序和 逆序的情况下，所需的关键字的比较次数和移动次数完全相同。由于局部冒泡排 序和冒泡排序的数据移动次数总是相同的，而局部冒泡排序所需关键字的比较次 数常少于冒泡排序，这意味着局部冒泡排序很可能在平均比较次数上对冒泡排序 有所改进，当比较次数较少的优点不足以抵消其程序复杂度所带来的额外开销， 而当数据量较大时，局部冒泡排序的时间性能则明显优于冒泡排序。 计算机与信息工程系《高级语言程序设计》课程设计报告 9 第四章程序设计结果 插入排序算法的结果 选择排序算法的结果 冒泡排序算法的结果 附录 冒泡排序： #include voidmain() { inta[10]; 计算机与信息工程系《高级语言程序设计》课程设计报告 10 Inti,j,t; printf(“input10numbers:n”); for(i=0;i<10;i++) scanf(“%d”,&a[i]); printf(“n”); for(j=0;j<9;j++) for(i=0;i<9-j;i++) if(a[i]>a[i+1] { t=a[i]; a[i]=a[i+1]; a[i+1]=t; } printf(“thesortednumbers:n”); printf(“%d”,a[i]); printf(“n”); } 选择排序： #include #include #defineN8 voidselect_sort(inta[],intn); //选择排序实现 voidselect_sort(inta[],intn)//n为数组a的元素个数 { //进行N-1轮选择 for(inti=0;i { 计算机与信息工程系《高级语言程序设计》课程设计报告 11 intmin_index=i; //找出第i小的数所在的位置 for(intj=i+1;j { if(a[j] { min_index=j; } } //将第i小的数，放在第i个位置；如果刚好，就不用交换 if(i!=min_index) { inttemp=a[i]; a[i]=a[min_index]; a[min_index]=temp; } } } intmain() { intnum[N]={89,38,11,78,96,44,19,25}; select_sort(num,N); for(inti=0;i printf("%d",num[i]); printf("n"); system("pause"); return0; } 计算机与信息工程系《高级语言程序设计》课程设计报告 12 插入排序： #include usingnamespacestd; voidInsertSort(intarr[],intlength) { inttemp; for(inti=1;i { temp=arr[i];//记录当前的元素 intj=i-1; while(j>=0&&temp 序好的序列元素进行挨个比较 { arr[j+1]=arr[j];//已经排序好的序列整体向后移动 --j; } arr[j+1]=temp;//插入当前的元素 } } intmain() { intarr[10]={9,2,8,2,3,2,4,10,34,5}; InsertSort(arr,10); for(inti=0;i<10;++i) { cout< } cout< return0; 计算机与信息工程系《高级语言程序设计》课程设计报告 13 } 参考文献 [1]谭浩强.数组C语言程序设计（第三版）清华大学出版社 [2]谭浩强.《C语言设计解题与上机指导（第三版）》.清华大学出版社 [3]李大友著.《C语言程序设计》.清华大学出版社