【经典算法8——希尔排序】

活动地址：CSDN21天学习挑战赛

经典算法8——希尔排序

• • 一、什么是排序？
  • 二、内部排序和外部排序
  • 三、内部排序的方法
  • 四、希尔排序
  • • 1.基本思想
    • 2.实例分析
    • 3.代码实现
    • 4.运行结果展示
    • 5.视频讲解
  • 五、时间复杂度与空间复杂度分析
  • • 1.时间复杂度
    • 2.空间复杂度
  • 六、说明

一、什么是排序？

排序是计算机内经常进行的一种操作，其目的是将一组**“无序”的记录序列调整为“有序”**的记录序列。
例如：将下列关键字序列
14，15，92，65，35，89，79，32
调整为
14，15，32，35，65，79，89，92

二、内部排序和外部排序

若整个排序过程中不需要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。

三、内部排序的方法

内部排序的过程是一个逐步扩大记录的有序序列长度的过程。

基于不同的“扩大”有序序列长度的方法，内部排序方法大致可分为：插入类、交换类、选择类、归并类、其它方法。

四、希尔排序

1.基本思想

希尔排序又称缩小增量排序，对待排记录序列先做“宏观”调整，再作“微观”调整。所谓“宏观”调整，指的是，“跳跃式”的插入排序。具体做法为：d为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1.

2.实例分析

1）例如：将下列关键字序列
14，15，92，65，35，89，79，32
调整为
14，15，32，35，65，79，89，92
2）第一次8/2=4，以四为增量

排序后
第二次4/2=2，以二为增量

将相同颜色升序排序后得到

第三次以一为增量按插入排序排序，得到最终期望序列
14，15，32，35，65，79，89，92

3.代码实现

#include<stdio.h>
int main(){
void shellsort(int a[],int n);//函数声明
int a[8]={14,15,92,65,35,89,79,32};
shellsort(a,8);//函数调用
for(int i=0;i<8;i++)
printf("%d ",a[i]);
printf("\n");
	return 0;
}
void shellsort(int a[],int n){
int i,j,k,temp;
for(k=n/2;k>0;k=k/2){
	for(i=k;i<n;i++)
	{
	temp=a[i];
	for(j=i;j>=k && temp<a[j-k];j=j-k)
		a[j]=a[j-k];		
		a[j]=temp;

	}

}

}

4.运行结果展示

5.视频讲解

请叫我AXin的排序算法：希尔排序【图解+代码】

五、时间复杂度与空间复杂度分析

1.时间复杂度

1）实现内部排序的基本操作有两个：
“比较”序列中两个关键字的大小和“移动”记录。
2)时间复杂度与增量的设置有关，目前还没有确定多少增量时间复杂度最小

2.空间复杂度

空间复杂度为O(1)

六、说明

21天学习挑战赛打卡第八篇，自知知识水平有限，如有不当之处还望批评斧正。
参考文章一头小山猪的一文学懂经典算法系列之：希尔排序