排序编程方法

《排序编程方法》由会员分享，可在线阅读，更多相关《排序编程方法（7页珍藏版）》请在金锄头文库上搜索。

1、排序是程序设计中非常重要的内容，它的功能是将一组无序的的数据，排列成有序的数据序 列，经过排列后的数据，要么是从大到小排列，要么是从小到大排列。一般也只有这两种情 况。例如我们统计班级学生的成绩，那么一般是按照学号来进行统计，原来成绩是无序排列 的，这样的话非常不适合于我们对成绩的查询，那么一般我们进行成绩查询之前，先进行排 序，如按照高分到低分的排序，这样可以很快地查出本班的最高分和最低分，和成绩比较靠 前或靠后的学生。排序有很多种方法，常用的有三种：冒泡排序、选择排序、插入排序等，下面我们就对这三 种方法做一下分析和比较，以便大家能够更好的理解和应用。一、冒泡排序1、冒泡排序的基本思想：对

2、于n个数进行排序（现假定是从大到小排序，以下均按此 进行），将相邻两个数依次比较，将大数调在前头：也就是说第一个数和第二个数比较，大 数放前，小数放后，第二个和第三个进行比较，大数放前、小数放后，然后依次类推。 经过第一轮比较以后，我们找到一个最小数在最下面（沉底）。然后进行下一轮比较，最后 一个数就不用再参加比较了，所以本轮就可以少比较一次。很显然，需要用双重循环来设计这个问题，外层循环控制进行的轮数，内层循环控制每轮比 较的次数，那么到底需要多少轮、每轮需要多少次，我们通过一个实例看一下：2、排序过程举例：外循环 1 轮 2 轮 3轮 4 轮4 个 3 个数数5 个数比内循环比 比 2 个

3、数比较 1 次较4次较3较2次次75869758691次 2次 3次4 次1次2次3 次1 次次次7778888877566666599999555897886775999866755657 沉底，5 沉底，次小数 6 沉底，其余3 个 其余2其余4个数个数比最小的数数继续比最后两个数一次比较较那么通过这个排序过程，我们了解了怎样去进行排序，那么到底谁是气泡呢，我们可以从中 找出答案，那么从大到小进行排序，较大的一些数就是气泡。随着排序的进行，气泡逐步上 升。从这个排序过种中，还可以看出，5个数实际经过4轮就可以了，实践证明，n个数最 多需要n-1轮排序就可以了。3、冒泡排序的程序如下：for

4、(i=0;i10;i+)for(j=0;j10i;j+)if(ajaj+l)t=aj;aj=aj+l;aj+l= t;在此程序段的上面加上输入部分和在程序段加上排序后的输出。程序的改进：4、算法的改进：从上面的排序的过程可以看出，如果一个已经排好序的一组数或者经过很少的轮数就可以排 完这些数，但是循环还是要继续进行，这样设计出的程序浪费了大量的时间，所以对一这个 算法我们可以重新设计。经过修改后的程如下：for(i=0;i10&!swap;i+)swap=1;for(j=0;j10I;j+)if(ajaj+l)t=aj;aj=aj+l;aj+l= t;swap=O;二、选择排序1、排序的基本思

5、想：先从第一个数开始起，用第一个数和其它的数进行比较，如果比 第一个数大就交换位置，否则不进行交换，这样经过第一轮比较我们就能够找出最大值放在 第一位置，然后从第二个位置起再找次大数，这样依次下去，就可以进行整个数的排序，实 践证明，n个数最多需要n-1轮排序就可以了。2、排序过程举例：81 次 2 次 3 次64次1次 2次 3 次 1 次 2次1次外循环1轮2轮3轮4轮内循5 个数比4 个数比3 个数比2 个数比较 1 次环较4次较3次较2次最大的数 9 找到，其余 4 个数找次大数其余3 个数找个数找 较选择排序较冒泡容易理解，程序编写也要相对容易一些。for(i=0;i10;i+)fo

6、r(j=i+l;j10;j+)if(aiaj)t=ai;ai=aj;aj= t;对于选择排序，我们也可以看到一个问题，如第一轮排序中，我们要找的是9才是最大值, 所以其它的交换完全没有必要进行，其它各轮都存在这样的情况，所以我们可以想办法取消 这种情况，也就是说我们真正找到的最大值的位置后再进行交换。for(i=0;i10;i+) p=i；for(j=i+l;j10;j+)if(apaj)p=j；辻(p!=i)t=ai;ai=aj;aj= t;这样算法经过改进以后就较好地解决了这个问题。三、插入排序1、插入排序基本思想：(假定从大到小排序)依次从后面拿一个数和前面已经排好序的数 进行比较，比较

7、的过程是从已经排好序的数中最后一个数开始比较，如果比这个数，继续往前面比较，直到找到比它大的数，然后就放在它的后面，如果一直没有找到，肯定这个数已 经比较到了第一个数，那就放到第一个数的前面。那么一般情况下，对于采用插入排序法去排序的一组数，可以先选取第一个数做为已经排 好序的一组数。然后把第二个放到正确位置2、程序的编写如下：for(i=l;i10;i+)/i从0开始或者1开始都可以。其它不变。for(j=i;j0;j-)if(ajaj-l)t=aj;aj=aj-l;aj-l= t;对于这个程序也有需要修该的地方，以上程序的排序实际上也是基于交换思想进行排序，也 可以进行真正意义上的排序，即

8、:先把待排序的数取出来，然后找出应该插入的位置，找到 后，将待插入位置后的数据统统后移，原待排数据已经取出放于临时变量中。然后把这个数 据插入到正确的空余位置就可以了。那么对于基于交换的插入排序，没有找到位置之前，也进行了交换，所以我们也可以进行程 序的改进。那么此程序的改进，肯定不能进行减少交换次数，因为我们知道如果到找到位置 再进行交换，那么肯定已经找乱了原来的排序结果，所以只能是找位置，腾位置、放元素这 几道手续。main()int i,j, t,a二12,11,2,3,6,67,89,0,1,3;for(i=l;i10;i+)t=ai;j=i-1；while(j=O&tai)aj+l=aj;j-；aj+1=t;for(i=0;i10;i+)pri ntf (%d ,ai);printf(n)；以上是对几种排序方法进行了探讨，关于排序问题，是程序设计中的一项非常重要的内容,所以在数据结构与算法中作为一项重要的内容做了深入的讲解，我们这在这里只做简单 的探讨，以备C语言的初学者或正在学习C语言编程的爱好者使用。