c语言程序的设计(排序算法)
《高级语言程序设计》
课程设计报告
题目：
排序算法 专业： 班级： 姓名： 指导教师：
成绩：
计算机与信息工程系
2015年3月26日
2014-2015学年 第2学期
目录
引言 (1)
需求分析 (1)
第一章程序内容及要求 (1)
1.1 冒泡排序 (1)
1.2 选择排序 (2)
1.3 插入排序 (4)
第二章概要设计 (4)
2.1冒泡排序 (4)
2.2选择排序 (6)
2.3插入排序 (7)
第三章程序的比较及其应用 (9)
3.1时间复杂度 (9)
3.2空间复杂度 (9)
3.3稳定程度 (9)
3.4应用及其改进 (9)
第四章程序设计结果 (11)
附录 (12)
参考文献 (16)
引言
伴随着社会的发展，数据也变得越来越庞大。如何将庞大的数据进行很好的排序，使用户更加方便的查找资料，成了一件越来越重要的问题。对于程序员来说，这将是一个挑战。
经常查找资料的朋友都会知道，面对海量的资料，如果其查找资料没有进行排序，那么其查找资料将会是一家非常痛苦的事情。针对这一问题，我们自此通过一个课程设计来解决它。
理论上排序算法有很多种，不过本课程设计只涉及到三种算法。这三种算法包括：冒泡排序，选择排序，直接插入排序。
本课程设计通过对这三种算法的运行情况进行对比，选择最优秀的算法出来。希望通过我的努力能解决一些问题，带来一些方便。
需求分析
本课程题目是排序算法的实现，由于各方面的原因，本科程设计一共需要设计三种排序算法。这三种算法包括：冒泡排序，选择排序，直接插入排序。三种排序算法各有独到之处，因此我们要通过各种调试分析来比较其优劣长短。
由于使用的调试软件及操作系统不一样。因此个别程序在不同的软件上可能会报错。
本课程软件运行的的操作系统为Windows7 64位操作系统。所使用的软件为Microsoft Visual C++6.0以及Turbo C2.0
第一章程序内容及要求
1.1 冒泡排序
冒泡排序（Bubble Sort，台湾译为：泡沫排序或气泡排序）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。
冒泡排序（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个的新无序区。
这样，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，a i-2，…，a1进行比较，找出合适的位置将ai插入；
⒊重复第二步，共进行n-i次插入处理，数列全部有序。
第二章概要设计
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]; 进行数的调换，把大的数据调到后面。
a[i]=a[i+1];
a[i+1]=t;
2.2选择排序
简单选择排序，每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可。
void select_sort(int a[],int n)//n为数组a的元素个数
{//进行N-1轮选择
for(int i=0; i {int min_index = i; //找出第i小的数所在的位置 for(int j=i+1; j {if(a[j] < a[min_index]) {min_index = j; } } //将第i小的数，放在第i个位置；如果刚好，就不用交换 if( i != min_index) { int temp = a[i]; a[i] = a[min_index]; a[min_index] = temp; 2.3插入排序 将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2 个记录逐个进行插入，直至整个序列有序为止。 { int temp; for (int i = 1; i < length; ++i) // 从数组中的第二个元素开始 { temp = arr[i]; // 记录当前的元素 int j = i - 1; while (j >= 0 && temp < arr[j]) // 将当前元素与之前的已经排序好的序列元素进行挨个比较 { 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稳定程度 冒泡排序和插入排序的稳定程度都是比较稳定的，只有选择排序是不稳定的。那么综合上面的比较来看，选择排序是最不好的，而冒泡排序以及插入排序是比较好的。冒泡排序是最慢的，但是也是最容易懂得。插入排序是比较快的，但是对于自身的能力有一定的要求。当然，这只是相对而言。 3.4应用及其改进 三种排序算法都可以应用于一些简单排列数据的程序。也可以作为C 语言初学者的练手的课题。对于我们学习C语言也是一个不小的帮助。同时可 以加深我们对于循环和数组的理解及其应用。同时我们可以对冒泡排序进行一点点的改进，使其更加的完善。 冒泡算法的改进，当排序的数据比较多时排序的时间会明显延长。改进方法：快速排序：具体做法：任意选取某一记录（通常取第一个记录），比较其关键字与所有记录的关键字，并将关键字比它小的记录全部放在它的前面，将比它大的记录均存放在它的后面，这样，经过一次排序之后，可将所有记录以该记录所在的分界点分为两部分，然后分别对这两部分进行快速排序，直至排序完。在冒泡排序中，一趟扫描有可能无数据交换，也有可能有一次或多次数据交换，在传统的冒泡排序算法及近年来的一些改进的算法中，只记录一趟扫描有无数据交换的信息，对数据交换发生的位置信息则不予处理。为了充分利用这一信息，可以在一趟全局扫描中，对每一反序数据对进行局部冒泡排序处理，称之为局部冒泡排序。局部冒泡排序与冒泡排序算法具有相同的时间复杂度，并且在正序和逆序的情况下，所需的关键字的比较次数和移动次数完全相同。由于局部冒泡排序和冒泡排序的数据移动次数总是相同的，而局部冒泡排序所需关键字的比较次数常少于冒泡排序，这意味着局部冒泡排序很可能在平均比较次数上对冒泡排序有所改进，当比较次数较少的优点不足以抵消其程序复杂度所带来的额外开销，而当数据量较大时，局部冒泡排序的时间性能则明显优于冒泡排序。 第四章程序设计结果插入排序算法的结果 选择排序算法的结果 冒泡排序算法的结果 附录 冒泡排序： #include void main() { int a[10]; Int i,j,t; printf(“input 10 numbers :\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(“the sorted numbers :\n”); printf(“%d”,a[i]); printf(“\n”); } 选择排序： #include #include #define N 8 void select_sort(int a[],int n); //选择排序实现 void select_sort(int a[],int n)//n为数组a的元素个数{ //进行N-1轮选择 for(int i=0; i { int min_index = i; //找出第i小的数所在的位置 for(int j=i+1; j { if(a[j] < a[min_index]) { min_index = j; } } //将第i小的数，放在第i个位置；如果刚好，就不用交换 if( i != min_index) { int temp = a[i]; a[i] = a[min_index]; a[min_index] = temp; } } } int main() { int num[N] = {89, 38, 11, 78, 96, 44, 19, 25}; select_sort(num, N); for(int i=0; i printf("%d ", num[i]); printf("\n"); system("pause"); return 0; } 插入排序： #include using namespace std; void InsertSort(int arr[], int length) { int temp; for (int i = 1; i < length; ++i) // 从数组中的第二个元素开始 { temp = arr[i]; // 记录当前的元素 int j = i - 1; while (j >= 0 && temp < arr[j]) // 将当前元素与之前的已经排序好的序列元素进行挨个比较 { arr[j + 1] = arr[j]; // 已经排序好的序列整体向后移动 --j; } arr[j + 1] = temp; // 插入当前的元素 } } int main() { int arr[10] = {9, 2, 8, 2, 3, 2, 4, 10, 34, 5}; InsertSort(arr, 10); for (int i = 0; i < 10; ++i) { cout< } cout< return 0; } 参考文献 [1]谭浩强.数组C语言程序设计（第三版）清华大学出版社 [2]谭浩强.《C语言设计解题与上机指导（第三版）》.清华大学出版社 [3]李大友著.《C语言程序设计》.清华大学出版社