分享
 
 
 

C语言常用的三种排序方法总结与探讨

王朝c/c++·作者佚名  2008-06-01
窄屏简体版  字體: |||超大  

C语言常用的三种排序方法总结与探讨

排序是程序设计中非常重要的内容,它的功能是将一组无序的的数据,排列成有序的数据序列,经过排列后的数据,要么是从大到小排列,要么是从小到大排列。一般也只有这两种情况。

例如我们统计班级学生的成绩,那么一般是按照学号来进行统计,原来成绩是无序排列的,这样的话非常不适合于我们对成绩的查询,那么一般我们进行成绩查询之前,先进行排序,如按照高分到低分的排序,这样可以很快地查出本班的最高分和最低分,和成绩比较靠前或靠后的学生。

排序有很多种方法,常用的有三种:冒泡排序、选择排序、插入排序等,下面我们就对这三种方法做一下分析和比较,以便大家能够更好的理解和应用。

一、冒泡排序

1、冒泡排序的基本思想:对于n个数进行排序(现假定是从大到小排序,以下均按此进行),将相邻两个数依次比较,将大数调在前头:也就是说第一个数和第二个数比较,大数放前,小数放后,第二个和第三个进行比较,大数放前、小数放后,然后依次类推。。。经过第一轮比较以后,我们找到一个最小数在最下面(沉底)。然后进行下一轮比较,最后一个数就不用再参加比较了,所以本轮就可以少比较一次。

很显然,需要用双重循环来设计这个问题,外层循环控制进行的轮数,内层循环控制每轮比较的次数,那么到底需要多少轮、每轮需要多少次,我们通过一个实例看一下:

2、排序过程举例:

外循环

1轮

2轮

3轮

4轮

内循环

5个数比较4次

4个数比较3次

3个数比较2次

2个数比较1次

7

5

8

6

9

1次

2次

3次

4次

1次

2次

3次

1 次

2次

1次

7

5

8

6

9

7

8

5

6

9

7

8

6

5

9

7

8

6

9

5

8

7

6

9

5

8

7

6

9

5

8

7

9

6

5

8

7

9

6

5

8

9

7

6

5

9

8

7

6

5

最小的数5沉底,其余4个数继续比较

次小数6沉底,其余3个数

7沉底,其余2个数比较

最后两个数一次比较

那么通过这个排序过程,我们了解了怎样去进行排序,那么到底谁是气泡呢,我们可以从中找出答案,那么从大到小进行排序,较大的一些数就是气泡。随着排序的进行,气泡逐步上升。

从这个排序过种中,还可以看出,5个数实际经过4轮就可以了,实践证实,n个数最多需要n-1轮排序就可以了。

3、冒泡排序的程序如下:

for(i=0;i<10;i++)

for(j=0;j<10-i;j++)

if(a[j]<a[j+1])

在此程序段的上面加上输入部分和在程序段加上排序后的输出。

程序的改进:

4、算法的改进:

从上面的排序的过程可以看出,假如一个已经排好序的一组数或者经过很少的轮数就可以排完这些数,但是循环还是要继续进行,这样设计出的程序浪费了大量的时间,所以对一这个算法我们可以重新设计。

经过修改后的程如下:

for(i=0;i<10&&!swap;i++)

{

swap=1;

for(j=0;j<10-I;j++)

if(a[j]<a[j+1])

}

二、选择排序

1、排序的基本思想:先从第一个数开始起,用第一个数和其它的数进行比较,假如比第一个数大就交换位置,否则不进行交换,这样经过第一轮比较我们就能够找出最大值放在第一位置,然后从第二个位置起再找次大数,这样依次下去,就可以进行整个数的排序,实践证实,n个数最多需要n-1轮排序就可以了。

2、排序过程举例:

外循环

1轮

2轮

3轮

4轮

内循环

5个数比较4次

4个数比较3次

3个数比较2次

2个数比较1次

7

5

8

6

9

1次

2次

3次

4次

1次

2次

3次

1 次

2次

1次

7

5

8

6

9

8

5

7

6

9

8

5

7

6

9

9

5

7

6

8

9

7

5

6

8

9

7

5

6

8

9

8

5

6

7

9

8

6

5

7

9

8

7

6

5

9

8

7

6

5

最大的数9找到,其余4个数找次大数

次大数8找到,其余3个数找

7找到,其余2个数找

最后两个数一次比较

选择排序较冒泡轻易理解,程序编写也要相对轻易一些。

for(i=0;i<10;i++)

for(j=i+1;j<10;j++)

if(a[i]<a[j])

对于选择排序,我们也可以看到一个问题,如第一轮排序中,我们要找的是9才是最大值,所以其它的交换完全没有必要进行,其它各轮都存在这样的情况,所以我们可以想办法取消这种情况,也就是说我们真正找到的最大值的位置后再进行交换。

for(i=0;i<10;i++)

{ p=i;

for(j=i+1;j<10;j++)

if(a[p]<a[j])

p=j;

if(p!=i)

}

这样算法经过改进以后就较好地解决了这个问题。

三、插入排序

1、插入排序基本思想:(假定从大到小排序)依次从后面拿一个数和前面已经排好序的数进行比较,比较的过程是从已经排好序的数中最后一个数开始比较,假如比这个数,继续往前面比较,直到找到比它大的数,然后就放在它的后面,假如一直没有找到,肯定这个数已经比较到了第一个数,那就放到第一个数的前面。

那么一般情况下,对于采用插入排序法去排序的一组数,可以先选 取第一个数做为已经排好序的一组数。然后把第二个放到正确位置

2、程序的编写如下:

for(i=1;i<10;i++)//i从0开始或者1开始都可以。其它不变。

for(j=i;j>0;j--)

if(a[j]<a[j-1])

对于这个程序也有需要修该的地方,以上程序的排序实际上也是基于交换思想进行排序,也可以进行真正意义上的排序,即:先把待排序的数取出来,然后找出应该插入的位置,找到后,将待插入位置后的数据统统后移,原待排数据已经取出放于临时变量中。然后把这个数据插入到正确的空余位置就可以了。

那么对于基于交换的插入排序,没有找到位置之前,也进行了交换,所以我们也可以进行程序的改进。那么此程序的改进,肯定不能进行减少交换次数,因为我们知道假如到找到位置再进行交换,那么肯定已经找乱了原来的排序结果,所以只能是找位置,腾位置、放元素这几道手续。

main()

{

int i,j,t,a[]=;

for(i=1;i<10;i++)

{t=a[i];

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有