十大排序之希尔排序(C语言实现)(排序算法)

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止. 时间复杂度O(n^（1.3—2）) 空间复杂度O(1) 举个例子：

在这里我们要提出逆序对的相关问题，设 A 为一个有 n 个数字的有序集 (n>1)，其中所有数字各不相同。 如果存在正整数 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，则 <A[i], A[j]> 这个有序对称为 A 的一个逆序对，也称作逆序数。 例如，数组（3，1，4，5，2）的逆序对有(3,1),(3,2),(4,2),(5,2)，共4个。 所以像选择，排序，插入每次都是消去一个逆序对，所以执行的次数会比较高。 所以希尔排序就是一次我不只消掉一个逆序对，而是一次消掉多个逆序对，这样效率就高了。 执行代码如下

#include<stdio.h>
void xier_sort(int a[],int N);
int main()
{
          
   
	int a[10];
	int i;
	printf("请输入要排序的元素:
");
	for(i=0;i<10;i++)
	scanf("%d",&a[i]);
	printf("未排序之前的元素顺序:
");
	for(i=0;i<10;i++)
		printf("%2d",a[i]);
	charu_sort(a,10);
	printf("
");
	printf("排序之后的元素顺序为:
");
	for(i=0;i<10;i++)
		printf("%2d",a[i]);
	return 0;
}
void xier_sort(int a[],int N)//内层是插入排序
{
          
   
	int temp;
	for(int D=N/2;D>0;D/=2)/*希尔增量序列*/
	{
          
   
		for(int i=D;i<N;i++)
	{
          
   
		temp=a[i];
		for(int j=i;j>=D&&a[j-D]>temp;j-=D)
		{
          
   
			a[j]=a[j-D];
			a[j-D]=temp;
		}
	}
	}
}

运算结果如下: