#include <stdio.h>

//希尔排序--优化过的插入排序
void sort(int* arr, int len)
{
	int mid = len;
	int gap = len;
	do{
		mid = mid / 2;
		if (mid == 0) {
			gap = 1;
		}
		else {
			gap = mid;
		}
		for (int i = 0;i+gap < len;i++) {
			if (arr[i] > arr[i + gap]) {
				int temp = arr[i];
				arr[i] = arr[i + gap];
				arr[i + gap] = temp;
			}
		}
	} while (mid >= 1);
}
int main()
{
	int arr[12] = { 10,9,8,7,6,65,21,5,4,3,2,1 };
	sort(arr, 12);
	return 0;
}

希尔排序就是优化过的插入排序，这里我们需要注意的就是当mid=0时循环结束，但是需要再判断一次当gap=1的时候的顺序。