shell_sort

绝地灬酷狼 2024-04-18 22:50 46阅读 0赞

希尔排序是直接插入排序的改进版。首先设置步长len，然后分组，下标之差为步长整数倍的分为一组。然后去len/2作为步长，直至len=1，此时就是直接

插入排序了。

代码如下：

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  \#include<iostream> 
2.  using namespace std;
3.  
4.  void shell\_sort(int a\[\],int n)
5.  \{
6.  int i,j,len,tem; //len为步长 
7.  
8.  len=n/2; //默认步长设为n/2 
9.  
10. while(len>=1)
11. \{
12. for(i=len;i<n;i++) //当len=1时就是插入排序了 
13. \{
14. tem=a\[i\];
15. j=i-len;
16. 
17. while(j>=len-1 && a\[j\]>tem)
18. \{
19. a\[j+len\]=a\[j\];
20. j-=len;
21. \}
22. a\[j+len\]=tem;
23. \}
24. 
25. len/=2;
26. \}
27. \}
28. 
29. int main()
30. \{
31. int a\[100\];
32. int i,n;
33. 
34. while(cin>>n,n)
35. \{
36. for(i=0;i<n;i++)
37. cin>>a\[i\];
38. 
39. shell\_sort(a,n);
40. 
41. for(i=0;i<n;i++)
42. cout<<a\[i\]<<" ";
43. 
44. cout<<endl<<endl;
45. \}
46. 
47. return 0;
48. \}

#include<iostream>
    using namespace std;
    
    void shell_sort(int a[],int n)
    {
    	int i,j,len,tem;   //len为步长
    
    	len=n/2;    //默认步长设为n/2
    
    	while(len>=1)
    	{
    		for(i=len;i<n;i++)   //当len=1时就是插入排序了
    		{
    			tem=a[i];
    			j=i-len;
    
    			while(j>=len-1 && a[j]>tem)
    			{
    				a[j+len]=a[j];
    				j-=len;
    			}
    			a[j+len]=tem;
    		}
    
    		len/=2;
    	}
    }
    
    int main()
    {
    	int a[100];
    	int i,n;
    
    	while(cin>>n,n)
    	{
    		for(i=0;i<n;i++)
    			cin>>a[i];
    
    		shell_sort(a,n);
    
    		for(i=0;i<n;i++)
    			cout<<a[i]<<" ";
    
    		cout<<endl<<endl;
    	}
    
    	return 0;
    }

Attention:

①希尔排序是原地排序。

②时间复杂度为o(nlog2n)，空间复杂度为o(n)。

[view plain]: http://blog.csdn.net/lulipeng_cpp/article/details/7447053#