冒泡排序(三种实现方案思路与实现)
程序员文章站
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
上一篇: Linux硬盘合并的实现代码