相關(guān)文章
算法（一）時(shí)間復(fù)雜度
前言
排序是算法的基礎(chǔ)，排序有很多種方法，有些方法實(shí)現(xiàn)起來(lái)很簡(jiǎn)單，但是效率較差，我們可以將這些排序的方法稱(chēng)之為初等排序。這篇文章我們就來(lái)學(xué)習(xí)初等排序中的插入排序和冒泡排序。
1.插入排序
插入排序比較容易想到，思路與打撲克時(shí)排列牌的順序是類(lèi)似的。比如我們左手拿牌，然后用右手將牌從左到右，從小到大來(lái)排序，這就需要我們把需要進(jìn)行排列的牌抽出來(lái)放到合適的位置，并且不斷的重復(fù)，直到牌的順序排好，這個(gè)過(guò)程就可以理解為插入排序。
圖解插入排序
插入排序過(guò)程中會(huì)將需要排序的數(shù)組，分為兩個(gè)部分：已排序部分和未排序部分，如下圖所示。
從圖中可以看出這個(gè)數(shù)組分為兩個(gè)部分，其中下標(biāo)為0、1、2的元素為已排列部分，其余的則為未排列部分。
插入的排序規(guī)則：
將開(kāi)頭元素視為以排序部分。接著執(zhí)行如下的處理，直到?jīng)]有未排序部分。
- 取出未排序部分的開(kāi)頭元素賦值給臨時(shí)保存數(shù)據(jù)的變量v。
- 在已排列的部分將所有比v大的元素向后移動(dòng)一個(gè)位置。
- 將取出的元素v插入空位。
按照這個(gè)規(guī)則，我們來(lái)舉一個(gè)簡(jiǎn)單的例子。我們對(duì)數(shù)組 a={8,3,1,5,2,1} 進(jìn)行從小到大排序，數(shù)組a如下圖所示。
我們對(duì)數(shù)組a進(jìn)行排序，共需要5個(gè)步驟：
1.接著我們將a[0]=8視為已排序，我們從a[1]開(kāi)始操作，將a[1]的值3取出，3要小于a[0]的值8，因此將a[0]的值8移動(dòng)到a[1]，再把3插入到a[0]，如下圖所示。
2.a[2]的值1要比a[0]和a[1]的值要小，則將a[0]和a[1]順次向后移一個(gè)位置，然后將1插入a[0]，如下圖所示。
3.將a[3]中的5拿出來(lái)，比它大的是a[2]的8，因此8向后移，將5插入a[3]。如下圖所示。
4.將a[4]中2拿出來(lái)，發(fā)現(xiàn)a[1]、a[2]、a[3]中的值都比2大，因此將它們依次向后移，將2插入到a[1]中，如下圖所示。
5.最后將a[5]中的1移到合適的位置，過(guò)程和上面一樣，最后的排序結(jié)果如下圖所示。
實(shí)現(xiàn)插入排序
接下來(lái)要實(shí)現(xiàn)插入排序，針對(duì)下圖來(lái)定義變量。
如上圖所示，i代表未排序部分的開(kāi)頭元素，v是臨時(shí)保存a[i]值的變量， j代表已排序部分v要插入的位置。
根據(jù)定義的這三個(gè)變量，插入排序的實(shí)現(xiàn)思路就是：外層循環(huán)i從1開(kāi)始自增，并在每次循環(huán)開(kāi)始時(shí)將a[i]的值保存在v中；內(nèi)層循環(huán)則是j從i-1開(kāi)始向前自減，并將比v大的元素從a[j]移動(dòng)到a[j+1]，并將v插入到當(dāng)前j+1的位置（內(nèi)層循環(huán)后j會(huì)先自減1，因此插入的地方則是j+1的位置），當(dāng)j等于-1或者a[j]小于等于v則內(nèi)層循環(huán)結(jié)束。
接下來(lái)我們用代碼來(lái)實(shí)現(xiàn)插入排序，如下所示。
public class InsertSort {
public static void main(String[] args) {
int a[] = {8, 3, 1, 5, 2, 1};
ArrayUtils.printArray(a);
int b[] = insert(a);
ArrayUtils.printArray(b);
}
public static int[] insert(int[] a) {
int i, j, v;
int n = a.length;
for (i = 1; i < n; i++) {
v = a[i];
j = i - 1;
while (j >= 0 && a[j] > v) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = v;
}
return a;
}
}
其中負(fù)責(zé)打印數(shù)組的ArrayUtils類(lèi)如下所示。
public class ArrayUtils {
public static void printArray(int[] array) {
System.out.print("{");
int len=array.length;
for (int i = 0; i < len; i++) {
System.out.print(array[i]);
if (i < len - 1) {
System.out.print(", ");
}
}
System.out.println("}");
}
}
輸出結(jié)果為：
{8, 3, 1, 5, 2, 1}
{1, 1, 2, 3, 5, 8}
插入排序的復(fù)雜度
根據(jù)算法（一）時(shí)間復(fù)雜度所講的，我們來(lái)算一下插入排序的時(shí)間復(fù)雜度。在最壞的情況下，每個(gè)i循環(huán)都需要執(zhí)行i次移動(dòng)，總共需要1+2+......+n-1=n2/2+n/2，根據(jù)此前講過(guò)的推導(dǎo)大O階的規(guī)則的我們得出插入排序的時(shí)間復(fù)雜度為O(n2)。
2.冒泡排序
冒泡排序應(yīng)該是開(kāi)發(fā)者最容易理解的排序算法，它的基本思想就是每次比較兩個(gè)相鄰的元素，如果它們的順序錯(cuò)誤就把它們交換過(guò)來(lái)。需要進(jìn)行排序的元素則向水中的氣泡一樣慢慢的移向水面。
圖解冒泡排序
與插入排序一樣，需要進(jìn)行冒泡排序的數(shù)組也分為已排序部分和未排序部分。
冒泡排序的規(guī)則為：從數(shù)組末尾開(kāi)始依次比較相鄰的兩個(gè)元素，如果大小關(guān)系相反則交換位置，直到數(shù)組中不再有順序相反的相鄰元素。
我們對(duì)數(shù)組 a={5,3,2,4,1} 進(jìn)行從小到大排序，排序過(guò)程如下所示。
第一輪排序：
我們將數(shù)組末尾的a[4]的值和a[3]的值進(jìn)行對(duì)比，發(fā)現(xiàn)a[4]的值比a[3]的值小，則將它們交換，再接著對(duì)剩下的相鄰的兩個(gè)元素進(jìn)行對(duì)比和交換，最終得到的結(jié)果為a={1,5,3,2,4}，已排序的部分的元素為1。
第二輪排序：
首先對(duì)比a[3]和a[4]的值，發(fā)現(xiàn)a[3]的值比a[4]的值小，則不需要進(jìn)行排序。最終得到的結(jié)果為a={1,2,5,3,4}，已排序部分的元素為1、2。
第三輪排序：
經(jīng)過(guò)第三輪排序，已排序部分的元素為1、2、3。
第四輪排序：
經(jīng)過(guò)四輪排序我們最終得到的結(jié)果為a={1,2,3,4,5}
實(shí)現(xiàn)冒泡排序
實(shí)現(xiàn)插入排序時(shí)，我們要先定義兩個(gè)變量，i為循環(huán)變量，表示未排序部分的開(kāi)頭元素，從數(shù)組開(kāi)頭向末尾移動(dòng)。j也為循環(huán)變量，用于對(duì)未排序部分中相鄰元素兩兩比較，從數(shù)組的末尾n-1開(kāi)始減小到 i 結(jié)束(i=1)。
代碼實(shí)現(xiàn)如下所示。
public class BubbleSort {
public static void main(String[] args) {
int a[] = {5, 3, 2, 4, 1};
ArrayUtils.printArray(a);
int b[] = bubble(a);
ArrayUtils.printArray(b);
}
public static int[] bubble(int[] a) {
int i, j, v;
int n = a.length;
for (i = 1; i <= n - 1; i++) {
for (j = n - 1; j >= i ; j--) {
if (a[j] < a[j - 1]) {
v = a[j];
a[j] = a[j - 1];
a[j - 1] = v;
}
}
}
return a;
}
}
其中ArrayUtils的printArray方法此前講過(guò)，這里就不再給出，打印結(jié)果為：
{5, 3, 2, 4, 1}
{1, 2, 3, 4, 5}
冒泡排序的復(fù)雜度
最壞的情況下，冒泡排序?qū)ξ磁判虿糠值南噜徳剡M(jìn)行了(n-1)+(n-2)+(n-3)+……+1次比較，也就是n2/2+n/2次比較，根據(jù)推導(dǎo)大O階的規(guī)則我們得出冒泡排序的時(shí)間復(fù)雜度為O(n2)。
歡迎關(guān)注我的微信公眾號(hào)，第一時(shí)間獲得博客更新提醒，以及更多成體系的Android相關(guān)技術(shù)干貨。
掃一掃下方二維碼即可關(guān)注：
