排序是數(shù)據(jù)處理中十分常見(jiàn)且核心的操作躲查，雖說(shuō)實(shí)際項(xiàng)目開(kāi)發(fā)中很小幾率會(huì)需要我們手動(dòng)實(shí)現(xiàn)它浅，畢竟每種語(yǔ)言的類(lèi)庫(kù)中都有n多種關(guān)于排序算法的實(shí)現(xiàn)。但是了解這些精妙的思想對(duì)我們還是大有裨益的镣煮。本文簡(jiǎn)單溫習(xí)下最基礎(chǔ)的三類(lèi)算法：選擇姐霍，冒泡，插入怎静。
簡(jiǎn)單選擇排序
簡(jiǎn)單選擇排序是最簡(jiǎn)單直觀的一種算法邮弹，基本思想為每一趟從待排序的數(shù)據(jù)元素中選擇最星狻（或最大）的一個(gè)元素作為首元素蚓聘，直到所有元素排完為止，簡(jiǎn)單選擇排序是不穩(wěn)定排序盟劫。
在算法實(shí)現(xiàn)時(shí)夜牡，每一趟確定最小元素的時(shí)候會(huì)通過(guò)不斷地比較交換來(lái)使得首位置為當(dāng)前最小，交換是個(gè)比較耗時(shí)的操作侣签。其實(shí)我們很容易發(fā)現(xiàn)塘装，在還未完全確定當(dāng)前最小元素之前，這些交換都是無(wú)意義的影所。我們可以通過(guò)設(shè)置一個(gè)變量min蹦肴，每一次比較僅存儲(chǔ)較小元素的數(shù)組下標(biāo)，當(dāng)輪循環(huán)結(jié)束之后猴娩，那這個(gè)變量存儲(chǔ)的就是當(dāng)前最小元素的下標(biāo)阴幌，此時(shí)再執(zhí)行交換操作即可勺阐。代碼實(shí)現(xiàn)很簡(jiǎn)單，一起來(lái)看下矛双。
private static void sort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int min = i; //每一趟循環(huán)比較時(shí)渊抽，min用于存放較小元素的數(shù)組下標(biāo)，這樣當(dāng)前批次比較完畢最終存放的就是此趟內(nèi)最小的元素的下標(biāo)议忽，避免每次遇到較小元素都要進(jìn)行交換懒闷。
for (int j = i + 1; j < arr.length; j++) {
if (arr[min] > arr[j]) {
min = j;
}
}
//進(jìn)行交換，如果min發(fā)生變化栈幸，則進(jìn)行交換
if (min != i) {
swap(arr, min, i);
}
}
}
private static void swap(int[] arr, int min, int i) {
int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
簡(jiǎn)單選擇排序通過(guò)上面優(yōu)化之后愤估，無(wú)論數(shù)組原始排列如何，比較次數(shù)是不變的速址；對(duì)于交換操作灵疮，在最好情況下也就是數(shù)組完全有序的時(shí)候，無(wú)需任何交換移動(dòng)壳繁，在最差情況下震捣，也就是數(shù)組倒序的時(shí)候，交換次數(shù)為n-1次闹炉。綜合下來(lái)蒿赢，時(shí)間復(fù)雜度為O(n2)
冒泡排序
冒泡排序的基本思想是，對(duì)相鄰的元素進(jìn)行兩兩比較渣触，順序相反則進(jìn)行交換羡棵，這樣，每一趟會(huì)將最小或最大的元素“浮”到頂端嗅钻，最終達(dá)到完全有序
代碼實(shí)現(xiàn)
在冒泡排序的過(guò)程中皂冰，如果某一趟執(zhí)行完畢，沒(méi)有做任何一次交換操作养篓，比如數(shù)組[5,4,1,2,3]秃流，執(zhí)行了兩次冒泡，也就是兩次外循環(huán)之后柳弄，分別將5和4調(diào)整到最終位置[1,2,3,4,5]舶胀。此時(shí)，再執(zhí)行第三次循環(huán)后碧注，一次交換都沒(méi)有做嚣伐，這就說(shuō)明剩下的序列已經(jīng)是有序的，排序操作也就可以完成了萍丐，來(lái)看下代碼
private static void sort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] < arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}
根據(jù)上面這種冒泡實(shí)現(xiàn)轩端，若原數(shù)組本身就是有序的（這是最好情況），僅需n-1次比較就可完成逝变；若是倒序基茵，比較次數(shù)為 n-1+n-2+...+1=n(n-1)/2刻撒，交換次數(shù)和比較次數(shù)等值。所以耿导，其時(shí)間復(fù)雜度依然為O(n2）声怔。綜合來(lái)看，冒泡排序性能還還是稍差于上面那種選擇排序的舱呻。
直接插入排序
直接插入排序基本思想是每一步將一個(gè)待排序的記錄醋火，插入到前面已經(jīng)排好序的有序序列中去，直到插完所有元素為止箱吕。
private static void sort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
for (int j = i; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
swap(arr, j, j-1);
}
}
}
}
簡(jiǎn)單插入排序在最好情況下芥驳，需要比較n-1次，無(wú)需交換元素茬高，時(shí)間復(fù)雜度為O(n);在最壞情況下兆旬，時(shí)間復(fù)雜度依然為O(n2)。但是在數(shù)組元素隨機(jī)排列的情況下怎栽，插入排序還是要優(yōu)于上面兩種排序的丽猬。
總結(jié)
本文列舉了排序算法中最基本的三種算法（簡(jiǎn)單選擇，冒泡熏瞄，插入）脚祟，這三種排序算法的時(shí)間復(fù)雜度均為O(n2)，后續(xù)會(huì)陸續(xù)更新其他更高階一些的排序算法强饮，時(shí)間復(fù)雜度也會(huì)逐步突破O(n2）由桌。
