作者主頁(yè)：paper jie的博客_CSDN博客-C語(yǔ)言,算法詳解領(lǐng)域博主

本文作者：大家好，我是paper jie，感謝你閱讀本文，歡迎一建三連哦。

本文錄入于《算法詳解》專欄，本專欄是針對(duì)于大學(xué)生，編程小白精心打造的。筆者用重金(時(shí)間和精力)打造，將算法基礎(chǔ)知識(shí)一網(wǎng)打盡，希望可以幫到讀者們哦。

其他專欄：《系統(tǒng)解析C語(yǔ)言》《C語(yǔ)言》《C語(yǔ)言-語(yǔ)法篇》

內(nèi)容分享：本期將對(duì)八大排序中的直接插入排序進(jìn)行詳細(xì)的講解，各位看官姥爺快搬好小板凳坐好叭。

? ? -------- 不要998，不要98，只要一鍵三連，三連買不了吃虧，買不了上當(dāng)

目錄

前言

什么是直接插入排序

直接插入排序的實(shí)現(xiàn)

基本思想

具體代碼

直接插入排序的原理

直接插入排序的特點(diǎn)和性能

復(fù)雜度?

穩(wěn)定性

二分查找代碼的應(yīng)用

前言

上期我們對(duì)快速排序進(jìn)行了分析，了解了它的思想，原理和實(shí)現(xiàn)代碼及它的特性。今天我們來(lái)了解一下插入排序中的直接插入排序。

什么是直接插入排序

插入排序，一般也被稱為直接插入排序。對(duì)于少量元素的排序，它是一個(gè)有效的算法?。插入排序是一種最簡(jiǎn)單的排序方法，它的基本思想是將一個(gè)記錄插入到已經(jīng)排好序的有序表中，從而一個(gè)新的、記錄數(shù)增1的有序表。在其實(shí)現(xiàn)過(guò)程使用雙層循環(huán)，外層循環(huán)對(duì)除了第一個(gè)元素之外的所有元素，內(nèi)層循環(huán)對(duì)當(dāng)前元素前面有序表進(jìn)行待插入位置查找，并進(jìn)行移動(dòng)

直接插入排序的實(shí)現(xiàn)

基本思想

1.???每次從無(wú)序表中取出第一個(gè)元素，把它插入到有序表的合適位置，使有序表仍然有序。

2.? ?第一趟比較前兩個(gè)數(shù)，然后把第二個(gè)數(shù)按大小插入到有序表中

3.???第二趟把第三個(gè)數(shù)據(jù)與前兩個(gè)數(shù)從后向前掃描，把第三個(gè)數(shù)按大小插入到有序表中；

4.???依次進(jìn)行下去，進(jìn)行了(n-1)趟以后就完成了整個(gè)排序過(guò)程。

具體代碼

#include <stdio.h>
//直接插入排序
void InsertSort(int* arr, int len)
{
	//定義變量用來(lái)循環(huán)
	int i = 0;
	int j = 0;
	//哨兵變量 即用來(lái)存放需要查入的元素
	int tmp = 0;
	//第一層循環(huán) 循環(huán)len-1次
	//因?yàn)楫?dāng)數(shù)組只有一個(gè)元素時(shí)它就是有序的不用比較
	//所以從第二個(gè)元素開(kāi)始比較 即i=1
	for (i = 1; i < len; i++)
	{
		//將需要插入的元素放入tmp中
		tmp = arr[i];
		//第二層循環(huán) 和要插入的元素比較
		//要比較的就是插入元素前面的 即j=i-1
		for (j = i - 1; j >= 0; j--)
		{
			//如果插入元素前一個(gè)大于插入元素就將它們交換
			if (arr[j] > arr[j + 1])
			{
				arr[j + 1] = arr[j];
				arr[j] = tmp;
			}
			//如果不大于插入元素的時(shí)候就跳出
			//因?yàn)橐迦朐厍懊娴淖訑?shù)組的元素已經(jīng)是有序的
			//只要大于子數(shù)組后面的元素，前面的就不用比較了
			else
				break;
		}
	}
}
int main()
{
	//待排序數(shù)組
	int arr[] = { 3,8,7,2,6,9,1,4 };
	//直接插入排序函數(shù)
	InsertSort(arr, sizeof(arr) / sizeof(arr[0]));
	//打印
	int i = 0;
	for (i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		printf("%d ", arr[i]);
	}

	return 0;
}

直接插入排序的原理

直接插入排序是由兩層嵌套循環(huán)組成的。外層循環(huán)標(biāo)識(shí)并決定待比較的趟術(shù)和數(shù)值。內(nèi)層循環(huán)為待比較數(shù)值確定其最終位置。直接插入排序?qū)⒋容^的數(shù)值與它的前一個(gè)數(shù)值進(jìn)行比較，所以外層循環(huán)是從第二個(gè)數(shù)值開(kāi)始的。當(dāng)前一數(shù)值比待比較數(shù)值大的情況下繼續(xù)循環(huán)比較，直到找到比待比較數(shù)值小的并將待比較數(shù)值置入其后一位置，結(jié)束該次循環(huán)。

這里我們以代碼中的數(shù)組為例：我們將數(shù)組{?3,8,7,2,6,9,1,4}進(jìn)行升序。我們將3元素從無(wú)序表中拿出來(lái)放到有序表中，有序表中無(wú)元素，它仍然有序。注意（比較中是從后往前，比較的數(shù)組是有序的，如果待插入的元素大于比較元素，則比較元素前面的就不用比較了。）這時(shí)開(kāi)始正式比較，第一次比較8大于3，不用交換直接插入，有序表3，8。第二次比較7小于8交換，7大于3不交換，直接插入，有序表3，7，8。第三次比較2小于8交換，2小于7交換，2小于3交換，前面沒(méi)有元素了，插入。有序表2，3，7，8。第四次交換比較6小于8交換，6小于7交換，6大于3不交換，插入。有序表2，3，6，7，8。第五次交換比較9大于6不交換，直接插入。有序表2，3，6，7，8，9。第六次交換比較1小于9交換，1小于7交換，1小于6交換，1小于3交換，1小于2交換。有序表1，2，3，6，7，8，9。第7次交換比較4小于9交換，4小于8交換，4小于7交換，4小于6交換，4大于3不交換，直接插入，有序表1，2，3，4，6，7，8，9。這時(shí)數(shù)組就已經(jīng)變成有序的了。

畫圖分析：

直接插入排序的特點(diǎn)和性能

復(fù)雜度?

直接插入排序的時(shí)間復(fù)雜度為?O (n^2)?，空間復(fù)雜度為 O (1) 。 在排序過(guò)程中，如果待排序的序列已經(jīng)近似有序，則直接插入排序的效率會(huì)很高，因?yàn)樯傩枰苿?dòng)已排序部分的元素。 但如果待排序序列的規(guī)模很大或者是隨機(jī)分布的，那么直接插入排序的效果會(huì)不如其他高效率排序算法，如快速排序等。

穩(wěn)定性

插入排序是在一個(gè)已經(jīng)有序的小序列的基礎(chǔ)上，一次插入一個(gè)元素。如果碰見(jiàn)一個(gè)和插入元素相等的，那么將會(huì)把待插入元素放在相等元素的后面。所以，相等元素的相對(duì)的前后順序沒(méi)有改變，所以插入排序是穩(wěn)定的。

二分查找代碼的應(yīng)用

下面還有一個(gè)插入排序中的二分查找，大家可以看看文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-574698.html

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#define MaxSize 100
#define ElemType int
#define Status int
using namespace std;
//順序表數(shù)據(jù)結(jié)構(gòu)
typedef struct
{
	ElemType data[MaxSize];//順序表元素
	int length;            //順序表當(dāng)前長(zhǎng)度
}SqList;
//***************************基本操作函數(shù)*******************************//
//初始化順序表函數(shù)，構(gòu)造一個(gè)空的順序表 
Status InitList(SqList &L)
{
	memset(L.data,0,sizeof(L));//初始化數(shù)據(jù)為0
	L.length=0;                //初始化長(zhǎng)度為0
	return 0;
}
//創(chuàng)建順序表函數(shù) 初始化前n個(gè)數(shù)據(jù)
bool CreatList(SqList &L,int n)
{
	if(n<0||n>MaxSize)false;//n非法
	for(int i=0;i<n;i++)
	{
		scanf("%d",&L.data[i]);
		L.length++;
	}
	return true;
}
//插入函數(shù) 位置i插入數(shù)據(jù) i及之后元素后移  1=<i<=length+1 
bool InsertList(SqList &L,int i,ElemType e)
{
	if(i<1||i>L.length+1) //判斷位置是否有效
     {
		printf("位置無(wú)效！?。n");
    	return false;
	 }
	if(L.length>=MaxSize)//判斷存儲(chǔ)空間是否已滿
	{
		printf("當(dāng)前存儲(chǔ)空間已滿?。。n");
		return false;
	}
	for(int j=L.length;j>=i;j--)//位置i及之后元素后移
	{
		L.data[j]=L.data[j-1];
	}
	L.data[i-1]=e;
	L.length++;
	return true;
}
//刪除函數(shù) 刪除位置i的元素 i之后的元素依次前移
bool  ListDelete(SqList &L,int i)
{
	if(i<1||i>L.length)
     {
		printf("位置無(wú)效?。?！\n");
    	return false;
	 }
	for(int j=i;j<=L.length-1;j++)//位置i之后元素依次前移覆蓋
	{
		L.data[j-1]=L.data[j];
	}
	L.length--;
	return true;
}
//查找函數(shù) 按位置從小到大查找第一個(gè)值等于e的元素 并返回位置
int LocateElem(SqList L,ElemType e)
{
 for(int i=0;i<L.length;i++)//從低位置查找
	{
		if(L.data[i]==e)
			return i+1;
	}
 return 0;
 
}
//二分查找函數(shù)
int Binary_search(SqList L,ElemType key)
{
	int low = 0;int mid = 0;int high = L.length-1;
	while(low<=high)
	{
		mid = (low+high)/2;
 		if(key==L.data[mid])
		{
			return mid;
		}
		else if(key>L.data[mid])
		{
			low = mid+1;
		}
		else
		{
			high = mid-1;
		}
	}
	return -1;
}
//********************************功能函數(shù)*****************************************//
//輸出功能函數(shù) 按位置從小到大輸出順序表所有元素
void PrintList(SqList L)
{
	printf("當(dāng)前順序表所有元素:");
	for(int i=0;i<L.length;i++)
	{
		printf("%d ",L.data[i]);
	}
	printf("\n");
}
//創(chuàng)建順序表函數(shù)
void Create(SqList &L)
{
	int n;bool flag;
	printf("請(qǐng)輸入要?jiǎng)?chuàng)建的順序表長(zhǎng)度(>1):");
	scanf("%d",&n);
	printf("請(qǐng)輸入%d個(gè)數(shù)（空格隔開(kāi)）:",n);
	flag=CreatList(L,n);
	if(flag){
		printf("創(chuàng)建成功！\n");
		PrintList(L);
	}
	else printf("輸入長(zhǎng)度非法！\n");
 
}
//插入功能函數(shù) 調(diào)用InsertList完成順序表元素插入 調(diào)用PrintList函數(shù)顯示插入成功后的結(jié)果
void Insert(SqList &L)
{
  int place;ElemType e;bool flag;
  printf("請(qǐng)輸入要插入的位置(從1開(kāi)始)及元素:\n");
  scanf("%d%d",&place,&e);
  flag=InsertList(L,place,e);
  if(flag) 
  {
	printf("插入成功！?。n");
	PrintList(L);
  }
}
//刪除功能函數(shù) 調(diào)用ListDelete函數(shù)完成順序表的刪除 調(diào)用PrintList函數(shù)顯示插入成功后的結(jié)果
void Delete(SqList &L)
{
  int place;bool flag;
  printf("請(qǐng)輸入要?jiǎng)h除的位置(從1開(kāi)始):\n");
  scanf("%d",&place);
  flag=ListDelete(L,place);
  if(flag) 
  {
	printf("刪除成功?。?！\n");
	PrintList(L);
  }
}
//查找功能函數(shù) 調(diào)用LocateElem查找元素
void Search(SqList L)
{
  ElemType e;int flag;
  printf("請(qǐng)輸入要查找的值:\n");
  scanf("%d",&e);
  flag=LocateElem(L,e);
  if(flag) 
  {
	printf("該元素位置（從1起）為:%d\n",flag);
  }
  else
	  printf("未找到該元素！\n");
}
//簡(jiǎn)單選擇排序功能函數(shù) 為二分做準(zhǔn)備
void SelectSort(SqList &L)
{
	int min;int temp;
	for(int i=0;i<L.length;i++)
	{
		min=i;
		for(int j=i+1;j<L.length;j++)
		{
			if(L.data[j]<L.data[min])min=j;
		}			
		if(min!=i)
		{
			temp=L.data[min];
			L.data[min]=L.data[i];
			L.data[i]=temp;
		}
	}
}
//二分查找功能函數(shù) 調(diào)用Binary_search
void Binary(SqList L)
{
	int key;int place;
	SelectSort(L);       //二分查找前先排序
	PrintList(L);
	printf("請(qǐng)輸入要查找的值：\n");
	scanf("%d",&key);
	place=Binary_search(L,key);
	if(place>=0)printf("位置（從0起）為：%d\n",place);
	else printf("未找到！\n");
}
//菜單
void menu()
{
   printf("********1.創(chuàng)建    2.插入*********\n");
   printf("********3.刪除    4.查找*********\n");
   printf("********5.輸出    6.二分查找*********\n");
   printf("********7.退出\n");
}
int main()
{
 SqList L;int choice;
 InitList(L);
 while(1)
 {
  menu();
  printf("請(qǐng)輸入菜單序號(hào)：\n");
  scanf("%d",&choice);
  if(7==choice) break;
  switch(choice)
  {
  case 1:Create(L);break;
  case 2:Insert(L);break;
  case 3:Delete(L);break;
  case 4:Search(L);break;
  case 5:PrintList(L);break;
  case 6:Binary(L);break;
  default:printf("輸入錯(cuò)誤?。?！\n");
  }
 }
 return 0;
}

到了這里，關(guān)于直接插入排序到底有多“直男”的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！