圖解，C語言數(shù)據(jù)結(jié)構(gòu)，插入排序
之前寫過的排序文章，放上鏈接給大家看看。
高中新生開學(xué)，需要進(jìn)行軍訓(xùn)，軍訓(xùn)的時(shí)候，教官需要大家把按高到低排隊(duì)排好。
先隨機(jī)找到一個(gè)比較帥的男生做排頭。
然后第二個(gè)人過來跟這個(gè)男生比身高，如果比第一個(gè)高，就排到左邊，要不就排到右邊。
然后第三個(gè)人過來了，他需要在原來的兩個(gè)人中找到自己的位置。
……
經(jīng)過把所有的人插入原來的序列，就完成了學(xué)生的身高排序。
—— 定義
插入排序顧名思義就是把未排序的數(shù)字插入到已經(jīng)排序的序列的正確位置。
插入排序在很多文章中也會(huì)寫作直接插入排序。
——?用圖片來舉例子
比如我們需要排序這幾個(gè)數(shù)字
我們首先拿出第一個(gè)數(shù)字6。
然后我們?nèi)〉诙€(gè)數(shù)字和第一個(gè)數(shù)字6進(jìn)行排序，6被認(rèn)為是已經(jīng)排序好的數(shù)列，因?yàn)樗椭挥幸粋€(gè)數(shù)字，當(dāng)然是排序好的了。
5和6排序后，可以得到新的數(shù)列
前面兩個(gè)已經(jīng)是排序好的序列，再拿第三個(gè)序列和前面的序列比較。
然后新排序的序列會(huì)變成這樣
后面的數(shù)字都會(huì)依次插入前面已經(jīng)排序好的序列，得到一個(gè)新的排序好的序列。
整個(gè)過程如下圖
—— 插入排序是否是穩(wěn)定的排序算法？
什么是穩(wěn)定排序？
如果兩個(gè)位置 A[j] == A[k]?相等，我們的排序算法不會(huì)改變 A[j] 和 A[k]的位置，這樣的排序算法就是穩(wěn)定的。
比如下面的序列，我們把數(shù)字5插入到原來的序列中，但是原來的序列中也有一個(gè)數(shù)字5，我們不改變?cè)瓉頂?shù)字的位置，就說明是穩(wěn)定的排序。
—— 代碼實(shí)現(xiàn)
#include???
void?insert_sort(int?arr[],?int?n)
{
????int?i,j,temp;
????/*從第一個(gè)位置開始，1~n-1，依次和前面的數(shù)據(jù)比較*/
????for?(i?=?1;?i?????{
????????/*保存要插入的值*/
????????temp?=?arr[i];
????????/*找到需要插入數(shù)據(jù)的位置*/
????????for?(j?=?i?-?1;?temp?=?0;?--j)
????????{
????????????/*把j位置的數(shù)據(jù)移動(dòng)到j(luò)+1位置，向后移動(dòng)一位*/
????????????arr[j?+?1]?=?arr[j];
????????}
????????/*插入數(shù)據(jù)*/
????????arr[j?+?1]?=?temp;
????}
}
#define?LENGTH?8
int?main()
{
????int?i,j;
????int?arr[LENGTH]?=?{6,5,3,1,8,7,2,4};
????/*排序前*/
????for(i=0;i????????printf("%d?",arr[i]);printf("\n");
????insert_sort(arr,LENGTH);
????/*排序后*/
????for(i=0;i????????printf("%d?",arr[i]);printf("\n");
????return?0;
}
看代碼，是從第 1 位置開始做插入排序的，而且比較是從后往前開始比較。
比如第一個(gè)位置的數(shù)字，需要和第0個(gè)位置開始比較。
如果是第3個(gè)位置，就需要和第2、1、0這三個(gè)位置比較。
—— 代碼輸出
6?5?3?1?8?7?2?4?
1?2?3?4?5?6?7?8?
加上隨機(jī)數(shù)的代碼
#include???
#include??
#include????
void?insert_sort(int?arr[],?int?n)
{
????int?i,j,temp;
????/*從第一個(gè)位置開始，1~n-1，依次和前面的數(shù)據(jù)比較*/
????for?(i?=?1;?i?????{
????????/*保存要插入的值*/
????????temp?=?arr[i];
????????/*找到需要插入數(shù)據(jù)的位置*/
????????for?(j?=?i?-?1;?temp?=?0;?--j)
????????{
????????????/*把j位置的數(shù)據(jù)移動(dòng)到j(luò)+1位置，向后移動(dòng)一位*/
????????????arr[j?+?1]?=?arr[j];
????????}
????????/*插入數(shù)據(jù)*/
????????arr[j?+?1]?=?temp;
????}
}
#define?LENGTH?30
int?main()
{
????int?i,j;
????int?arr[LENGTH]?=?{6,5,3,1,8,7,2,4};
????/*隨機(jī)數(shù)設(shè)置種子*/
????srand((unsigned)time(NULL));
????/*賦值*/
????for(i=0;i????????arr[i]?=?rand()%100;
????/*排序前*/
????for(i=0;i????????printf("%d?",arr[i]);printf("\n");
????insert_sort(arr,LENGTH);
????/*排序后*/
????for(i=0;i????????printf("%d?",arr[i]);printf("\n");
????return?0;
}
—— 代碼輸出
58?90?36?55?5?91?27?56?19?37?69?75?73?24?14?2?40?57?27?86?2?31?6?59?23?92?16?10?62?92?
2?2?5?6?10?14?16?19?23?24?27?27?31?36?37?40?55?56?57?58?59?62?69?73?75?86?90?91?92?92?
—— 算法復(fù)雜度
老王帶你理解算法復(fù)雜度O(1),O(N),O(N^2)
時(shí)間復(fù)雜度和空間復(fù)雜度，一看就懂，面試前必過一遍
兩個(gè)循環(huán)遍歷，算法時(shí)間復(fù)雜度是?O(N^2)
