資訊專欄INFORMATION COLUMN
摘要：外層循環(huán)讓內(nèi)層循環(huán)繼續(xù)排沒(méi)有排序過(guò)的數(shù)組，排序過(guò)的不用再排。那么優(yōu)化后的算法能快多少呢。我們都以數(shù)組長(zhǎng)度為來(lái)計(jì)算傳統(tǒng)冒泡排序步，優(yōu)化后的冒泡排序步。因?yàn)閮?yōu)化后的冒泡排序，每排完一次，最后一個(gè)數(shù)已經(jīng)是最大的，就不需要再比較了。
冒泡排序的時(shí)間用大O表示法是O(N^2).
傳統(tǒng)的冒泡排序：
/**
* @param total 要排序的數(shù)組長(zhǎng)度
*/
public void sort(int total){
int num[];
if(total <= 0){
System.out.println("請(qǐng)輸入大于0的正整數(shù)");
}else{
num = new int[total];
for (int i = 0 ; i < total; i++){
//生成隨機(jī)1到100之間的數(shù)
Random ra =new Random();
num[i] = ra.nextInt(100)+1;
}
System.out.println("要排序的數(shù)組為：" + Arrays.toString(num));
int sum = 0;
int out,in;
for (out = total - 1; out > 1; out--){
for (in = 0 ; in < out; in++){
sum ++;
if(num[in] > num[in+1]){
int temp = num[in];
num[in] = num[in+1];
num[in+1] = temp;
}
}
}
// 最原始的冒泡排序
for(int i = 0; i < total -1 ; i ++){
for (int j = 0 ; j < total -1 ; j++){
sum ++;
if(num[j] > num[j+1]){
int temp = num[j];
num[j] = num[j+1];
num[j+1] = temp;
}
}
}
System.out.println("排序完成的數(shù)組為：" + Arrays.toString(num));
System.out.println("總共用次數(shù)：" + sum);
}
}
優(yōu)化過(guò)后的冒泡排序：
/**
* @param total 要排序的數(shù)組長(zhǎng)度
*/
public void sort(int total){
int num[];
if(total <= 0){
System.out.println("請(qǐng)輸入大于0的正整數(shù)");
}else{
num = new int[total];
for (int i = 0 ; i < total; i++){
//生成隨機(jī)1到100之間的數(shù)
Random ra =new Random();
num[i] = ra.nextInt(100)+1;
}
System.out.println("要排序的數(shù)組為：" + Arrays.toString(num));
/**核心算法：
* 雙重循環(huán)，外層循環(huán)用于控制排多少次序。
* 內(nèi)層循環(huán)從第一位開(kāi)始一直往后比較，內(nèi)層循環(huán)一次后，可以將最大的數(shù)至于末尾。
* 外層循環(huán)讓內(nèi)層循環(huán)繼續(xù)排沒(méi)有排序過(guò)的數(shù)組，排序過(guò)的不用再排。
*/
int sum = 0;
int out,in;
for (out = total - 1; out > 1; out--){
for (in = 0 ; in < out; in++){
sum ++;
if(num[in] > num[in+1]){
int temp = num[in];
num[in] = num[in+1];
num[in+1] = temp;
}
}
}
System.out.println("排序完成的數(shù)組為：" + Arrays.toString(num));
System.out.println("總共用次數(shù)：" + sum);
}
}
大家對(duì)比可以發(fā)現(xiàn)，就是外層循環(huán)的時(shí)候有點(diǎn)變化，其他的代碼都是一模一樣的。
那么優(yōu)化后的算法能快多少呢。我們都以數(shù)組長(zhǎng)度為10來(lái)計(jì)算：
傳統(tǒng)冒泡排序：9x9=81步，
優(yōu)化后的冒泡排序：9+8+7+6+5+4+3+2=44步。
因?yàn)閮?yōu)化后的冒泡排序，每排完一次，最后一個(gè)數(shù)已經(jīng)是最大的，就不需要再比較了。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/73305.html
摘要：二分查找法要查找的數(shù)數(shù)組長(zhǎng)度設(shè)定的數(shù)組花了多少次找到最小值最大值當(dāng)前猜的值打印猜的每個(gè)數(shù)找到了花了次如果猜的數(shù)大于選定的數(shù)，則把設(shè)為猜的數(shù)，否則把設(shè)為猜的數(shù)請(qǐng)輸入大于等于的正整數(shù)且查找的數(shù)不能大于數(shù)組里最大的數(shù)調(diào)用方法執(zhí)行結(jié)果找到了花了次 大O表示法使用大寫(xiě)字母O，可以認(rèn)為其含義為order of（大約是）。我們可以使用大O法來(lái)描述線性查找使用了O(N)級(jí)時(shí)間，二分查找使用了O(log...
摘要：多練練排序算法，不僅能夠讓我們知道一些排序方法的底層實(shí)現(xiàn)細(xì)節(jié)，更能夠鍛煉我們的思維，提升編程能力。排序算法的穩(wěn)定性一個(gè)穩(wěn)定的排序，指的是在排序之后，相同元素的前后順序不會(huì)被改變，反之就稱為不穩(wěn)定。 1. 導(dǎo)言 因?yàn)檫@是排序算法系列的第一篇文章，所以多啰嗦幾句。 排序是很常見(jiàn)的算法之一，現(xiàn)在很多編程語(yǔ)言都集成了一些排序算法，比如Java 的Arrays.sort()方法，這種方式讓我們可...
摘要：算法思想冒泡排序?qū)儆谝环N典型的交換排序。冒泡排序常規(guī)版代碼實(shí)現(xiàn)下面詳細(xì)分析一下常規(guī)版的冒泡排序，整個(gè)算法流程其實(shí)就是上面實(shí)例所分析的過(guò)程。 算法思想 冒泡排序?qū)儆谝环N典型的交換排序。 交換排序顧名思義就是通過(guò)元素的兩兩比較，判斷是否符合要求，如過(guò)不符合就交換位置來(lái)達(dá)到排序的目的。冒泡排序名字的由來(lái)就是因?yàn)樵诮粨Q過(guò)程中，類似水冒泡，?。ù螅┑脑亟?jīng)過(guò)不斷的交換由水底慢慢的浮到水的...
摘要：插入排序特殊從第二個(gè)元素開(kāi)始，和第一個(gè)元素比較，如果滿足排序的順序，則交換順序。優(yōu)化后選擇排序從第一個(gè)位置開(kāi)始遍歷待排序的元素，找到最小值和第一元素交換從位置開(kāi)始往后遍歷，找到之后元素中的最小值，和第個(gè)元素交換位置。 插入排序1、特殊：從第二個(gè)元素開(kāi)始，和第一個(gè)元素比較，如果滿足排序的順序，則交換順序。2、一般：把待比較和他之前的所有元素相比（從右往左），如果滿足排序的順序，這交換。 ...
閱讀 2197·2023-04-25 18:49
閱讀 1902·2019-08-30 14:02
閱讀 2731·2019-08-29 17:24
閱讀 3376·2019-08-28 18:10
閱讀 2987·2019-08-28 18:03
閱讀 558·2019-08-26 12:01
閱讀 3373·2019-08-26 11:31
閱讀 1496·2019-08-26 10:29
