算法之插入排序及希尔排序（C语言版）

本文介绍: 思想：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。读者可能会想这个希尔排序是三层循环，而插入排序才两层循环，不可能出现其算法更优越啊！这是一个相同数据检测出来两者的时间差距，可见两者的差距有多大，希尔牛逼！n=2:外层2次，内层最坏2次。n=3:外层3次，内层最坏3次。n=n:外层n次，内层最坏n次。时间复杂度为：O(N*N)=O(N^2);

我们来实现上述排序

当插入第i(i&g t;=1)个元素时，前面的array[0],array[1],.,arr a y[i-1]已经排好序，此时用arr ay[i的排序码与arr ay[i-1]arr ay[i-2].的排序码顺序进行比较，找到插入位置即将arr ayU插入，原来位置上的元素顺序后移.

CSDN这个链接有我之前写的直接插入排序

今天我们来实现广义上的插入排序：

我直接写出来，会在里面写注释

void Insertsort(int* arr, int n)//arr数组，n元素个数
{
	//我们用升序排列
	for (int i = 0; i < n-1; i++)//循环n次
	{
		int end = i;//将i的值赋给end，方便将其数值改变而不影响循环
		int tmp = arr[end + 1];//由于升序，我们要提前保存要排序的数
		//这里默认前i个数是已排好的，即end
		while (end &gt;= 0)
		{
			if (arr[end] &gt; tmp)//arr[end]与arr[end+1]比较
			{
				arr[end + 1] = arr[end];//满足条件赋值
				end--;//继续向前排列
			}
			else
			{
				break;//不满足条件退出循环
			}
		}
		arr[end + 1] = tmp;//将保存的数值赋给留出的位置
	}
}

我们排一个数组试试：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h&gt;
void Insertsort(int* arr, int n)//arr数组，n元素个数
{
	//我们用升序排列
	for (int i = 0; i < n-1; i++)//循环n次
	{
		int end = i;//将i的值赋给end，方便将其数值改变而不影响循环
		int tmp = arr[end + 1];//由于升序，我们要提前保存要排序的数
		//这里默认前i个数是已排好的，即end
		while (end &gt;= 0)
		{
			if (arr[end] > tmp)//arr[end]与arr[end+1]比较
			{
				arr[end + 1] = arr[end];//满足条件赋值
				end--;//继续向前排列
			}
			else
			{
				break;//不满足条件退出循环
			}
		}
		arr[end + 1] = tmp;//将保存的数值赋给留出的位置
	}
}
void Print(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
}
int main()
{
	int arr[] = { 2,4,6,8,0,1,3,5,7,9 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	Insertsort(arr, sz);
	Print(arr, sz);

}

void Insertsort(int* arr, int n)//arr数组，n元素个数
{
	//我们用升序排列
	for (int i = 0; i < n-1; i++)//循环n次
	{
		int end = i;//将i的值赋给end，方便将其数值改变而不影响循环
		int tmp = arr[end + 1];//由于升序，我们要提前保存要排序的数
		//这里默认前i个数是已排好的，即end
		while (end >= 0)
		{
			if (arr[end] < tmp)//arr[end]与arr[end+1]比较,改变<,>符号即可
			{
				arr[end + 1] = arr[end];//满足条件赋值
				end--;//继续向前排列
			}
			else
			{
				break;//不满足条件退出循环
			}
		}
		arr[end + 1] = tmp;//将保存的数值赋给留出的位置
	}
}

void Shellsort(int* arr, int n)
{
	int gap = n;//将n的值赋值一份给gap，便于后续对gap给值划分
	while (gap > 1)
	{
		//法一：gap/2为单位
		gap = gap / 2;//gap的值以二分之一不断划分，最后得到gap=1进行插入排序
		//gap/3为单位
		//gap = gap / 3 + 1;//gap的值以三分之一不断划分，最后加+1得到gap=1进行插入排序
		//gap>1时进行预排序
		//gap=1时进行插入排序
		for (int i = 0; i < n - gap; i++)//i<n-gap:把间隔为gap的多组数据同时排
		{
			//下面操作和插入排序大体相同，但注意不再时加减1；而是以gap为单位！！！
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}
}

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
void Shellsort(int* arr, int n)
{
	int gap = n;//将n的值赋值一份给gap，便于后续对gap给值划分
	while (gap > 1)
	{
		//法一：gap/2为单位
		gap = gap / 2;//gap的值以二分之一不断划分，最后得到gap=1进行插入排序
		//gap/3为单位
		//gap = gap / 3 + 1;//gap的值以三分之一不断划分，最后加+1得到gap=1进行插入排序
		//gap>1时进行预排序
		//gap=1时进行插入排序
		for (int i = 0; i < n - gap; i++)//i<n-gap:把间隔为gap的多组数据同时排
		{
			//下面操作和插入排序大体相同，但注意不再时加减1；而是以gap为单位！！！
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}
}
void Print(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
}
int main()
{
	int arr[] = { 2,4,6,8,0,1,3,5,7,9 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	Shellsort(arr, sz);
	Print(arr, sz);

}

gap = gap / 2;// logN
//gap = gap / 3 + 1;// 1og3N 以3为底数的对数

for (int i = 0; i < n - gap; i++)
{
	// gap > 1时都是预排序 接近有序
	// gap == 1时就是直接插入排序 有序
	// gap很大时，下面预排序时间复杂度0(N)
	// // gap很小时，数组已经很接近有序了，这时差不多也是(N)
	int end = i;
	int tmp = arr[end + gap];
	while (end >= 0)
	{
		if (arr[end] > tmp)
		{
			arr[end + gap] = arr[end];
			end -= gap;
		}
		else
		{
			break;
		}
	}
	arr[end + gap] = tmp;
}