在開始學(xué)習(xí)排序前我們需要明白如下幾個知識點：
1.時間復(fù)雜度：一個算法執(zhí)行所需要的時間；
2.空間復(fù)雜度：運行完一個算法的過程需要的內(nèi)存大小；
3.穩(wěn)定性：穩(wěn)定的排序，如果待排序的序列中肋拔，之前有a,b兩個元素并且a=b，在經(jīng)過了排序算法后呀酸，a元素的位置依然在b元素的前方這種排序算法是穩(wěn)定的凉蜂；反之這種排序就不穩(wěn)定；
4.內(nèi)排序：所有的排序算法都在內(nèi)存中完成性誉；
5.外排序：待排序的數(shù)據(jù)非常巨大窿吩，因此需要將數(shù)據(jù)放在磁盤中，在排序過程中需要需要通過磁盤和內(nèi)存數(shù)據(jù)的交換才能進(jìn)行
冒泡排序
冒泡排序?qū)儆诜€(wěn)定排序错览，算法的最佳時間復(fù)雜度為O(n),最差的數(shù)據(jù)復(fù)雜度為O(n2)纫雁，所以時間復(fù)雜度為O(n2)；同時它屬于交換排序倾哺，具體思路為：第一次比較從第一個元素起轧邪，依次比較相鄰的兩個元素，如比較第一個元素和第二個元素羞海，如果第一個元素大于第二個元素則交換忌愚，依次重復(fù)上述操作，在進(jìn)行完第一輪兩兩比較后最大的元素在最后一個位置却邓，再進(jìn)行上述操作硕糊，次大的元素在數(shù)組的倒數(shù)第二個位置；
實現(xiàn)代碼如下：
/**
* 冒泡排序
*/
public class BubblingSort {
public void applyOptimize(int[] value) {
if (value ==null || value.length ==0) {
System.out.println("value is null ---------->");
return;
? ? ? ? }
int indexOne, indexTwo, tempValue;
? ? ? ? for (indexOne = value.length -1; indexOne >0; indexOne--) {
for (indexTwo =0; indexTwo < indexOne; indexTwo++) {
if (value[indexTwo] > value[indexTwo+1]) {
tempValue = value[indexTwo];
? ? ? ? ? ? ? ? ? ? value[indexTwo] = value[indexTwo+1];
? ? ? ? ? ? ? ? ? ? value[indexTwo+1] = tempValue;
? ? ? ? ? ? ? ? }
}
}
}
}
可以從幾個方面優(yōu)化冒泡排序算法
1.設(shè)置一個標(biāo)記變量，如果在某一輪兩兩比較過程中简十，沒有發(fā)生元素交換說明數(shù)組已經(jīng)排好序了檬某，算法運算結(jié)束；
public void applyOptimize(int[] value) {
if (value ==null || value.length ==0) {
System.out.println("value is null ---------->");
return;
? ? }
boolean isChange =false;
? ? int indexOne, indexTwo, tempValue;
? ? for (indexOne = value.length -1; indexOne >0; indexOne--) {
isChange =false;
? ? ? ? for (indexTwo =0; indexTwo < indexOne; indexTwo++) {
if (value[indexTwo] > value[indexTwo+1]) {
tempValue = value[indexTwo];
? ? ? ? ? ? ? ? value[indexTwo] = value[indexTwo+1];
? ? ? ? ? ? ? ? value[indexTwo+1] = tempValue;
? ? ? ? ? ? ? ? isChange =true;
? ? ? ? ? ? }
}
if(!isChange){
return;
? ? ? ? }
}
}
