JAVA算法之简单排序
2018-07-19 05:38:07来源:博客园 阅读 ()
冒泡排序:
在概念上是排序算法中最简单的,但是运行起来非常慢,冒泡排序遵循以下几个规则(假如我们现在要给一队打乱的足球队员排序):
- 比较两个队员
- 如果左边的队员比右边的高,则交换位置
- 向右移动一位,比较下面两个队员
接下来给出冒泡排序的JAVA代码
1 public Integer[] bubbleSort(Integer[] a){ 2 int out,in; 3 for(out = a.length-1;out > 0;out--){//外层每循环一次排出一个最大值 4 for(in = 0;int < out;in++){ 5 if(a[in]>a[in+1]){ //比较相邻元素大小,左边的大则交换位置 6 long temp = a[in]; 7 a[in] = a[in+1]; 8 a[in+1] = temp; 9 } 10 } 11 } 12 return a; 13 }
冒泡排序的效率:
在冒泡排序中若有N个数据项,则第一趟排序中需要N-1次比较,第二趟中有N-2次比较,类推下来我们可以得到比较次数的求和公式N*(N-1)/2这样我们忽略-1可得我们的冒泡算法大概做了N2/2次比较,假设数据是随机的,则需要进行交换的次数平均下来是N2/4次。交换和比较的操作次数都和N2成正比,在大O表示法中,冒泡排序运行需要O(N2)的时间级别,在任何时候只要看到一个循环嵌套在另外一个循环中我们都可以怀疑他的运行时间为O(N2)级别;
选择排序:
选择排序改进了冒泡排序,将必要的交换次数从O(N2)减少到了O(N)但是比较次数仍然是O(N2),选择排序算法,假如对一队足球队员进行排序,从队列的最左端开始记录队员的身高,和后面的队员挨个比较,若遇到身高比他矮的,则记录换成更矮的人的身高,最后这一趟排序就能找到最矮的队员,然后最后再和第一个队员进行交换位置;这期间做了N-1次比较,只做了一次交换;下面给出排序的java代码
public Integer[] selectionSort(Integer[] a){ int out, in, min; for (out = 0; out < a.length-1; out++) { min = out; //记录最小元素的索引 for (in = out + 1; in < a.length; in++) { if (a[min] > a[in]) { //依次比较记录较小元素的索引 min = in; } } //上面循环结束得到此外层循环的最小元素,进行交换 int temp = a[min]; a[min] = a[out]; a[out] = temp; } return a; }
选择排序的效率:
选择排序和冒泡排序执行了相同的比较次数N*(N-1)/2。当N值很大的时候,比较的次数是主要的,所以选择排序运行的时间用大O法表示为O(N2),虽然大O表示复杂度和冒泡一样,但是选择排序无疑是更快的,因为进行的交换要少很多,当N值较小时,特别是交换时间比比较时间大得多的时候,选择排序无疑是相当快的。
插入排序:
大多情况下插入排序是基本排序算法中最好的一种,虽然用大O表示时间复杂度仍然为O(N2),但是一般情况下比冒泡排序快一倍,比选择排序还要快一点。经常用在比较复杂的排序的最后阶段,比如快速排序。
插入排序算法即从队列最左边开始,将后面的每个人一个个地插入到队列的相应的位置,
上图可以很好地表示排序算法的排序过程,对于上图的理解,假如我们从排序算法的中间开始,在被标记的队员左边已经排好序了,此时让已标记的队员出列,然后依次同左边的队员比较,将比标记队员高的依次向右移,最后找到需要插入的位置,插入标记的队员,下面给出插入排序java代码
1 public Integer[] insertionSort(Integer[] a){ 2 int out, in; 3 4 for (out = 1; out < a.length; out++) { 5 int temp = a[out]; 6 in = out; 7 while (in > 0 && a[in - 1] >= temp) { 8 a[in] = a[in - 1]; //每个比当前标记的大的元素一次向数组后移一位 9 --in; 10 } 11 //当上面的循环结束时,此时in的位置就刚好停在比当前标记元素大的前面一个位置 12 //此时位置经过循环之后所有比标记元素大的都向后移动过了,因此此时可以向当前位置插入元素 13 a[in] = temp; 14 } 15 return a; 16 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 国外程序员整理的Java资源大全(全部是干货) 2020-06-12
- 2020年深圳中国平安各部门Java中级面试真题合集(附答案) 2020-06-11
- 2020年java就业前景 2020-06-11
- 04.Java基础语法 2020-06-11
- DES/3DES/AES 三种对称加密算法实现 2020-06-11
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash