排序算法-----希尔排序

这篇具有很好参考价值的文章主要介绍了排序算法-----希尔排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

前言

希尔排序(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语言

 代码实现(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) 

稳定性

 前面我们学习了插入排序知道,一次性的插入排序是稳定的,但是希尔排序是先分组然后再去插入排序,所以出现相同的元素的时候,元素的相对位置会发生改变,所以希尔排序是不稳定的

 好了,以上就是本期的全部内容了,我们下一期再见!!!

分享一张壁纸:排序算法-----希尔排序,数据结构与算法,排序算法,算法,数据结构,c语言文章来源地址https://www.toymoban.com/news/detail-708756.html

到了这里,关于排序算法-----希尔排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包