常见插入排序算法

算法可视化互动网站：Comparison Sorting Visualization

基本思想：将待排关键字放入到已排序的子列中

#define _CRT_SECURE_NO_WARNINGS
#include
//第一层for：从前往后检查，如果a[i]>a[i+1]则将a[i]放入temp
//第二层for：寻找temp的插入位置，并移动元素以腾出空间
//最后将temp插入到腾出的位置上
void InsertionSort(int a[], int n) {
	int i, j,temp;
	for (i = 1; i < n; i++)
	{

		if (a[i] < a[i - 1])	//为防止越界 尽量不要写成 a[i+1]
		{
			//将a[i]放至temp
			temp = a[i];
			//循环移动，直到找到 temp>a[j]
			for (j = i - 1; j >= 0 && temp < a[j]; j--)
			{
				//将a[j+1]放至a[j]
				a[j + 1] = a[j];
			}
			//将temp放到上述循环移动空出来的位置
			//即a[j]的后一个位置 a[j+1]
			a[j + 1] = temp;
		}

	}
}
int main() {
	//一个待排序数组
	int a[9] = { 10,43,54,45,3,20,22,86 };
	//直接插入排序
	InsertionSort(a, 8);
	//输出排序结果
	for (int i = 0; i < 8; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

基本思想：寻找插入位置时使用折半查找，找到后移动元素，最后插入到正确位置

#define _CRT_SECURE_NO_WARNINGS
#include
//折半查找
void Half_Insertion_Sort(int a[], int n) {
	int i,low=0, high=n, mid,temp;
	//寻找插入位置
	for (i=1;i<=n;i++)
	{
		temp = a[i]; //寻找第i个值的插入位置

		while (low<=high)//满足此条件时继续寻找
		{
			mid = (low + high) / 2;
			if (a[mid]>temp)
				high = mid - 1; //插入位置位于左半区
			else
				low = mid + 1; //插入位置位于右半区
		}//最终temp的插入位置为high+1
		//移动元素
		for (int j = i - 1; j >= high + 1; j--)
		{
			a[j + 1] = a[j];
		}
		//插入
		a[high + 1] = temp;
	}
}
int main() {
	//一个待排序数组
	int a[9] = { 10,43,54,45,3,20,22,86 };
	//折半插入排序
	Half_Insertion_Sort(a, 9);
	//输出排序后的数组
	for (int i = 0; i < 8; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

基本思想：相距某个增量的两个元素进行比较，如果增量左端元素大于右端则进行交换，直到增量右端到序列末尾，对此增量的子列进行直接插入排序，随后增量减半重复上述操作

#define _CRT_SECURE_NO_WARNINGS
#include
//根据增量incre遍历序列，如果增量左侧a[i-incre]>增量右侧a[i]就进行交换（借助temp)
//完成上述操作后，对增量对应的子序列进行直接插入排序
//在此子序列中从后到前寻找a[i-incre]>a[i]
//在此子序列中移动从a[i-incre]到a[i]之间的元素：j=i-incre;j>=0&&a[j]>temp;j-=incre
//插入位置即为a[j]之后的位置a[j+incre]，将temp放至a[j+incre]
void ShellSort(int a[], int n) {
	//增量incre，中间变量temp，循环变量i,j
	int incre,temp,i,j;
	//处理多个有多个增量构成的子序列
	for (incre=n/2; incre>=1; incre/=2)//初始增量为表长一半；增量依次减半
	{
		for (i = incre; i < n; i++)//处理某个增量对应的单个子序列，注意这里i能等于n，下标为0到n-1
		{	
			//对子序列进行直接插入排序
			if (a[i-incre]>a[i])//增量右端小于增量右端
			{
				temp = a[i];//将增量右端移出
				//寻找temp的插入位置，从a[i-incre]到a[i]之间的元素依次后移一个增量（为temp腾出空间）
				for (j = i-incre; j>=0 && a[j]>temp; j-=incre)
				{
					a[j+incre] = a[j];
				}//最终插入位置为j+incre
				a[j+incre] = temp;
			}
		}
	}
}
int main() {
	//一个待排序数组
	int a[8] = { 10,43,54,45,3,20,22,86 };
	//希尔排序
	ShellSort(a, 8);
	//输出排序结果
	for (int i = 0; i < 8; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}