Java完成冒泡排序與雙向冒泡排序算法的代碼示例。本站提示廣大學習愛好者：（Java完成冒泡排序與雙向冒泡排序算法的代碼示例）文章只能為提供參考，不一定能成為您想要的結果。以下是Java完成冒泡排序與雙向冒泡排序算法的代碼示例正文
冒泡排序：
就是按索引逐次比擬相鄰的兩個元素，假如年夜於/小於(取決於須要升序排照樣降序排)，則置換，不然不做轉變
如許一輪上去，比擬了n-1次，n等於元素的個數；n-2, n-3 ... 一向到最初一輪，比擬了1次
所以 比擬次數為遞加：從n-1 到 1
那末總的比擬次數為：1+2+3+...+(n-1), 以等差公式盤算：(1+n-1)/2*(n-1) ==> n/2*(n-1) ==> (n^2-n) * 0.5
用年夜O表現算法的時光龐雜度：O(n^2) , 疏忽了系數0.5和常數-n
public class BubbleSort {
public static void main(String[] args) {
int len = 10;
int[] ary = new int[len];
Random random = new Random();
for (int j = 0; j < len; j++) {
ary[j] = random.nextInt(1000);
}
System.out.println("-------排序前------");
for (int j = 0; j < ary.length; j++) {
System.out.print(ary[j] + " ");
}
/*
* 升序， Asc1和Asc2優化了外部輪回的比擬次數，比擬好
* 總的比擬次數：
* Asc1、Asc2：(1+n-1)/2*(n-1) ==> n/2*(n-1) ==> n*(n-1)/2 ==>(n^2-n)/2
* Asc： n^2-n
*/
// orderAsc(ary);
// orderAsc2(ary);
orderAsc1(ary);
//降序，只須要把斷定年夜小於 置換一下
}
static void orderAsc(int[] ary) {
int count = 0;//比擬次數
int len = ary.length;
for (int j = 0; j < len; j++) {//外層固定輪回次數
for (int k = 0; k < len - 1; k++) {//內層固定輪回次數
if (ary[k] > ary[k + 1]) {
ary[k] = ary[k + 1] + (ary[k + 1] = ary[k]) * 0;//一步交流
/* 交流兩個變量值
* a=a+b
* b=a-b
* a=a-b
*/
}
count++;
}
}
System.out.println("\n-----orderAsc升序排序後------次數：" + count);
for (int j = 0; j < len; j++) {
System.out.print(ary[j] + " ");
}
}
static void orderAsc1(int[] ary) {
int count = 0;//比擬次數
int len = ary.length;
for (int j = 0; j < len; j++) {//外層固定輪回次數
for (int k = len - 1; k > j; k--) {//內層從多到少遞加比擬次數
if (ary[k] < ary[k - 1]) {
ary[k] = ary[k - 1] + (ary[k - 1] = ary[k]) * 0;//一步交流
}
count++;
}
}
System.out.println("\n-----orderAsc1升序排序後------次數：" + count);
for (int j = 0; j < len; j++) {
System.out.print(ary[j] + " ");
}
}
static void orderAsc2(int[] ary) {
int count = 0;//比擬次數
int len = ary.length;
for (int j = len - 1; j > 0; j--) {//外層固定輪回次數
/*
* k < j; 總的比擬次數=(n^2-n)/2
*/
for (int k = 0; k < j; k++) {//內層從多到少遞加比擬次數
if (ary[k] > ary[k + 1]) {
ary[k] = ary[k + 1] + (ary[k + 1] = ary[k]) * 0;//一步交流
}
count++;
}
}
System.out.println("\n-----orderAsc2升序排序後------次數：" + count);
for (int j = 0; j < len; j++) {
System.out.print(ary[j] + " ");
}
}
}
打印
-------排序前------ 898 7 862 286 879 660 433 724 316 737 -----orderAsc1升序排序後------次數：45 7 286 316 433 660 724 737 862 879 898
雙向冒泡排序
冒泡排序_雞尾酒排序、就是雙向冒泡排序。
此算法與冒泡排序的分歧處在於排序時是以雙向在序列中停止排序,外層比擬閣下界限l<r,
內層一個輪回從左向右比，取高值置後；一個輪回從右向左，取低值置前；
效力上，O(N^2), 不比通俗的冒泡快
public class Bubble_CocktailSort {
public static void main(String[] args) {
int len = 10;
int[] ary = new int[len];
Random random = new Random();
for (int j = 0; j < len; j++) {
ary[j] = random.nextInt(1000);
}
/*
* 交流次數最小也是1次，最年夜也是(n^2-n)/2次
*/
// ary=new int[]{10,9,8,7,6,5,4,3,2,1}; //測試交流次數
// ary=new int[]{1,2,3,4,5,6,7,8,10,9}; //測試交流次數
System.out.println("-------排序前------");
for (int j = 0; j < ary.length; j++) {
System.out.print(ary[j] + " ");
}
orderAsc1(ary);
// orderAsc2(ary);
//降序，只須要把斷定年夜小於 置換一下
}
static void orderAsc1(int[] ary) {
int compareCount = 0;//比擬次數
int changeCount = 0;//交流次數
int len = ary.length;
int left = 0, right = len -1, tl, tr;
while (left < right) {//外層固定輪回次數
tl = left + 1;
tr = right - 1;
for (int k = left; k < right; k++) {//內層從多到少遞加比擬次數, 從左向右
if (ary[k] > ary[k + 1]) {//前年夜於後， 置換
ary[k] = ary[k + 1] + (ary[k + 1] = ary[k]) * 0;//一步交流
changeCount++;
tr = k; //一輪中最初一比擬的時刻，將k地點索引賦給tr, tr表現今後比擬的停止索引值, 從左向右比後，k表現右邊的索引
}
compareCount++;
}
right = tr;
for (int k = right; k > left; k--) {//內層從多到少遞加比擬次數, 從右向左
if (ary[k] < ary[k - 1]) {//後小於前 置換
ary[k] = ary[k - 1] + (ary[k - 1] = ary[k]) * 0;//一步交流
changeCount++;
tl = k; //一輪中最初一比擬的時刻，將k地點索引賦給tl, tl表現今後比擬的開端索引值, 從向右向左比後，k表現左邊的索引
}
compareCount++;
}
left = tl;
}
System.out.println("\n-----orderAsc1升序排序後------比擬次數：" + compareCount + ", 交流次數：" + changeCount);
for (int j = 0; j < len; j++) {
System.out.print(ary[j] + " ");
}
}
//跟orderAsc1的思緒沒有差別
static void orderAsc2(int[] ary) {
int compareCount = 0;//比擬次數
int changeCount = 0;//交流次數
int len = ary.length;
int l = 0, r = len -1, tl, tr;
for (; l < r; ) {//外層固定輪回次數
tl = l + 1;
tr = r - 1;
/*
* 從左向右比，將年夜的移到前面
*/
for (int k = l; k < r; k++) {
if (ary[k] > ary[k + 1]) {
int temp = ary[k] + ary[k + 1];
ary[k + 1] = temp - ary[k + 1];
ary[k] = temp - ary[k + 1];
changeCount++;
tr = k;
}
compareCount++;
}
r = tr;
/*
* 從右向左比，將小的移到後面
*/
for (int k = r; k > l; k--) {
if (ary[k] < ary[k - 1]) {
int temp = ary[k] + ary[k - 1];
ary[k - 1] = temp - ary[k - 1];
ary[k] = temp - ary[k - 1];
changeCount++;
tl = k;
}
compareCount++;
}
l = tl;
}
System.out.println("\n-----orderAsc2升序排序後------比擬次數：" + compareCount + ", 交流次數：" + changeCount);
for (int j = 0; j < len; j++) {
System.out.print(ary[j] + " ");
}
}
}
打印
-------排序前------ 783 173 53 955 697 839 201 899 680 677 -----orderAsc1升序排序後------比擬次數：34, 交流次數：22 53 173 201 677 680 697 783 839 899 955
