数据结构：插入排序

简介：使用C语言实现插入排序算法，其中包括带哨兵的直接插入排序，不带哨兵的直接插入排序，折半插入排序，希尔排序。算法的原理网上的资料很多，比较容易查到，这里就不一一赘述。

排序头文件：Sort.h

#ifndef SORT_H
#define SORT_H

#define ElemType int

void DirectInsertSortWithSentry(ElemType A[], int n);
void DirectInsertSortWithoutSentry(ElemType A[], int n);
void BinaryInsertSortWithSentry(ElemType A[], int n);
void ShellSort(ElemType A[], int n);

#endif 

排序源文件：Sort.c

#include "Sort.h"


void DirectInsertSortWithSentry(ElemType A[], int n)
{
	int i, j;

	for (i = 2; i <= n; i++) //依次将A[2]~A[n]插入前面已排序序列
	{
		if (A[i] < A[i-1]){ //若A[i]小于其前驱，将A[i]插入有序表
			A[0] = A[i];    //复制为哨兵，A[0]处不存放元素

			for (j = i-1; A[j] > A[0]; j--) //从后查找待插入位置
				A[j+1] = A[j];  //向后挪动

			A[j+1] = A[0];  //复制到插入位置
		}
	}
}


void DirectInsertSortWithoutSentry(ElemType A[], int n)
{
	int i, j, temp;

	for (i = 1; i < n; i++) //依次将A[1]~A[n-1]插入前面已排序序列
	{
		if (A[i] < A[i-1]) //若A[i]小于其前驱，将A[i]插入有序表
		{
			temp = A[i]; //暂存A[i]

			for (j = i-1; A[j] > temp && j >= 0; j--) //从后查找待插入位置
				A[j+1] = A[j]; //向后挪动

			A[j+1] = temp; //复制到插入位置
		}
	}
}


void BinaryInsertSortWithSentry(ElemType A[], int n)
{
	int i, j, low, high, mid;

	for (i = 2; i <= n; i++) //依次将A[2]~A[n]插入前面已排序序列
	{
		A[0] = A[i]; //将A[i]暂存到A[0]

		low = 1; //设置折半查找的范围

		high = i - 1;

		while (low <= high) //折半查找，默认递增序列
		{
			mid = (low + high) / 2; //去中间点

			if (A[mid] > A[i]) //查找左半子表
				high--;
			else //查找右半子表
				low++;
		}

		for (j = i-1; j >= high + 1; j--) //后移元素
			A[j + 1] = A[j];

		A[high + 1] = A[0]; //插入操作
	}
}


void ShellSort(ElemType A[], int n)
{
	int dk, i, j;

	for (dk = n/2; dk >= 1; dk/=2)	//步长变化
	{
		for (i = dk + 1; i <= n; i++) //子序列插入排序
		{
			if (A[i] < A[i - dk]) 
			{
				A[0] = A[i]; //A[0]暂存数据

				for (j = i-dk; j > 0 && A[0] < A[j]; j -= dk){ //记录后移
					A[j + dk] = A[j]; 
				}

				A[j + dk] = A[0]; //插入数据
			}
		}
	}
}

用于测试功能的主函数：main.c

#include "stdio.h"
#include "stdlib.h"
#include "Sort.h"

#define DriectDataNum 5


void SortTest(void)
{
	ElemType array1[DriectDataNum+1] = {0, 2, 5, 9 ,1, 0};
	ElemType array2[DriectDataNum] = {2, 5, 9 ,1, 0};
	ElemType array3[DriectDataNum+1] = {0, 2, 5, 9 ,1, 0};
	ElemType array4[DriectDataNum+1] = {0, 5, 4, 3 ,2, 1};

	DirectInsertSortWithSentry(array1, DriectDataNum);

	DirectInsertSortWithoutSentry(array2, DriectDataNum);

	BinaryInsertSortWithSentry(array3, DriectDataNum);

	ShellSort(array4, DriectDataNum);
}


int main(void)
{
	SortTest(); //插入排序测试

	system("pause");

	return 0;
}

推荐：想要详细了解以上算法的原理，强烈推荐王道考研数据结构课程。