Java實(shí)現(xiàn)冒泡排序與雙向冒泡排序算法的代碼示例
更新時(shí)間：2016年04月12日 08:47:20 作者：匆忙擁擠repeat
這篇文章主要介紹了Java實(shí)現(xiàn)冒泡排序與雙向冒泡排序算法的代碼示例,值得一提的是所謂的雙向冒泡排序并不比普通的冒泡排序效率來(lái)得高,注意相應(yīng)的時(shí)間復(fù)雜度,需要的朋友可以參考下
冒泡排序：
就是按索引逐次比較相鄰的兩個(gè)元素，如果大于/小于(取決于需要升序排還是降序排)，則置換，否則不做改變
這樣一輪下來(lái)，比較了n-1次，n等于元素的個(gè)數(shù)；n-2, n-3 ... 一直到最后一輪，比較了1次
所以 比較次數(shù)為遞減：從n-1 到 1
那么總的比較次數(shù)為：1+2+3+...+(n-1), 以等差公式計(jì)算：(1+n-1)/2*(n-1) ==> n/2*(n-1) ==> (n^2-n) * 0.5
用大O表示算法的時(shí)間復(fù)雜度：O(n^2) , 忽略了系數(shù)0.5和常數(shù)-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優(yōu)化了內(nèi)部循環(huán)的比較次數(shù)，比較好
* 總的比較次數(shù)：
* 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;//比較次數(shù)
int len = ary.length;
for (int j = 0; j < len; j++) {//外層固定循環(huán)次數(shù)
for (int k = 0; k < len - 1; k++) {//內(nèi)層固定循環(huán)次數(shù)
if (ary[k] > ary[k + 1]) {
ary[k] = ary[k + 1] + (ary[k + 1] = ary[k]) * 0;//一步交換
/* 交換兩個(gè)變量值
* a=a+b
* b=a-b
* a=a-b
*/
}
count++;
}
}
System.out.println("\n-----orderAsc升序排序后------次數(shù)：" + count);
for (int j = 0; j < len; j++) {
System.out.print(ary[j] + " ");
}
}
static void orderAsc1(int[] ary) {
int count = 0;//比較次數(shù)
int len = ary.length;
for (int j = 0; j < len; j++) {//外層固定循環(huán)次數(shù)
for (int k = len - 1; k > j; k--) {//內(nèi)層從多到少遞減比較次數(shù)
if (ary[k] < ary[k - 1]) {
ary[k] = ary[k - 1] + (ary[k - 1] = ary[k]) * 0;//一步交換
}
count++;
}
}
System.out.println("\n-----orderAsc1升序排序后------次數(shù)：" + count);
for (int j = 0; j < len; j++) {
System.out.print(ary[j] + " ");
}
}
static void orderAsc2(int[] ary) {
int count = 0;//比較次數(shù)
int len = ary.length;
for (int j = len - 1; j > 0; j--) {//外層固定循環(huán)次數(shù)
/*
* k < j; 總的比較次數(shù)=(n^2-n)/2
*/
for (int k = 0; k < j; k++) {//內(nèi)層從多到少遞減比較次數(shù)
if (ary[k] > ary[k + 1]) {
ary[k] = ary[k + 1] + (ary[k + 1] = ary[k]) * 0;//一步交換
}
count++;
}
}
System.out.println("\n-----orderAsc2升序排序后------次數(shù)：" + count);
for (int j = 0; j < len; j++) {
System.out.print(ary[j] + " ");
}
}
}
打印
-------排序前------ 898 7 862 286 879 660 433 724 316 737 -----orderAsc1升序排序后------次數(shù)：45 7 286 316 433 660 724 737 862 879 898
雙向冒泡排序
冒泡排序_雞尾酒排序、就是雙向冒泡排序。
此算法與冒泡排序的不同處在于排序時(shí)是以雙向在序列中進(jìn)行排序,外層比較左右邊界l<r,
內(nèi)層一個(gè)循環(huán)從左向右比，取高值置后；一個(gè)循環(huán)從右向左，取低值置前；
效率上，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);
}
/*
* 交換次數(shù)最小也是1次，最大也是(n^2-n)/2次
*/
// ary=new int[]{10,9,8,7,6,5,4,3,2,1}; //測(cè)試交換次數(shù)
// ary=new int[]{1,2,3,4,5,6,7,8,10,9}; //測(cè)試交換次數(shù)
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;//比較次數(shù)
int changeCount = 0;//交換次數(shù)
int len = ary.length;
int left = 0, right = len -1, tl, tr;
while (left < right) {//外層固定循環(huán)次數(shù)
tl = left + 1;
tr = right - 1;
for (int k = left; k < right; k++) {//內(nèi)層從多到少遞減比較次數(shù), 從左向右
if (ary[k] > ary[k + 1]) {//前大于后， 置換
ary[k] = ary[k + 1] + (ary[k + 1] = ary[k]) * 0;//一步交換
changeCount++;
tr = k; //一輪中最后一比較的時(shí)候，將k所在索引賦給tr, tr表示以后比較的結(jié)束索引值, 從左向右比后，k表示左邊的索引
}
compareCount++;
}
right = tr;
for (int k = right; k > left; k--) {//內(nèi)層從多到少遞減比較次數(shù), 從右向左
if (ary[k] < ary[k - 1]) {//后小于前 置換
ary[k] = ary[k - 1] + (ary[k - 1] = ary[k]) * 0;//一步交換
changeCount++;
tl = k; //一輪中最后一比較的時(shí)候，將k所在索引賦給tl, tl表示以后比較的開(kāi)始索引值, 從向右向左比后，k表示右邊的索引
}
compareCount++;
}
left = tl;
}
System.out.println("\n-----orderAsc1升序排序后------比較次數(shù)：" + compareCount + ", 交換次數(shù)：" + changeCount);
for (int j = 0; j < len; j++) {
System.out.print(ary[j] + " ");
}
}
//跟orderAsc1的思路沒(méi)有區(qū)別
static void orderAsc2(int[] ary) {
int compareCount = 0;//比較次數(shù)
int changeCount = 0;//交換次數(shù)
int len = ary.length;
int l = 0, r = len -1, tl, tr;
for (; l < r; ) {//外層固定循環(huán)次數(shù)
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升序排序后------比較次數(shù)：" + compareCount + ", 交換次數(shù)：" + changeCount);
for (int j = 0; j < len; j++) {
System.out.print(ary[j] + " ");
}
}
}
打印
-------排序前------ 783 173 53 955 697 839 201 899 680 677 -----orderAsc1升序排序后------比較次數(shù)：34, 交換次數(shù)：22 53 173 201 677 680 697 783 839 899 955
相關(guān)文章
這篇文章主要給大家介紹了關(guān)于java讀取zip/jar包中文件的幾種方式,在我們?nèi)粘Ｊ褂弥袎嚎s文件是非常常用的,文中通過(guò)示例代碼將java讀取zip/jar包中文件的方法介紹的非常詳細(xì),需要的朋友可以參考下2023-07-07
SpringBoot項(xiàng)目中使用redis緩存的方法步驟
本篇文章主要介紹了SpringBoot項(xiàng)目中使用redis緩存的方法步驟，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-12-12
Windows環(huán)境IDEA下Ranger1.2.0源碼編譯詳細(xì)流程
本文給大家講解Windows環(huán)境IDEA下Ranger1.2.0源碼編譯過(guò)程，通過(guò)配置Tomcat，發(fā)布?security-admin-web項(xiàng)目，編譯啟動(dòng)tomcat即可完成，需要的朋友參考下2021-06-06
Eclipse是一款非常優(yōu)秀的開(kāi)源IDE，非常適合Java開(kāi)發(fā)，由于支持插件技術(shù)，受到了越來(lái)越多的開(kāi)發(fā)者的歡迎。配合眾多令人眼花繚亂的插件，完全可以滿(mǎn)足從企業(yè)級(jí)Java應(yīng)用到手機(jī)終端Java游戲的開(kāi)發(fā)。本文將帶您手把手步入Eclipse的廣闊天地2016-09-09
java利用CountDownLatch實(shí)現(xiàn)并行計(jì)算
這篇文章主要介紹了java利用CountDownLatch實(shí)現(xiàn)并行計(jì)算，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-10-10
這篇文章主要給大家介紹了關(guān)于Spring Boot配置過(guò)濾器的2種方式，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家學(xué)習(xí)或者使用Spring Boot具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-09-09
Springboot整合hutool驗(yàn)證碼的實(shí)例代碼
在 Spring Boot 中,你可以將 Hutool 生成驗(yàn)證碼的功能集成到 RESTful API 接口中,這篇文章主要介紹了Springboot整合hutool驗(yàn)證碼,需要的朋友可以參考下2024-08-08
這篇文章主要介紹了Java之springcloud Sentinel案例講解,本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08
SpringBoot集成FastDFS+Nginx整合基于Token的防盜鏈的方法
這篇文章主要介紹了SpringBoot集成FastDFS+Nginx整合基于Token的防盜鏈的方法，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2019-04-04
Java線程池中的Future實(shí)現(xiàn)詳解
這篇文章主要介紹了Java線程池中的Future實(shí)現(xiàn)詳解, FutureTask是一個(gè)任務(wù),FutureTask繼承了Runnable、Callable, 通過(guò)FutureTask可以獲取到任務(wù)執(zhí)行的狀態(tài),任務(wù)執(zhí)行完成完成后,將結(jié)構(gòu)通過(guò)Future接口返回,調(diào)用者可以調(diào)用Future#get()方法獲取到數(shù)據(jù),需要的朋友可以參考下2023-10-10