目录
前言
希尔排序(shell)
排序原理
大致思路
示例
代码实现(C语言)
算法分析
时间复杂度
空间复杂度
稳定性
前言
前面我有一篇插入排序的详细的文章讲解(链接:排序算法-----插入排序(图文详解)_灰勒塔德的博客-CSDN博客)今天我们接着学习排序算法中的希尔排序(shell_sort),希尔排序跟插入排序是有一定关联的,可以这么说,希尔排序是对插入排序的再进一步优化,下面我们就开始学习吧!
希尔排序(shell)
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至 1 时,整个文件恰被分成一组,算法便终止。
排序原理
大致思路
希尔排序是去通过设置一个分组区间gap,把一个初始的数组进行分组,然后对每一个小组里面的数组通过插入排序算法来去排序,这就是完成了一轮排序;然后再把区间gap缩小,再次以新的gap区间进行分组,然后按照以上的做法再次进行新的一轮排序;最后直到gap=1时候,这时候的数组就是一个整体了,就对这个整体的数组进行排序,最终结果就是排序完成后的数组了。(初始化的gap可以设置为任意数值,不会影响到最终结果的)
示例
给定一个初始数组[9,1,2,5,7,4,8,6,3,5],下面怎么去通过希尔排序来完成这个排序呢?
第一步,先进行分组,此时设置区间gap为5,分组完成后进行初步排序,结果如下所示:
第一组:9 4 ——>4 9
第二组:1 8 ——>1 8
第三组:2 6 ——>2 6
第四组:5 3 ——>3 5
第五组:7 5 ——>5 7
此时新的数组为 [4,1,2,3,5,9,8,6,5,7]
第二步,缩小gap,可以去通过整除去缩小,此时gap为2,再次分组排序,结果如下:
第一组:4 2 5 8 5——>2 4 5 5 8
第二组:1 3 9 6 7——>1 3 6 7 9
此时新的数组为 [2,1,4,3,5,6,5,7,8,9]
第三步,此时gap再次缩小,为1,那么就只有一组了,也就是整个数组为一个整体去排序:
2 1 4 3 5 6 5 7 8 9——>1 2 3 4 5 5 6 7 8 9
此时排序完成。
图解如下:
代码实现(C语言)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
//希尔shell排序
void shell_sort(int* n,int length) {
int i, j, gap;
for (gap = length / 2; gap > 0; gap /= 2) {
for (i = 0; i < gap; i++) {
for (j = i+gap; j < length; j += gap) {
//以下对每一组进行插入排序
int temp = n[j];
int k = j - gap;
if (n[j] < n[j - gap]) {
while (k >= 0 && n[k] > temp) {
n[k + gap]= n[k];
k -= gap;
}
n[k + gap] = temp;
}
}
}
}
}
int main() {
int array[10];
srand((unsigned)time(0));
for (int i = 0; i < 10; i++) {
array[i] = rand() % 20;
}
for (int i = 0; i < sizeof(array) / sizeof(int); i++) {
printf("%d ", array[i]);
}
printf("\n排序后:");
shell_sort(array, sizeof(array) / sizeof(int));//希尔排序
for (int i = 0; i < sizeof(array) / sizeof(int); i++) {
printf("%d ", array[i]);
}
}
//输出结果:
//3 9 17 4 5 18 13 14 12 15
//排序后:3 4 5 9 12 13 14 15 17 18
算法分析
时间复杂度
增量序列的选择会极大地影响希尔排序的效率。 希尔排序时间复杂度非常难以分析,它的平均复杂度界于 O(n) 到 O(n^2) 之间,普遍认为它最好的时间复杂度为 O(n^1.3),相较于插入排序,时间复杂度降低了很多,尤其是当数组数量非常大的时候效果最明显,当然如果数组是完全逆序的话,那么时间复杂度就是O(n^2)。
空间复杂度
希尔排序没有涉及到空间的开辟等等,使用的空间是原数组的空间,所以空间复杂度是O(1)
稳定性
前面我们学习了插入排序知道,一次性的插入排序是稳定的,但是希尔排序是先分组然后再去插入排序,所以出现相同的元素的时候,元素的相对位置会发生改变,所以希尔排序是不稳定的
好了,以上就是本期的全部内容了,我们下一期再见!!!文章来源:https://www.toymoban.com/news/detail-708756.html
分享一张壁纸:文章来源地址https://www.toymoban.com/news/detail-708756.html
到了这里,关于排序算法-----希尔排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!