冒泡排序算法，是最基本的排序算法， 它属于交换排序。
冒泡排序过程
设想被排序的数组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 堆排序算法
^