希尔排序是建立在插入排序的基础之上的,只不过是将数据中做插入排序之前做了一次分组,他的分组是根据用户输入的一个数字来决定分多少组的,比如有如下数据:
49 58 65 97 26 13 27 49 55 4
按下图表示的方法进行三次分组,对每次分组出来的数据执行插入排序,最后得出有序的数组,乍一看来这岂不是多了一步画蛇添足的步骤?实际并不是这样,因为先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的,因此希尔排序在时间效率上比前三种方法有较大提高。
【实现代码】
void shell_sort(int *arr, int len) { int value = len; int temp = 0; int index = 0; do { // 业界统一实验的 平均最好情况 经过若干次后,收敛为1 value = value / 3 + 1; // 一次跳 value 个 for (int idx = 0; idx < value; idx++) { // 对分组后的数据进行排序,每一次跳过整个长度 for (int i = value; i < len; i += value) { index = i; temp = arr[i]; for (int j = i - value; j >= 0 && arr[j] > temp; j -= value) { arr[j + value] = arr[j]; index = j; } arr[index] = temp; } } } while (value > 1); }