数据结构（希尔排序、堆排序）

男娘i 2023-07-09 09:26 14阅读 0赞

## 希尔排序 ##

先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。  
**增量increment**  
增量初始值设置为length（待排序的数组长度）/2

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    void Shellsort(int a[],int length)
    { 
    	int i,j;
    	int increment=length;
    	do
    	{ 
    		increment/=2;
    		for(int i=increment+1;i<=length;i++)
    		{ 
    			if(a[i]<a[i-increment])
    			{ 
    				a[0]=a[i];
    				for(j=i-increment;j>0&&a[0]<a[j];j-=increment)
    				{ 
    					a[j+increment]=a[j];
    				}
    				a[j+increment]=a[0];
    			}
    		}
    	}
    	while(increment>1);
    	for(int i=1;i<=length;i++)
    	printf("%d ",a[i]);
    }
    int main()
    { 
    	int n,a[1001];
    	cin>>n;
    	for(int i=1;i<=n;i++)
    	cin>>a[i];
    	Shellsort(a,n);
    	return(0);
    }

后面我看到一个大佬的代码，简洁很多（易背难懂）

void shellsort3(int a[], int n)
    { 
    	int i, j, gap;
     
    	for (gap = n / 2; gap > 0; gap /= 2)
    		for (i = gap; i < n; i++)
    			for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap)
    				swap(a[j], a[j + gap]);
    }

希尔排序也是一种不稳定的排序，在合适的增量其时间复杂度比冒泡的O（n平方）要快！！

## 堆排序 ##

学堆排序之前要了解什么是堆，堆就是具有特殊性质的完全二叉树，比如图一父节点比子节点都大，这就是最大堆，相反图二就是最小堆。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTkzOTgy_size_16_color_FFFFFF_t_70]  
步骤就是把待排序的数组先构造成一个堆（这里要利用完全二叉树的性质，比如在数组里面父节点的序号是i，那左孩子一定是2\*i，右孩子一定是2  
\*i+1），然后再构造成一个最大堆，就得到了一个有序的序列。  
**排序算法时间复杂度分析**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTkzOTgy_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTkzOTgy_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200228163325973.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTkzOTgy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTkzOTgy_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200228164230198.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTkzOTgy,size_16,color_FFFFFF,t_70