常用算法(一)——冒泡排序和双向冒泡排序
程序员文章站
2022-07-12 14:37:26
...
今天回顾了一些常用的算法,总结了一下冒泡和双向冒泡排序。如下:
两种冒泡的原理:
冒泡排序: 嵌套的for循环,外层for控制比较的次数,内层的for控制移动的次数(简单说,就是赋值次数)。通过外层for的(次数)变量的自增,来控制内层for的(索引)变量向0索引逼近。
双向冒泡:定义左右两个索引为0和length-1,通过while循环里面的for循环(控制移动的循环)的索引自增(向右)和自减(向左),将最后一次移动操作后的索引值传递给控制向左和向右比较推荐的left和right两个变量,实现元素的比较向数组中间的逼近,最后当left>right,结束循环即排序结束。特别需要注意的是,外层是循环while别写成if。
效率比较:
如果数据量足够大,双向冒泡是明显要比单向冒泡的效率高的。
下面来看代码:
import java.util.Arrays;
/**
* Created by Sora on 2018-08-18.
* 双向冒泡排序: Shaker Sort
* 左——>右 把大的往后放
* 右——>左 把小的往前放
*/
public class BubbleAdvancedSort {
public static void main(String[] args) {
int[] score = {2,4,3,1,5,3,6,...,2,4,3,1,5,3,6,4};//足够大的数组
shakerSort(score,score.length);
System.out.println("最后结果:" + Arrays.toString(score));
int[] score1 = {2,4,3,1,5,3,6,...,2,4,3,1,5,3,6,4};//足够大的数组
commonBubble(score1);
System.out.println("最后结果:" + Arrays.toString(score1));
}
public static void shakerSort(int[] arr,int n) {
int left, right, l, r, i = 0;
left =0;
right = n -1;
long s = System.currentTimeMillis();
while (left < right) {
l = left + 1;
r = right -1;
//从左往右
for (i = left; i < right; i++) {
if (arr[i] > arr[i + 1]) {
arr[i] = arr[i] + arr[i + 1] - (arr[i + 1] = arr[i]);
r = i;
}
}
right = r;
//从右往左
for (i = right; i > left; i--) {
if (arr[i] < arr[i - 1]) {
arr[i] = arr[i] + arr[i - 1] - (arr[i - 1] = arr[i]);
//arr[i] = arr[i - 1] + (arr[i - 1] = arr[i]) * 0;
l = i;
}
}
left = l;//左边的索引向右移动
}
long e = System.currentTimeMillis();
System.out.println("双向冒泡:"+(e-s)+" 毫秒!");
}
//普通冒泡
public static void commonBubble(int[] arr) {
int len = arr.length;
long s = System.currentTimeMillis();
//比较次数
for (int i = 0; i < len; i++) {
//移动次数
for (int j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
//arr[j] = arr[j+1] + (arr[j+1] = arr[j])*0;
arr[j] = arr[j] + arr[j + 1] - (arr[j + 1] = arr[j]);
}
}
}
long e = System.currentTimeMillis();
System.out.println("普通冒泡:" + (e - s) + " 毫秒!");
}
}
多次测试后,双向冒泡在性能上都是优于单向冒泡的。
第二次测试
第三次测试
上一篇: STL函数对象——函数对象
下一篇: 排序算法