【数据结构】【排序】插入排序

【数据结构】【排序】插入排序

插入排序可分为直接插入排序及希尔排序

①直接插入排序

步骤如下：

1、将数组分为2部分：已排序部分、待排序部分

2、每次从待排序部分中拿出元素，在已排序部分中找到合适的位置插入元素

思想：将一个记录插入到已排序好的有序表中，从而得到一个新记录数增1的有序表。即：先将序列的第一个记录看成是一个有序的子序列，然后从第二个记录逐个进行插入，直至整个序列有序为止。

代码实现：

#include<stdio.h>

void InsertSort(int arr[],int len)
{
	int tmp=0;
	int i=1;
	int j=i-1;
	for(i;i<len;i++)
	{
		tmp=arr[i];
		for(j=i-1;j>=0&&arr[j]>tmp;j--)
		{
			arr[j+1]=arr[j];
		}
		arr[j+1]=tmp;
	}
}

void Print(int arr[],int len)
{
	for(int i=0;i<len;i++)
	{
		printf("%d  ",arr[i]);
	}
}

int main()
{
	int arr[]={1,33,2,4,53,75,6,8,22};
	int len = sizeof(arr)/sizeof(arr[0]);
	InsertSort(arr,len);
	Print(arr,len);
}

②希尔排序

先将整个待排序的记录序列分割成若干个子序列，分别进行直接插入排序。待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

代码实现：

#include<stdio.h>
void Shell(int arr[],int len,int dk)
{
	int tmp=0;
	int i=dk;
	int j=i-dk;
	for(i;i<len;i++)
	{
		tmp=arr[i];
		for(j=i-dk;j>=0&&arr[j]>tmp;j-=dk)
		{
			arr[j+dk]=arr[j];
		}
		arr[j+dk]=tmp;
	}
}

void ShellSort(int arr[],int len,int dk[],int dlen)
{
	for(int i=0;i<dlen;i++)
	{
		Shell(arr,len,dk[i]);
	}
}

void Print(int arr[],int len)
{
	for(int i=0;i<len;i++)
	{
		printf("%d  ",arr[i]);
	}
}

int main()
{
	int arr[]={1,2,3,3,4,5,6,6,7,8,9};
	int len=sizeof(arr)/sizeof(arr[0]);
	int dk[]={5,3,1};
	int dlen=sizeof(dk)/sizeof(dk[0]);
	ShellSort(arr,len,dk,dlen);
	Print(arr,len);
}