冒泡 选择 插入排序算法总结
时间:6年前 阅读:4879
概述:
由于排序非常重要而且可能非常耗时,所以它已经成为一个计算机科学中广泛研究的课题,
而且人们的确已经研究出一些非常成熟的方法。在这篇文中将看到三个简单排序的算法:
冒泡,选择,插入排序,还有另外两种高级排序算法,希尔和快速排序。插入排序比较重要,
它比冒泡和选择排序有时更有效率,而且对于小规模和基本有序的文件,插入排序算法能比
快速排序算法更为有效。
这篇文中阐述三种简单排序算法,下一篇文中阐述高级排序算法。
从三个角度来阐述算法:代码,执行效率(大O表示法)以及不变性。
不变性:在许多算法中,有些条件在算法执行时是不变的,这些条件被称为不变性。认识
不变性对理解算法是有用的。在一定的情况下它们对调试也有用;可以反复检查不变性是否
为真,如果不是的话就标记出错。
阐述语言:Java
冒泡排序
冒泡排序算法运行起来非常慢,但在概念上它是排序算法中最简单的,因此冒泡
排序算法在刚开始研究排序技术时是一个非常好的算法。
代码:
//冒泡排序
public void bubbleSort()
{
int out,in;
for(out = nElms - 1;out > 0;out --)
for(in = 0;in < out; in++)
if(array[in] > array[in + 1])
swap(in,in+1);
}
不变性:它的不变性是指out右边的所有数据项有序,在算法的整个运行过程中这个条件始终为真。
效率:
比较次数:数组中有N个数据项,第一趟排序中有N-1次比较,第二趟有N-2次比较,如此类推,
最后一趟需要1次比较
故比较次数为:(N-1)+ (N-2) + ... + 1 = N(N-1)/2
交换次数为 0 - N(N-1)/2,两个极端情况,完全有序和完全逆序时交换次数分别为0和N(N-1)/2。,
故平均比较次数为:N(N-1)/4
大O表示法要忽略常数,故BubbleSort的时间复杂度为0(N²)
ps:无论何时,只要看到一个循环嵌套在另一个循环里,就可以怀疑这个算法的运行时间为
0(N²)时间级别。
选择排序
算法描述:
每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全
部待排序的数据元素排完。
与冒泡比较:
交换的复杂度降为0(N),不幸的是比较复杂度仍然保持为0(N²)
代码:
//选择排序
public void selectSort()
{
int out,in,min;
for(out = 0;out < nElms - 1;out ++)
{
min = out;
for(in = out + 1;in < nElms;in ++)
if(array[in] < array[min])
min = in;
swap(min,out);
}
}
不变性:在算法执行过程中,下标小于或等于out的位置的数据项总是有序的。
效率:
比较次数为:N(N-1)/2
交换次数为:N/2
仍然维持在0(N²)。但是如果交换的时间级比比较的时间级大得多时,选择排序实际上是相当
快的。
ps:综上,实际编程中,能用选择排序的时候就不要用冒泡排序,冒泡排序好像只是学习排序
算法的一块垫脚石。
插入排序
算法描述:在未排序序列中,依次循环将元素插入到已排序的序列当中去。知道所有的数据
序列有序。
代码:
//插入排序
public void insertionSort()
{
int out,in;
for(out = 1;out < nElms ; out ++)
{
int temp = array[out];
in = out;
while(in > 0 && array[in - 1] >= temp )
{
array[in] = array[in - 1];
--in;
}
array[in] = temp;
}
}
不变性:在外层循环每趟结束时,比out变量下标号小的数据项都是局部有序的。
效率:
比较次数:每次循环最多的比较次数依次为1,2,......,N-1.最坏情况下和冒泡排序一样,次数为N(N-1)/2,
那平均只有一半数据项进行了比较,故比较次数为N(N-1)/4.
复制次数:复制次数大致等于比较次数,即为N(N-1)/4.
用大O表示法,那仍然维持在O(N²)。
三种算法比较:
从比较次数而言:
冒泡和选择排序的时间复杂度是一样的,而插入排序的效率是冒泡和选择排序的两倍。
从交换(复制)次数而言:
插入排序的效率是冒泡排序的3倍(一次交换的复杂度约等于三次复制,冒泡排序中是要交换,而插入排序时要复制就可以了)。
插入排序相对选择排序而言,如果都转化成复制的效率,选择时间复杂度为:选择排序为(N/2)*3,而插入排序为N(N-1)/4,
并体现不了插入排序的优势。
总结:
除非手边没有算法书可参考,一般情况几乎不太使用冒泡排序。
在大多数情况下,假设当数据量比较小或基本上有序时,插入排序算法是三种简单排序算法中
最好的选择。在实际应用中插入排序使用时最多的。
本站声明:网站内容来源于网络,如有侵权,请联系我们https://www.qiquanji.com,我们将及时处理。
微信扫码关注
更新实时通知
网友评论