希尔排序

希尔排序(Shell Sort)是插入排序的一种算法，是对直接插入排序的一个优化，也称缩小增量排序。

希尔排序是非稳定排序算法。
希尔排序因DL．Shell于1959年提出而得名。

希尔排序是将待排序的数组元素按下标的一定增量分组 ，分成多个子序列，然后对各个子序列进行直接插入排序算法排序；然后依次缩减增量再进行排序，直到增量为1时，进行最后一次直接插入排序，排序结束。

1. 算法步骤

1. 确定增量分组次数
2. 每一次增量中遍历一个分组中所有的元素
3. 不同分组之间的元素进行插入排序

$$count=\lfloor len/2\rfloor$$

count : 增量分组次数（分多少次组） len：数组长度

2. 动图演示

3.代码实现

void swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}

void shell_sort(int arr[], int len)//默认是对int类型的数组进行数据交换
{for (int i = len; i != 1; i = i/2)//增量分组次数为len/2再向下取整{								//i变量循环的次数就是增量分组次数for (int j = 0; j < i/2; j++)//遍历分组中的每个元素{for (int k = j+i/2; k < len; k=k+i/2)//思想是插入排序{int temp = k;//第一个待交换元素的下标while (1){if (arr[temp] < arr[temp-i/2])//该分组元素小于前一个分{							//组，进行交换if (temp < (i / 2))//如果是第一分组，退出死循环{break;}swap(arr + temp, arr + temp - i / 2);//交换temp = temp - i / 2;//指向前一个序列中相应位置}else{break;}}}}}
}

void main()
{int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70,32};//定义一个待排序的数组int len = sizeof(arr) / sizeof(*arr);printf("\nsort before\n");for (int i = 0; i < len; i++){printf("%d\t", arr[i]);}shell_sort(arr,len);printf("\shell_sort after\n");for (int i = 0; i < len; i++){printf("%d\t", arr[i]);}system("pause");
}

4.实验结果