冒泡排序和选择排序的效率问题26
发布网友
发布时间：2023-09-29 22:48
共2个回答
热心网友
时间：2024-12-12 18:38
追答应该是吧，冒泡排序遇到一个需要交换的就交换一次。
遇到比当前最大值(降序)大的,或比当前最小值小的升序就交换一次。
选择每次选一个最大值(降序)或最小值交换(升序)。
你这个明显是这么做的!
不过冒泡的改进算法效率也不低。就是记录交换次数的方法。
选择排序由于每次只交换一个，比简单的冒泡效率高。
但是你这个效率也不是很好！
好一点的选择排序，
只需要记录最大值(降序)或最小值交换(升序)的位置，
就行了,不要赋值这一步了。
另外C数组下标，都是从0开始计数的；
所以如无特殊需要。一般从0开始！
你这里11个字符只有1~10 是有用数据
第0个字符没有用到!
只有某些比较原始的,插入排序算法，才是从1开始的；0留出来另有用途(是叫哨兵吧!)。
由于你这里是字符数组,
所以算法上最好的,不一定就是最好的!
从算法来说,下面这样的小小改动是比较好的!
for(i=1;i<11;i++)//控制被比较数滑动, .......... 一共进行10轮比较。
{
k=i; //.......k就是最大值的下标，先假设最大值在i；
for(j=i+1;j<11;j++) //控制比较.............比较 10-i次;
if(str[k]<str[j])k=j; //改进的选择排序算法。这个是降序,选最大的,只有遇到更大的,才改变k!
if(k!=i) //i是最大值时不交换；在这里使用，提高不了多少效率，只是从算法上说更好些！
{ t=str[i];str[i]=str[k];str[k]=t; }//最大值从k,交换到i;这一步没什么花样!
}
更好的选择排序，是希尔排序（shellsort）或者叫歇尔排序,
最好的希尔排序,时间复杂度O（N^(4/3))；
这个就看数据结构和算法方面的书吧！
少了 k=i;//这一步，可是内循环里 多了这么多代码 str[i]<str[j]?t=str[i],k=i:t=str[j],k=j;
虽然用了？运算符可是，至少需要两个赋值操作。
这里数据尺寸较小不算什么，一旦数组中的数据尺寸较大就很不划算了！
k=i 就不同了，不管数据如何，只是一个整数赋值操作而已。
最好的内部排序算法好像是快速排序吧!
最好的外部排序算法是归并排序!
热心网友
时间：2024-12-12 18:38
经典排序之冒泡排序
