直接插入排序的平均復(fù)雜度是 /(O(n^2)/)，因此應(yīng)用場(chǎng)景較少。
直接插入排序的思路是： 每次處理一個(gè)數(shù)據(jù)，將其插入到一個(gè)已經(jīng)排好序的子序列中，直到數(shù)據(jù)處理完畢。
下面給出一個(gè)動(dòng)畫示例：
從上面來(lái)看我們也可以發(fā)現(xiàn)一些優(yōu)點(diǎn)：
（1） 實(shí)現(xiàn)簡(jiǎn)單，比其它 /(O(n^2)/) 排序算法高效； （2） 當(dāng)數(shù)據(jù)已經(jīng)基本有序時(shí)，效率較高； （3） 排序穩(wěn)定，并且需要的額外存儲(chǔ)空間??； （4） 可以快速處理新增加的數(shù)據(jù)；
參照動(dòng)畫我們可以很容易的理解下面的c++代碼：
void insertsort (int data[], int n){ int j, temp; // 外層循環(huán)負(fù)責(zé)依次處理每一個(gè)元素（忽略第一個(gè)） for (int i = 1; i < n; i++){ j = i; // 內(nèi)層循環(huán)負(fù)責(zé)移動(dòng)數(shù)據(jù)直到找到插入的位置 while (j > 0 && data[j] < data[j-1]){ temp = data[j]; data[j] = data[j-1]; data[j-1] = temp; j--; } }}未完待續(xù)。。。。
參考資料：
（1）WIKI：https://en.wikipedia.org/wiki/Insertion_sort
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
