啊哈磊_编程从这里起步
标题:
改进的冒泡排序
[打印本页]
作者:
rosynirvana
时间:
2014-10-11 02:09
标题:
改进的冒泡排序
#include <stdio.h>
void swap(int*, int*);
void bubble_sort(int*, int);
int main()
{
int data[5] = {3, 7, 4, 1, 9};
int i;
bubble_sort(data, 5);
for(i=0; i!=5; ++i)
printf("%d ", data[i]);
return 0;
}
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void bubble_sort(int* ary, int length)
{
int i, j;
int changed;
for(i=0; i<length-1 && changed; ++i){
changed = 0;
for(j=0; j<length-i; ++j)
if(ary[j] > ary[j+1]){
changed = 1;
swap(&ary[j], &ary[j+1]);
}
}
}
复制代码
一句话简介:用一个变量(changed)来记录在某一轮比较中有没有发生交换,如果没有,那么排序已经完成
很明显,如果一个数组的a[1] < a[2] a[2] < a[3] ....都成立,那么这个数组就是排好序的
如果要用冒泡排序,强烈建议加上这个判断,否则冒泡排序就要和选择排序做同样次数的比较,而且由于选择排序少的缘故,必然是选择排序比较好。
另外,选择排序要比冒泡排序稍微好写一点
后面的实际例子也是如此,人名是个字符串,一般占的内存较多,让两个占很大内存空间的结构体进行交换是比较低效的事情。
有两种解决方法,第一是给每个人编号,然后实际排序的结构体中记录人的编号和分数,例如
编号 人名
0 huhu
1 haha
2 xixi
3 hengheng
4 gaoshou
然后结构体中的数据是
0 5 (对应huhu 5)
1 3 (对应haha 3)
2 5
3 2
4 8
这样保证排序进行交换的时候只交换8个字节的数据,然后输出的时候再根据编号输出人名
另外一种方法是结构体中保存分数和姓名字符串的指针,这样保证每次交换的时候只有8字节或12字节(64位系统)
可以试着自己研究一下
作者:
王萍萍
时间:
2015-3-4 13:20
经常把选择排序当成冒泡来写,当必须写冒泡时,写不出来了
作者:
福华
时间:
2015-7-10 19:25
给每个人编号来提高交换效率,比较简单实用
作者:
超神级
时间:
2015-11-20 20:25
{:soso_e121:}
欢迎光临 啊哈磊_编程从这里起步 (https://bbs.codeaha.com/)
Powered by Discuz! X3.2