一、步骤:
希尔排序的基本思想:先选定一个整数,把待排序文件中所有记录分成个组,所有距离为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;}}}
}