java shake排序算法(改良的冒泡排序)

2018年04月21日 08:49 | 2733次浏览 作者原创 版权保护

冒泡排序算法,是最基本的排序算法, 它属于交换排序。

冒泡排序过程

设想被排序的数组R[1..N]垂直竖立,将每个数据元素看作有重量的气泡,根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R,凡扫描到违反本原则的轻气泡,就使其向上"漂浮"(交换位置),如此反复进行,直至最后任何两个气泡都是轻者在上,重者在下为止。

性能分析

若记录序列的初始状态为"正序",则冒泡排序过程只需进行一趟排序,在排序过程中只需进行n-1次比较,且不移动记录;反之,若记录序列的初始状态为"逆序",则需进行n(n-1)/2次比较和记录移动。因此冒泡排序总的时间复杂度为O(n*n)。

改良的冒泡排序实现

根据扫描方向不同,实现略有不同。

   方法就在于气泡排序的双向进行,先让气泡排序由左向右进行,再来让气泡排序由右往左进行, 

如此完成一次排序的动作,而您必须使用left与right两个旗标来记录左右两端已排序的元素位置

package com.wepayweb.weixin.util.paixu;
/***
 * 
 * @author www.vxzsk.com V型知识库
 *
 */
public class Shakersort {
	 final int MAX=20;  
	   int num[]=new int[MAX];  
	   {  
	       System.out.print("生成的随机数组是:");  
	       for(int i=0;i<20;i++){  
	           num[i]=(int)(Math.random()*100);  
	           System.out.print(num[i]+" ");  
	       }  
	       System.out.println();  
	   }  
	
	/*---------------------Shake排序法(改良的冒泡排序法)-------------------------- 
    方法就在于气泡排序的双向进行,先让气泡排序由左向右进行,再来让气泡排序由右往左进行, 
    如此完成一次排序的动作,而您必须使用left与right两个旗标来记录左右两端已排序的元素位置。  
--------------------------------------------------------------------*/  
public void shakersort(int number[]) {   
int i, temp, left = 0, right = MAX - 1, shift = 0;   
long start,end;  

start=System.nanoTime();  
while(left < right) {   
  // 向右進行氣泡排序   
  for(i = left; i < right; i++) {   
      if(number[i] > number[i+1]) {   
          temp=number[i];  
          number[i]=number[i+1];  
          number[i+1]=temp;  
          shift = i;   
      }   
  }   
  right = shift;    

  // 向左進行氣泡排序   
  for(i = right; i > left; i--) {   
      if(number[i] < number[i-1]) {   
          temp=number[i];  
          number[i]=number[i-1];  
          number[i-1]=temp;   
          shift = i;   
      }   
  }   
  left = shift;   
}  
end=System.nanoTime();  

System.out.println("-----------------shake排序法(改进的冒泡排序法)------------------");  
System.out.print("排序后是:");  
for(i=0;i<=MAX-1;i++){  
  System.out.print(number[i]+" ");  
}  
System.out.println();  
System.out.println("排序使用时间:"+(end-start)+" ns");  
}   

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Shakersort s = new Shakersort();
		s.shakersort(s.num.clone());                        //插入排序法  
	}

}

运行main方法




小说《我是全球混乱的源头》
此文章本站原创,地址 https://www.vxzsk.com/823.html   转载请注明出处!谢谢!

感觉本站内容不错,读后有收获?小额赞助,鼓励网站分享出更好的教程


上一篇:mongodb 查询分析 下一篇:java 堆排序算法
^