heap_sort

骑猪看日落 2024-04-18 22:50 52阅读 0赞

堆排序是利用堆来进行排序。

堆的定义：n个元素的序列（a1,a2...an）当且仅当满足下面关系时，称为堆。

（a(i)<=a(2\*i) && a(i)<=a(2\*i+1)）或者（a(i)>=a(2\*i) && a(i)>=a(2\*i+1)）其中，2\*i+1<=n。

堆的模型：可以借助完全二叉树来理解。每一节点的值均不大于或不小于其左右孩子节点的值。

代码如下：

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

1.  \#include<iostream> 
2.  using namespace std;
3.  
4.  void shift(int a\[\],int k,int m) //调整堆，以k为根，m个数据 
5.  \{
6.  int i,j,tem;
7.  bool finished;
8.  
9.  tem=a\[k\];
10. finished=false;
11. i=k;
12. j=2\*i;
13. 
14. while(j<=m && finished==false)
15. \{
16. if(j<m && a\[j\]<a\[j+1\]) //左右孩子的大值用j指示 
17. j++;
18. 
19. if(tem>=a\[j\])
20. finished=true;
21. else
22. \{
23. a\[i\]=a\[j\];
24. i=j;
25. j\*=2;
26. \}
27. \}
28. 
29. a\[i\]=tem;
30. \}
31. 
32. void heap\_sort(int a\[\],int n)
33. \{
34. int i,tem;
35. 
36. for(i=n/2;i>=1;i--) //初始建堆 
37. shift(a,i,n);
38. 
39. for(i=n;i>=2;i--)
40. \{
41. tem=a\[1\]; //输出大数到数组尾部 
42. a\[1\]=a\[i\];
43. a\[i\]=tem;
44. 
45. shift(a,1,i-1); //调整堆 
46. \}
47. \}
48. 
49. int main()
50. \{
51. int i,n,a\[101\];
52. 
53. while(cin>>n,n)
54. \{
55. for(i=1;i<=n;i++) //注意：存放有用数据下标从1开始，建堆需要 
56. cin>>a\[i\];
57. 
58. heap\_sort(a,n);
59. 
60. for(i=1;i<=n;i++)
61. cout<<a\[i\]<<" ";
62. cout<<endl<<endl;
63. \}
64. 
65. return 0;
66. \}

#include<iostream>
    using namespace std;
    
    void shift(int a[],int k,int m)  //调整堆，以k为根，m个数据
    {
    	int i,j,tem;
    	bool finished;
    
    	tem=a[k];
    	finished=false;
    	i=k;
    	j=2*i;
    
    	while(j<=m && finished==false)
    	{
    		if(j<m && a[j]<a[j+1])  //左右孩子的大值用j指示
    			j++;
    
    		if(tem>=a[j])
    			finished=true;
    		else
    		{
    			a[i]=a[j];
    			i=j;
    			j*=2;
    		}
    	}
    
    	a[i]=tem;
    }
    
    void heap_sort(int a[],int n)
    {
    	int i,tem;
    
    	for(i=n/2;i>=1;i--)  //初始建堆
    		shift(a,i,n);
    
    	for(i=n;i>=2;i--)
    	{
    		tem=a[1];    //输出大数到数组尾部
    		a[1]=a[i];
    		a[i]=tem;
    
    		shift(a,1,i-1);    //调整堆
    	}
    }
    
    int main()
    {
    	int i,n,a[101];
    
    	while(cin>>n,n)
    	{
    		for(i=1;i<=n;i++)   //注意：存放有用数据下标从1开始，建堆需要
    			cin>>a[i];
    
    		heap_sort(a,n); 
    
    		for(i=1;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/7467736#