# 希尔排序
是一个分组插入排序算法,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 DL.Shell 于 1959 年提出而得名。
# 基本思想
先追求表中的元素部分有序,再逐渐逼近全局有序。
- 先将待排序表分割成若干子表,对各个子表分别进行直接插入排序。缩小增量,再次分割子表,对子表进行直接插入排序,直到增量为 1,排序完成。
//举例 DL. Shel建议的增量序列为:n/2,n/4,…,1,称为希尔增量,最后一个增量值必须为1。 int arr={9,1,2,5,7,4,8,6,3,5}; //arr长度为10,第一次增量为10/2=5 //分成5组,每组两个元素,分别进行直接插入排序 //第一次分组为 {9,4} {1,8} {2,6} {5,3} {7,5} //第一次分组排序后为 {4,9} {1,8} {2,6} {3,5} {5,7} //第一次排序为 {4,1,2,3,5,9,8,6,5,7} //第二次增量为5/2=2 //分成2组,每组5个元素,分别进行直接插入排序 //第二次分组为 {4,2,5,8,5} {1,3,9,6,7} //第二次分组排序后为 {2,4,5,5,8} {1,3,6,7,9} //第二次排序为 {2,1,4,3,5,6,5,7,8,9} //第三次增量为2/2=1 //分成1组,每组10个元素,分别进行直接插入排序 //第三次分组为 {2,1,4,3,5,6,5,7,8,9} //第三次分组排序后为 {1,2,3,4,5,5,6,7,8,9} //第三次排序为 {1,2,3,4,5,5,6,7,8,9} //代码实现 void shellSort(int *arr, int length) { int i, j, temp, gap; // 增量每次都/2 直到为1 for (gap = length / 2; gap > 0; gap /= 2) { // 从第gap个元素开始,因为前面的元素默认是有序的 for (i = gap; i < length; ++i) { // 如果当前元素比前一个元素小,那么就需要将当前元素插入到前面的有序序列中 if (arr[i] < arr[i - gap]) { temp = arr[i]; // 从当前元素的前一个元素开始,依次和当前元素比较,如果比当前元素大,那么就将该元素后移gap位 // 如果是多个分组的话 每次循环会切换一个分组 有点不好理解 for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) { arr[j + gap] = arr[j]; } arr[j + gap] = temp; } } } } //第二种实现方式 (这种方式比较好理解 每次插入排序都是 先处理每个分组的所有元素 在处理下一个分组) void shellSort1(int *arr, int length) { int i = 0, j, temp, gap; for (gap = length / 2; gap > 0; gap /= 2) { // 这里的i++是为了每次循环都切换一个分组 i += 1; for (j = i + gap; j < length; j += gap) { if (arr[j] < arr[j - gap]) { temp = arr[j]; int k = j - gap; // 将当前分组的所有元素都对比一遍 确保当前分组的所有元素都是有序的 while (k >= 0 && arr[k] > temp) { arr[k + gap] = arr[k]; k -= gap; } arr[k + gap] = temp; } } } }
Copied!
# 算法分析
# 时间复杂度
和增量序列有关, 不太好计算确切的时间复杂度, 总体是优于直接插入排序的
最坏情况下的时间复杂度为 O(n^2)
- 和插入排序一样, 所有都是逆序的
# 空间复杂度
O(1) 和插入排序一样
# 稳定性
不稳定
- 例如: 5 8 5 2 9 这样一组数据, 第一次增量为 2, 5 和 5 交换了位置, 所以不稳定