1.冒泡排序
2.選擇排序
3.插入排序
4.快速排序
5.堆排序
6.希爾排序
7.歸并排序
8.計數(shù)排序
9.桶排序
10.基數(shù)排序
該篇排序方式：由小到大排序
1.冒泡排序
從后向前冒泡
從前向后冒泡
由小到大，從后向前冒泡：[90饱岸，78吹榴，65祟敛，43望薄，20]
一次冒泡
第一次比較：[90槽驶，78握侧，65蚯瞧，20，43] 一次交換操作
第二次比較：[90品擎，78埋合，20，65萄传，43] 一次交換操作
第三次比較：[90甚颂，20，78秀菱，65振诬，43] 一次交換操作
第四次比較：[20，90衍菱，78赶么，65，43] 一次交換操作
二次冒泡
第一次比較：[20脊串，90辫呻，78，43琼锋，65] 一次交換操作
第二次比較：[20印屁，90，43斩例，78雄人，65] 一次交換操作
第三次比較：[20，43，90础钠，78恰力，65] 一次交換操作
三次冒泡
第一次比較：[20，43旗吁，90踩萎，65，78] 一次交換操作
第二次比較：[20很钓，43香府，65，90码倦，78] 一次交換操作
四次冒泡
第一次比較：[20企孩，43，65袁稽，78勿璃，90] 一次交換操作
共十次交換操作
1.最后一個元素與相鄰元素對比
2.小于相鄰元素，則交換
3.大于等于相鄰元素推汽，無需交換补疑，繼續(xù)相鄰元素的對比
4.直到與最左邊的元素對比完成，一次冒泡結束
5.對剩下的序列歹撒，重復1~4的步驟
6.直到剩下的序列長度為1莲组，整個冒泡結束
1.不使用遞歸實現(xiàn)
/**
* 冒泡排序
*
* 由小到大排序
*
* 從后向前冒泡
*
* @param arr
*/
public void bubbleSort(int[] arr) {
if (arr == null || arr.length == 0)
return;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = arr.length - 1; j > i; j--) {
if (arr[j] < arr[j - 1]) {
swap(arr, j - 1, j);
}
}
}
}
public void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
2.使用遞歸方式實現(xiàn)
/**
*
*冒泡排序函數(shù)
*/
public void sortByBubble(int[] paramInts) {
sortByBubble(paramInts, 0);
}
/**
*
*冒泡排序的輔助方法
*paramInts:排序的數(shù)組對象
*index:序列最左邊下標
*/
private void sortByBubble(int[] paramInts, int index) {
if (index == paramInts.length - 1) {
return;
}
for (int i = paramInts.length - 1; i > index; i--) {
if (paramInts[i] < paramInts[i - 1]) {
int tempValue = paramInts[i];
paramInts[i] = paramInts[i - 1];
paramInts[i - 1] = tempValue;
}
}
sortByBubble(paramInts, index + 1);
}
從前向后冒泡
1.第一個元素與相鄰的元素對比
2.小于相鄰元素，則交換
3.大于等于相鄰元素暖夭，無需交換胁编，繼續(xù)相鄰元素的對比
4.直到與最右邊元素對比完成，一次冒泡結束
5.對剩下的序列鳞尔，重復1~4的步驟
6.直到剩下的序列長度為1，完成整個數(shù)組的冒泡
1.一次冒泡過程不使用遞歸實現(xiàn)
public void sortByBubble(int[] paramInts) {
sortByBubble(paramInts, paramInts.length - 1);
}
/**
*
*由前向后冒泡排序的輔助方法
*paramInts:排序數(shù)組對象
*index:序列最右邊的下標
*/
private void sortByBubble(int[] paramInts, int index) {
if (index == 0) {//沒有可冒泡的序列了
return;
}
for (int i = 0; i < index; i++) {
if (paramInts[i + 1] > paramInts[i]) {//小于相鄰元素
//與相鄰元素交換
int tempValue = paramInts[i];
paramInts[i] = paramInts[i + 1];
paramInts[i + 1] = tempValue;
}
}
sortByBubble(paramInts, index - 1);
}
2.一次冒泡過程使用遞歸代替for語句實現(xiàn)
/**
*
*冒泡排序
*
*使用遞歸方法實現(xiàn)
*/
private void sortByBubblinf(int[] paramInts) {
sortByBubbling(paramInts, 0, paramInts.length - 1);
}
/**
*
*冒泡排序遞歸實現(xiàn)的輔助方法
*paramInts:排序的數(shù)組對象
*index:對比到元素的下標
*minInex:序列最右邊元素下標
*/
private void sortByBubbling(int[] paramInts, int index, int minIndex) {
if (minIndex == 0) {//左邊沒有可對比的相鄰元素
return;
} else if (index == minIndex) {//沒有可對比的元素
//重復1~5步驟
sortByBubbling(paramInts, 0, minIndex - 1);
} else if (paramInts[index] < paramInts[index + 1]) {
//小于相鄰元素早直，與相鄰元素交換
int temp = paramInts[index];
paramInts[index] = paramInts[index + 1];
paramInts[index + 1] = temp;
sortByBubbling(paramInts, index + 1, minIndex);
} else {
//大于等于相鄰元素寥假，重復步驟1~3
sortByBubbling(paramInts, index + 1, minIndex);
}
}
介紹完冒泡排序，講解一下冒泡的時間復雜度
冒泡排序的時間復雜度為O(n^2)
時間復雜度
計算方法
1.一般情況下霞扬，算法中基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)糕韧，用T(n)表示，若有某個輔助函數(shù)f(n),使得當n趨近于無窮大時喻圃，T(n)/f(n)的極限值為不等于零的常數(shù)萤彩，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=O(f(n)),稱O(f(n)) 為算法的漸進時間復雜度斧拍，簡稱時間復雜度雀扶。
分析：隨著模塊n的增大，算法執(zhí)行的時間的增長率和 f(n) 的增長率成正比，所以 f(n) 越小愚墓，算法的時間復雜度越低予权，算法的效率越高。
冒泡排序的時間復雜度計算過程：
冒泡排序是一種用時間換空間的排序方法浪册，最壞情況是把順序的排列變成逆序扫腺，或者把逆序的數(shù)列變成順序。
在這種情況下村象，每一次比較都需要進行交換運算笆环。
舉個例子來說，一個數(shù)列 5 4 3 2 1 進行冒泡升序排列厚者，
第一次大循環(huán)從第一個數(shù)（5）開始到倒數(shù)第二個數(shù)（2）結束躁劣，
比較過程：先比較5和4，4比5小籍救，交換位置變成4 5 3 2 1习绢；
比較5和3，3比5小蝙昙，交換位置變成4 3 5 2 1
……
最后比較5和1闪萄，1比5小，交換位置變成4 3 2 1 5奇颠。
這時候共進行了4次比較交換運算败去，最后1個數(shù)變成了數(shù)列最大數(shù)。
第二次大循環(huán)從第一個數(shù)（4）開始到倒數(shù)第三個數(shù)（2）結束烈拒。進行3次比較交換運算圆裕。
……
所以總的比較次數(shù)為 4 + 3 + 2 + 1 = 10次對于n位的數(shù)列則有比較次數(shù)為 (n-1) + (n-2) + ... + 1 = n * (n - 1) / 2，這就得到了最大的比較次數(shù)而O(N^2)表示的是復雜度的數(shù)量級荆几。
舉個例子來說吓妆，如果n = 10000，那么 n(n-1)/2 = (n^2 - n) / 2 = (100000000 - 10000) / 2吨铸，相對10^8來說行拢，10000小的可以忽略不計了，所以總計算次數(shù)約為0.5 * N2诞吱。用O(N2)就表示了其數(shù)量級（忽略前面系數(shù)0.5）舟奠。
2.選擇排序
[90，78房维，65沼瘫，43，20]
一次選擇[20, 78, 65, 43, 90] 一次交換操作
二次選擇:[20, 43, 65, 78, 90] 一次交換操作
三次選擇:[20, 43, 65, 78, 90] 0次交換操作
四次選擇:[20, 43, 65, 78, 90] 0次交換操作
共兩次交換操作
1.查找序列中的最小元素與序列最左邊元素交換
2.剩下的序列中咙俩，重復1步驟
3.直到序列的長度為1耿戚，完成排序
/**
*選擇排序
*/
public void sortByCulling(int[] paramInts) {
sortByCulling(paramInts, 0);
}
/**
*選擇排序輔助方法
*paramInts:排序的數(shù)組對象
*index:序列最左邊元素的下標
*
*/
private void sortByCulling(int[] paramInts, int index) {
if (index == paramInts.length - 1) {
return;
}
//查詢序列中的最小元素
int tempIndex = index;
int tempValue = paramInts[tempIndex];
//掃描序列中的元素
for (int i = index + 1; i < paramInts.length; i++) {
if ( paramInts[i] < tempValue) {//找到更小的元素
//記錄下最小元素及下標
tempValue = paramInts[i];
tempIndex = i;
}
}
//掃描完序列
//判斷最小元素是否是序列最左邊的元素
if (tempIndex != index) {//不是
//交換元素
paramInts[tempIndex] = paramInts[index];
paramInts[index] = tempValue;
}
//調(diào)用函數(shù)本身
sortByCulling(paramInts, index + 1);
}
3.插入排序
[90，78，65溅话，43晓锻，20]
一次插入
[78, 90, 65, 43, 20] 一次交換操作
二次插入
[78, 65, 90, 43, 20] 一次交換操作
[65, 78, 90, 43, 20] 一次交換操作
三次插入
[65, 78, 43, 90, 20] 一次交換操作
[65, 43, 78, 90, 20] 一次交換操作
[43, 65, 78, 90, 20] 一次交換操作
四次插入:
[43, 65, 78, 20, 90] 一次交換操作
[43, 65, 20, 78, 90] 一次交換操作
[43, 20, 65, 78, 90] 一次交換操作
[20, 43, 65, 78, 90] 一次交換操作
共十次交換操作
1.從第一個元素開始，該元素認定為已經(jīng)被排序
2.取出下一個元素與已經(jīng)排序的元素從后向前依次對比
3.如果取出的元素小與對比的元素飞几，則交換
4.直到大于等于對比的元素則停止
5.重復2~4的步驟
6.直到?jīng)]有可取出的元素為止
/**
*插入排序函數(shù)
*
*/
public void sortByInsertionCulling (int[] paramInts) {
sortByInsertionCulling(paramInts, 1);
}
/**
*插入排序輔助方法
*paramInts:排序數(shù)組對象
*index:取出元素的下標
*/
private void sortByInsertionCulling(int[] paramInts, int index) {
if (index == paramInts.length) {//取出元素的下標已經(jīng)超出數(shù)組的長度砚哆，已經(jīng)沒有可取的元素
return;
}
//取出下標為index的元素
int tempValue = paramInts[index];
//記錄取出元素的下標
int tempIndex = index;
//取出的元素與已經(jīng)排序的元素從后向前依次對比
for (int i = index - 1; i >= 0; i--) {
if (tempValue < paramInts[i]) {//取出的元素小于當前元素
//與當前元素交換
paramInts[tempIndex] = paramInts[i];
paramInts[i] = tempValue;
tempIndex = i;
} else {//小于等于取出的元素
//停止對比
break;
}
}
//重復2~4步驟，調(diào)用函數(shù)本身
sortByInsertionCulling(paramInts, index + 1);
}
快速排序
基本思想是：通過一趟排序將要排序的數(shù)據(jù)分割成獨立的兩部分屑墨，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小躁锁，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行卵史，以此達到整個數(shù)據(jù)變成有序序列
[90战转，78，65以躯，43槐秧，20]
一趟快速排序
[20, 78, 65, 43, 90] 一次交換操作
兩趟快速排序
[20, 78, 65, 43, 90] 0次交換操作
三趟快速排序
[20, 43, 65, 78, 90] 一次交換操作
四趟快速排序
[20, 43, 65, 78, 90] 0次交換操作
共兩次交換操作
參考文章一
參考文章二
