一、步骤：
希尔排序的基本思想：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到gap = 1时，所有记录在统一组内排好序。
希尔排序是在直接插入排序的基础上演变的
1.先选定一个小于n的整数gap作为间隔（一般gap = n / 3 + 1），然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。它将一组数组分为了gap组，一组中每个元素的间隔为gap。
2.当gap的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。
图片讲解
将上述同一颜色相连的数分为一组，一共分了gap组，一组中每个元素的间隔为gap，对同一组中的元素进行插入排序。黑色组排序结果如图：
然后红色组进行排序：
最后绿色组进行排序，即gap = 3时，最终结果：
当gap = 3这组数据排序结束后，gap会缩小，直到gap = 1时，就是插入排序。
二、代码
代码1：
void ShellSort(int* arr, int n)
{int gap = n; // 先创立一个变量gapwhile (gap > 1){gap = gap / 3 + 1; // gap减小的规律可以是任意的，但最后一次一定要等于1。在这里后面要加1是为了保证最后一次gap = 1如果这里的gap = gap / 2，则最后一次gap一定等于1for (int i = 0; i < n - gap; i++) // i < n - gap为避免越界访问{int end = i; // 循环内与直接插入排序一样int tmp = arr[end + gap]; // 直接插入排序的tmp为arr[end + 1]，这里变成arr[end + gap]while (end >= 0){if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}}
}代码2 ：
这里的代码比上面的更容易理解，这里的代码跟符合上面的图片讲解
void ShellSort(int* arr, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;for (int j = 0; j < gap; j++) // 将整个数组分为了gap组{for (int i = j; i < n - gap; i += gap) // 每一组的元素进行直接插入排序{int end = i;int tmp = arr[end + gap];while (end >= 0){if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}}}
}
