图解希尔排序---C实现

希尔排序又称 “缩小增量排序” 它也是一种插入类排序的方法。

希尔排序原理：

希尔排序属于插入类排序,是 将整个有序序列分割成若干小的子序列分别进行 插入排序。

希尔排序示意图：

以“gap”为间距，将原数组分为若干部分，每一部分都进行插入排序。“gap”初始为原数组长度的一半，进而gap=gap/2。（图片来自百度图片） 要想完成数据排序必须在最后执行gap=1，即普通的插入排序法。不过此时对象数据顺序应该已经很整齐了。

C实现希尔排序：

#include <stdio.h>
#include <stdlib.h>

//希尔排序 

void shellSort(int array[], int length){
          
   
	int i,j,k,gap,temp;
	
	for(gap=length/2; gap>0; gap=gap/2){
          
      //以gap将数组分割
		for(i=0; i<gap; i++){
          
      //分割后的第一个元素
			for(j=i+gap; j<length; j=j+gap){
          
   	//进行插入排序
				if(array[j] < array[j - gap]){
          
   
					temp = array[j];
					k = j - gap;
					while(k>=0 && array[k]>temp){
          
      //只要该元素小，则较大的向后移动，该元素向前移动
						array[k + gap] = array[k];
						k = k - gap;
					}
					array[k + gap] = temp;
				}
			}
		}
	}
}

int main(int argc, char *argv[]) {
          
   
	int a[100],n,i;
	
	printf("请输入有几个数：");
	scanf("%d",&n);
	printf("请输入这几个数：");
	for(i=0;i<n;i++)
	{
          
   
		scanf("%d",&a[i]);
	}
	
	shellSort(a,n);   //希尔排序
	
	for(i=0;i<n;i++)  //将排序后的数组输出
	{
          
   
		if(i>0) printf(" ");   //从下标1开始，元素之前输出输出空格隔开
		printf("%d",a[i]);
	}
	return 0;
}