C語言中的直接插入排序(帶圖詳細(xì))

更新時(shí)間：2022年12月27日 09:07:28 作者：小陳沒煩惱

這篇文章主要介紹了C語言中的直接插入排序(帶圖詳細(xì))，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教

什么是直接插入排序？

直接插入排序是一種最簡單的排序方法，其基本操作是將需要排序的元素插入到已排好的有序表序列中，從而得到一個(gè)完整的有序序列。

算法思想

①將待排序序列分為兩部分，一部分有序一部分無序。

②我們把第一個(gè)元素看作有序序列，從第二個(gè)元素到最后為無序序列。

③將無序序列中每一個(gè)元素依次插入到有序序列的合適位置–從小到大（從大到?。?。

小陳沒煩惱

實(shí)例講解

我們有一個(gè)待排序序列為【3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48】

1、我們將第一個(gè)元素3看成已經(jīng)排序好的序列，即有序序列。

2、從第二個(gè)元素44到最后一個(gè)元素48我們看作為無序的的序列，即待排序的序列。

3、我們將待排序序列中的第一個(gè)元素【44】，插入到有序序列中。

①待排序元素【44】和有序序列中元素【3】進(jìn)行比較，【44】比【3】大則直接插入到有序序列中。

②此時(shí)有序序列為【3,44】，待排序序列為【38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48】

3、我們將待排序序列中的第一個(gè)元素【38】，插入到有序序列中。

①待排序元素【38】和有序序列中元素【44】進(jìn)行比較，【38】比【44】小，則將【44】向后移動(dòng)，然后在將【38】和【3】進(jìn)行比較，【38】大于【3】則將元素【38】插入到【3】位置后。

注意： 需要將待排序元素與有序序列中的每一個(gè)元素進(jìn)行比較。

②此時(shí)有序序列為【3,38,44】，待排序序列為【 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48】

4、然后按照以上操作，將待排序序列中的元素依次插入到有序列中。

小結(jié)：

待排序元素比有序元素元素大則直接插入到該有序元素后，若小于有序元素則將該有序元素向后移動(dòng)。

算法分析

時(shí)間復(fù)雜度

O(n2)

空間復(fù)雜度

O(1)

穩(wěn)定性

穩(wěn)定的排序算法，其穩(wěn)定性在于相同值的元素進(jìn)行插入排序完成后相對(duì)位置不發(fā)生改變。

代碼實(shí)現(xiàn)

#include<stdio.h>
void Print(int array[],int len){
	for(int i=0;i<len;i++){
		printf("%d ",array[i]);
	}
	printf("\n");
} 
/*直接插入排序*/
/*
*算法描述：
*1.將待排序序列分為兩部分，一部分有序一部分無序
*2.第一個(gè)元素為有序序列，從第二個(gè)元素到最后為無序序列 
*3.將無序序列中每一個(gè)元素依次插入到有序序列的合適位置--從小到大（從大到?。?
*合適的位置：待排序元素大于或等于（小于）該元素 
*/ 
void InsertSort(int array[],int len){
	int i,j;
	//第一個(gè)for循環(huán) 遍歷無序序列 
	for(i=1;i<len;i++){  //從數(shù)組的第二個(gè)元素開始依次遍歷無序序列 
	 	int tem = array[i];  //臨時(shí)保存將要排序的元素 
	 	//第二個(gè)for循環(huán)遍歷有序序列 
	 	for(j=i-1;tem<=array[j]&&j>=0;j--){  //將待排序元素依次和有序序列中的元素比較 
	 		//待排序元素 小于 有序序列中當(dāng)前元素時(shí) 將該元素后移
	 		array[j+1] = array[j];
	 	}
	array[j+1] = tem;  //待排序元素 大于 有序序列最后一個(gè)元素 直接將該元素插入到有序序列最后 
	}
	printf("\n排序完成!\n\n");
}

main(){ 
	int array[10] = {4,3,10,5,6,7,1,2,8,9} ;
	int len = sizeof(array) / sizeof(int);
	printf("初始序列：\n");
	Print(array,len);
	InsertSort(array,len);
	printf("排序后序列：\n");
	Print(array,len);
}