原理
冒泡排序原理：
冒泡排序是较简单的排序算法，它是比较相邻两个元素的大小，并进行交换。
1、两个相邻元素进行比较，如果第一个比第二个大就交换(升序)，
2、重复1动作，从开始第一对到最后一对，次数会越来越少
3、直到没有可以比较的元素，最后一位数字是最大的。
时间复杂度：O(n²)
空间复杂度：1
稳定性：稳定：比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变。简而言之，相同元素的前后顺序不会改变
鸡尾酒冒泡排序原理：
鸡尾酒排序又叫双向冒泡排序，是冒泡排序的一种优化，排序时以双向在序列中进行排序，从低到高然后从高到低
1、先找到最小的数字，放在第一位，然后找到最大数字放在最后，
2、接着找第二小的数字放在第二位，找到第二大数字放在倒数第二位，
3、一次类推
时间复杂度：O(n²)
空间复杂度：1
冒泡排序动态示意图
当数据量小的时候看不出2者的快慢，可以把下面的示例里的长度改成10000，会发现鸡尾酒排序会快些
示例
import java.util.Random;
/**
* 冒泡排序
* 鸡尾酒冒泡排序
*
**/
public class BulkSort {
public static void main(String[] args) {
int len = 10;
int[] datas = new int[len];
int[] copyDatas = new int[len];
Random r = new Random(0);
for(int i = 0; i < len;i++) {
int d = r.nextInt(100);
datas[i] = d;
copyDatas[i] = d;
}
long start = System.currentTimeMillis();
bulkSort(datas);
long spend = System.currentTimeMillis() - start;
System.out.println("****** spend " + spend);
for (int data:
datas) {
System.out.print(data + ",");
}
System.out.println("");
start = System.currentTimeMillis();
shakerBulkSort(copyDatas);
spend = System.currentTimeMillis() - start;
System.out.println("****** shaker spend " + spend);
for (int data:
copyDatas) {
System.out.print(data + ",");
}
}
/**
* 冒泡排序：
* 假设升序排序
* 当前元素向后按顺序和相邻元素比较，
* 若当前元素比比较的元素大则交换，否则继续向后面进行比较
* @param datas
*/
public static void bulkSort(int[] datas) {
int len = datas.length;
if(len == 0) {
return;
}
//排序趟数
for (int i = 1; i < len; i++) {
//每趟比较次数
for (int currIdx = 0; currIdx < len - i; currIdx ++) {
int cmpIdx = currIdx + 1;
//相邻量元素之间进行比较，逆序就交换
if(datas[currIdx] > datas[cmpIdx]) {
int temp = datas[currIdx];
datas[currIdx] = datas[cmpIdx];
datas[currIdx + 1] = temp;
}
}
}
}
/**
* 双向冒泡排序，也叫鸡尾酒算法
*
* @param datas
*/
public static void shakerBulkSort(int[] datas) {
int len = datas.length;
if(len == 0) {
return;
}
int midLen = len / 2;
//排序趟数
for (int i = 0; i < midLen; i++) {
//每趟比较次数
for (int currIdx = i; currIdx < len-i-1 ; currIdx ++) {
int cmpIdx = currIdx + 1;
//相邻量元素之间进行比较，逆序就交换
if(datas[currIdx] > datas[cmpIdx]) {
int temp = datas[currIdx];
datas[currIdx] = datas[cmpIdx];
datas[cmpIdx] = temp;
}
}
for (int currIdx = len - 1 - (i+1); currIdx > i; currIdx --) {
int cmpIdx = currIdx - 1;
//相邻量元素之间进行比较，逆序就交换
if(datas[currIdx] < datas[cmpIdx]) {
int temp = datas[currIdx];
datas[currIdx] = datas[cmpIdx];
datas[cmpIdx] = temp;
}
}
}
}}
