欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

冒泡排序(三种实现方案思路与实现)

程序员文章站 2022-05-12 17:53:38
...

1、第一种是最简单的方法,不用考虑性能问题:

  • 比较相邻的元素。如果第一个比第二个大(升序),就交换他们两个。
  • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  • 针对所有的元素重复以上的步骤,除了最后一个。
  • 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

所以设置一个外循环控制每次比较的此时。内循环进行比较,如第一次外循环也就是第一个元素需要比较n-1次,每次都是前一个和后一个比较,所以内循环每次只需要比较外层的前一个。

	public static int[] sort(int[] ins){
		boolean flag = true;		
			for(int i=ins.length-1; i>0; i--){
				for(int j=0; j<i; j++){//每次到达最后一个i下标的前一个,然后和后一个比较
					if(ins[j]>ins[j+1]){
						int temp = ins[j+1];
						ins[j+1] = ins[j];
						ins[j] = temp;
					}
				}
			}
		return ins;	
	}

第二种:如果这个序列是一个有序的,那么此时不用每个都进行比较,一旦比较的中间一次没有交换数据,说明这个序列已经是有序了。所以可以设置一个标志位。一旦一个循环比较没有交换,将标志位设置为false,跳出循环。

public static int[] sort2(int[] ins){
		boolean flag = true;
		int length = ins.length-1;
		while(flag){
			flag = false;
				for(int j=0; j< length; j++){
					if(ins[j]>ins[j+1]){
						int temp = ins[j+1];
						ins[j+1] = ins[j];
						ins[j] = temp;
						flag = true;
					}
				}
			length --;
		}	
		return ins;		
	}

第三种:如果有10万个数据需要进行冒泡排序,那么这个时候如果只有前面200个是无序的,后面的都是有序,而且都比前面200个无序的大。所只需要比较前面200然后排好序就可以了,上面的这种方法其实前面200个排好序后也就停止了,因为再排序就会跳出循环,但是上面的那种方法每次一个比较都要和200后面的数据进行比较。其实只需要比较前面200个数据就可以了。这样比较后面的数据就会带来时间的问题。所以我们每次排序都找到一个节点,这个节点的后面的数据就是已经排好了,不用比较的数据。

	public static int[] sort3(int[] ins){
		int flage = ins.length-1;
		while(flage>0){
			int k = flage;//k来记录遍历的尾边界
			flage=0;
			
			for(int i=0; i<k; i++){
				if(ins[i] > ins[i+1]){
					int temp = ins[i+1];
					ins[i+1] = ins[i];
					ins[i] = temp;
					flage = i;//每次比较后将边界值重新设定,如果比较过程中没有执行这一行语句,说明已经完成了排序,和第二种方法一样
				}
			}
		}
		return null;	
	}
                long t1 = System.currentTimeMillis();
		int[] ins2 = sort1(ins);
		System.out.println(System.currentTimeMillis()-t1);
		
		long t2 = System.currentTimeMillis();
		int[] ins3 = sort2(ins);
		System.out.println(System.currentTimeMillis()-t2);
		
		long t3 = System.currentTimeMillis();
		int[] ins4 = sort3(ins);
		System.out.println(System.currentTimeMillis()-t3);


这个是三个分别的运行结果(这个是运行时间):

35
1

0


相关标签: 冒泡排序 冒泡