给数组排序的三种简单算法:冒泡排序法,选择排序法,插入排序法。
用升序的例子来说明一下各算法的原理吧:
冒泡排序算法是先把数组的第1个元素与第2个元素比较,如果第1个大于第2个,则交换两者的位置,反之则不交换;接着比较第2个元素与第3个元素……这样比较、交换一遍后,数组当中最大的元素已经排到了最后;接下来从第1个元素开始,循环前面的操作,循环的次数比元素的个数少1,每次循环时比较大小的次数比上一次循环次数少1。这样每次循环的结果都是把大的元素排到最后,看起来像烧开水冒水泡,故名“冒泡排序算法”。
设数组元素个数为n,冒泡排序法第1次循环需要比较n-1次,第2次循环需要比较n-2次,第n次循环需要比较1次。每次的循环比较的次数可以写成这样一个序列:n-1,n-2,n-3……1,总共的比较次数为((n-1)+1)(n-1)/2,即n(n-1)/2。这里n(n-1)可以看成n^2(n值越大,n^2与n(n-1)的差别就越可以忽略不计),即n^2/2。用大O表示法表示算法效率为O(N^2)。交换次数在最理想情况下为0,在最糟糕的情况下每次比较都需要交换。所以第1次循环时交换的次数平均为(n-1)/2,第2次为(n-2)/2,最后可得出总交换次数为((n-1)/2+1/2)(n-1)/2,即n(n-1)/4,同理可用大O表示法表示算法效率为O(N^2)。
插入排序算法需要用到一个“指针”(一个用来标记最小值下标的临时变量)。其原理是先把“指针”指向第1个元素,即0。接着拿“指针”指着的元素和每一个元素作比较,如果被比较的元素小于“指针”指着的元素,就把“指针”指向被比较的元素,这样比较完一次,指针指着的元素就是最小的元素,然后把它与第一个元素交换位置。接着把“指针”指向第2个元素,开始循环刚才的操作。设元素个数为n,循环需要n-1次。插入排序过程中,比较大小的次数为((n-1)+1)(n-1)/2,即n(n-1)/2,用大O表示法表示算法效率为O(N^2)。理想情况下数据交换次数为0,在最糟糕的情况下每循环一次就交换一次数据(虽然最糟糕情况下每次比较都会把临时变量重新赋值一次,但相对于冒泡法每次的交换操作来说,赋值操作耗的资源少。交换操作至少等于3次赋值操作外加3次计算--个人理解)。所以平均交换次数为(n-1)/2,用大O表示法表示算法效率为O(N)。由此看来,选择排序法比冒泡排序法要快。但在数据量少的情况下效果不是很明显。
插入排序法是先把数组的第1个元素当作一个有序数组,再拿非有序数组的第1个元素(即整个数组的第2个元素)(暂且称它为参考元素吧)与之前的有序数组依次比较(当然第1次比较时,有序数组元素只有一个,所以只需要比较一次),如果第2个元素比第1个元素大,则跳出本次循环;反之,则将第1个元素向后移一个位置,覆盖掉第2个元素,然后把参考元素的值赋给第1个元素。接着开始第2次比较,这时有序数组中已经有两个元素了,所以拿第3个元素作参数元素,将它与前面的有序数组中的元素依次比较,如果参数元素比前面的元素大,这时因为参考元素不可能比有序数组中的其它元素小了,所以跳出本次循环;反之,则将这个比参考元素小的元素往后移动一个位置,直到有序数组中与参考元素比较的元素比参考小,这时把参考元素的值赋给较小的那个元素所在的下一个位置,这样循环。设元素个数为n,则循环次数为n-1。最理想情况下每次循环的比较次数为1;最糟糕的情况下第一次循环的比较次数为1,第2次为2,第n-1次为n-1,总次数为(1+(n-1))(n-1)/2,即n(n-1)/2。所以平均比较次数为((n-1)+n(n-1)/2)/2,即(n^2+n-2)/2,相对n^2来说,n-2可以忽略,得大O表示法:O(N^2)。理想情况下交换次数为0,最糟糕情况下,交换次数为n-1(虽然最糟糕情况下每次比较都会移动数组中的元素,而这移动操作其实就是给数组中元素重新赋值的操作,同选择排序法一样,相对于冒泡法每次的交换操作来说,赋值操作耗的资源少。交换操作至少等于3次赋值操作外加3次计算--个人理解)。所以平均交换次数为(n-1)/2,用大O表示算法效率为:O(N)。
以上说明都以升序排序为例,降序排序稍有不同。
分享到:
相关推荐
易语言数组排序算法集合源码,数组排序算法集合,排序程序,冒泡排序,改冒泡法,双向泡排序,双响泡排序,直接插入排序,地精排序,地精排序2,地精排序3,二分排序,选择排序,梳子排序,希尔排序,快速排序
用c语言数组实现的快速排序算法,用c语言数组实现的快速排序算法
Java 数组以及排序算法
算法(冒泡,选择,插入,数组排序) package Teacher; import java.io.*; import java.util.Scanner; public class Tset { public static void main(String args[]) throws IOException { // 需要排序的数组,...
易语言源码易语言数组排序算法集合源码.rar 易语言源码易语言数组排序算法集合源码.rar 易语言源码易语言数组排序算法集合源码.rar 易语言源码易语言数组排序算法集合源码.rar 易语言源码易语言数组排序算法集合...
数组排序算法,如: int[] array= {2, 1, 4, 5, 3}; 通过此方法 array={1,2,3,4,5};
最快的排序算法 千万级亿级数组排序最快的实现方法,排序算法数据结构
堆排序 归并排序 选择排序 快速排序 插入排序 可选择数组初始状态(随机、正序、逆序) 通过输出的时间可以更好地比较在不同数组状态下 各种排序算法的时间复杂度
该文档涵盖了数组排序的基本概念,包括如何实现各种排序算法,如冒泡排序、选择排序、插入排序、归并排序和快速排序。此外,文档还为每个排序算法提供了详细的代码示例和实现细节。 该文档还涵盖了高级主题,如如何...
Java程序中,排序算法有很多种,此次给大家介绍的是类排序方法、冒泡排序方法和直接排序方法。
c语言的基本算法c语言的基本算法c语言的基本算法c语言的基本算法c语言的基本算法c语言的基本算法c语言的基本算法c语言的基本算法c语言的基本算法c语言的基本算法c语言的基本算法c语言的基本算法c语言的基本算法c语言...
数组应用及冒泡排序算法示例,适用于初学者
提出了一种基于数组排序的堆排序方法。 讨论了它的一些优点和缺点。 将其与传统的直接应用方法进行了比较。 在该方法中,在构建空堆之后,将数组中的排序关键字逐一放入堆中。 该方法需要相对较少的空间,适合于有序...
php排序 ,插入排序,选择排序,冒泡排序,快速排序。 整理出来,供大家参考一下
iOS开发·必会的算法操作:字符串数组排序 模型对象数组排序
Java数组排序总结(冒泡_选择_插入_希尔)__递归算法的复杂度,实用
这个程序的头文件中包含四种排序方法:泡沫排序法(bubble),插入排序...头文件中还使用了模板技术,以便可以同时实现几种类型的排序算法。 dinimicky_hu对原程序做了修改和优化,使用了函数指针数组,并修改了一个BUG
C语言的数组 排序,删除,查找联合搬算法
本文介绍了Java数组的三种排序。冒泡,直接选择和反转。配有图片解释及完整代码。
主要给大家介绍了关于JavaScript数组排序的六种常见算法,文中通过示例代码介绍的非常详细,对大家的学习或者使用JavaScript数组具有一定的参考学习价值,需要的朋友们下面来一起学习学习吧