手把手教你排序算法怎么寫

今天以直接插入排序算法，給大家分享一下排序算法的實(shí)現(xiàn)思路，主要包含以下部分內(nèi)容：

插入排序介紹

插入排序算法實(shí)現(xiàn)

手把手教你排序算法怎么寫

在添加新的記錄時(shí)，使用順序查找的方式找到其要插入的位置，然后將新記錄插入。

以{3,0,9,8,2}無序表按升序排列為例,有序表是一個(gè)虛擬的順序表：
1. 插入排序剛開始，有序表中沒有數(shù)據(jù)，因此直接插入3即可。{3}

2. 插入0的時(shí)候要和有序表中記錄3進(jìn)行比較，0 <3,插入到3的左側(cè)。{0,3}

3. 插入9的時(shí)候，要和有序表中的記錄3進(jìn)行比較，9 > 3 插入到3的右側(cè){0,3,9}

4. 插入8的時(shí)候，要和有序表中的9進(jìn)行比較，9 > 8 8>3因此添加到 9和3之間{0,3,8,9}

5. 插入2的時(shí)候，要和有序表中的 9 8 3 0依次比較，確定2位于0和3之間{0,2,3,8,9}

分析：1、先寫框架2、實(shí)現(xiàn)排序邏輯3、驗(yàn)證調(diào)整代碼

2.1先寫框架-我的預(yù)期

這是一段整理思路的過程。

int a[] = {3,0,9,8,2};int size = sizeof(a) / sizeof(int);int i;for(i=0;i{ printf("%d ",a[i]);}printf("\n"); // 傳遞整型數(shù)據(jù)和長(zhǎng)度進(jìn)去，對(duì)數(shù)據(jù)進(jìn)行排序insertSort(a,size);
for(i=0;i{ printf("%d ",a[i]);}

預(yù)期效果：// 3 0 9 8 2// 0 2 3 8 9

2.2函數(shù)聲明

函數(shù)三要素：insertSort函數(shù)功能：實(shí)現(xiàn)對(duì)傳入數(shù)組的排序形參：數(shù)組，數(shù)組長(zhǎng)度返回值：直接在原有數(shù)組中進(jìn)行排序即可，無需返回值。
先寫函數(shù)聲明

void insertSort(int a[],int size){ // ......}

2.3實(shí)現(xiàn)排序邏輯1、尋找突破口按照直接插入排序的規(guī)則，需要對(duì)下標(biāo)為1以后的每一個(gè)數(shù)據(jù)進(jìn)行插入排序，先獲取到下標(biāo)為1之后的每一個(gè)數(shù)據(jù)。

void insertSort(int a[],int size){ int i; int j; for(i=1;i { // a[i] 從下標(biāo)為1開始，每循環(huán)一次向后獲取到一個(gè)數(shù)據(jù)。
} }

2、尋找排序規(guī)律// 使用當(dāng)前a[i]值和i下標(biāo)前面的每一個(gè)數(shù)值進(jìn)行比較// 如果 a[i-1] > a[i] a[i] = a[i-1] -- a[i]這個(gè)數(shù)據(jù)空間值可能被覆蓋掉，// 下面可能還要多次使用到該數(shù)據(jù)，// 因此可以將這個(gè)數(shù)據(jù)保存下來。// 繼續(xù)如果 a[i-2] > a[i] a[i-1] = a[i-2]//.....// 如果 a[i-j] < a[i] a[i-j+1] = a[i] --結(jié)束本次比較 ，a[i]已經(jīng)找到它所在的位置了
// 考慮邊界// i-j最小值為0，下標(biāo)不能越界3、偽代碼描述先將a[i]的值存起來到變量val里面開始循環(huán)比較 j,1<=j<=i(滿足i-j最小值為0),每次增加1，保證下標(biāo)連續(xù)比較a[i-j]和val的值
如果a[i-j] > val,a[i-j]需要向后移動(dòng)，即a[i-j-1] = a[i-j] 如果a[i-j] <= val;val可以直接放在a[i-j+1]的位置，即a[i-j-1] = val;結(jié)束本次循環(huán)，進(jìn)入下一個(gè)數(shù)的插入排序。
4、代碼實(shí)現(xiàn)

void insertSort(int a[],int size){ int i; int j; for(i=1;i { int val = a[i]; for(j=1;j<=i;j++) { if(a[i-j] <= val) { // 找到val坐在的位置了 a[i-j+1] = val; break; } else { a[i-j+1] = a[i-j]; }?
} } }

5、驗(yàn)證代碼

出錯(cuò)：沒有達(dá)到預(yù)期，即邏輯存在缺陷

6、排查錯(cuò)誤

排查錯(cuò)誤的時(shí)候，可以將比較的次數(shù)和每次比較后數(shù)組中的結(jié)果打印出來，進(jìn)行排查。

因?yàn)閿?shù)組打印要遍歷，為了不影響其他循環(huán)變量的值，可以在聲明一個(gè)變量。

從結(jié)果上看，第一次的0沒有插入成功，按照邏輯走一遍，發(fā)現(xiàn)i=1,j=1,0<3因此3向后移動(dòng)一步，然后j=2,循環(huán)結(jié)束了。
也就是意味著，如果當(dāng)前這個(gè)數(shù)是數(shù)組中的最小的數(shù)，應(yīng)該放在下標(biāo)為0的這一步操作沒有做。
7、修正代碼

void insertSort(int a[],int size){ int i; int j; for(i=1;i { int val = a[i]; for(j=1;j<=i;j++) { if(a[i-j] <= val) { // 找到val坐在的位置了 a[i-j+1] = val; break; } else { a[i-j+1] = a[i-j];
// 如果當(dāng)前a[i]是這個(gè)數(shù)組中最小的元素， // 交換位置后，只剩下0下標(biāo)的位置了,需要將數(shù)據(jù)插入到0的位置上。 if(i-j == 0){ a[i-j] = val; } }
}
} }

運(yùn)行代碼：

本篇內(nèi)容旨在幫助初學(xué)者整理寫算法代碼思路。