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

2022-12-27 14:01:41

什麼是直接插入排序？

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

演演算法思想

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

②我們把第一個元素看作有序序列，從第二個元素到最後為無序序列。

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

範例講解

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

1、我們將第一個元素3看成已經排序好的序列，即有序序列。

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

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

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

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

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

①待排序元素【38】和有序序列中元素【44】進行比較，【38】比【44】小，則將【44】向後移動，然後在將【38】和【3】進行比較，【38】大於【3】則將元素【38】插入到【3】位置後。

注意： 需要將待排序元素與有序序列中的每一個元素進行比較。

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

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

小結：

待排序元素比有序元素元素大則直接插入到該有序元素後，若小於有序元素則將該有序元素向後移動。

演演算法分析

時間複雜度

O(n2)

空間複雜度

O(1)

穩定性

穩定的排序演演算法，其穩定性在於相同值的元素進行插入排序完成後相對位置不發生改變。

程式碼實現

#include<stdio.h>
void Print(int array[],int len){
	for(int i=0;i<len;i++){
		printf("%d ",array[i]);
	}
	printf("n");
} 
/*直接插入排序*/
/*
*演演算法描述：
*1.將待排序序列分為兩部分，一部分有序一部分無序
*2.第一個元素為有序序列，從第二個元素到最後為無序序列 
*3.將無序序列中每一個元素依次插入到有序序列的合適位置--從小到大（從大到小） 
*合適的位置：待排序元素大於或等於（小於）該元素 
*/ 
void InsertSort(int array[],int len){
	int i,j;
	//第一個for迴圈 遍歷無序序列 
	for(i=1;i<len;i++){  //從陣列的第二個元素開始依次遍歷無序序列 
	 	int tem = array[i];  //臨時儲存將要排序的元素 
	 	//第二個for迴圈遍歷有序序列 
	 	for(j=i-1;tem<=array[j]&&j>=0;j--){  //將待排序元素依次和有序序列中的元素比較 
	 		//待排序元素 小於 有序序列中當前元素時 將該元素後移
	 		array[j+1] = array[j];
	 	}
	array[j+1] = tem;  //待排序元素 大於 有序序列最後一個元素 直接將該元素插入到有序序列最後 
	}
	printf("n排序完成!nn");
}

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);
}