insertion_sort

小鱼儿 2024-04-18 22:50 58阅读 0赞

现在来讲下插入排序。

输入：a1,a2...an。用数组a\[n\]来存储。

输出：将n个数按升序排列。

实现的代码如下：

第一种（有监视哨）：

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

1.  \#include<iostream> 
2.  using namespace std;
3.  
4.  void insertion\_sort(int a\[\],int n) //插入排序 
5.  \{
6.  int i,j;
7.  
8.  for(i=2;i<=n;i++) //n-1次插入操作 
9.  \{
10. a\[0\]=a\[i\]; //a\[0\]是监视哨 
11. 
12. for(j=i-1;j>=0;j--)
13. \{
14. if(a\[j\]>a\[0\])
15. a\[j+1\]=a\[j\];
16. else
17. \{
18. a\[j+1\]=a\[0\];
19. break;
20. \}
21. \}
22. \}
23. \}
24. 
25. int main()
26. \{
27. int a\[101\];
28. int i,n;
29. 
30. while(cin>>n,n)
31. \{
32. for(i=1;i<=n;i++)
33. cin>>a\[i\];
34. 
35. insertion\_sort(a,n);
36. 
37. for(i=1;i<=n;i++)
38. cout<<a\[i\]<<" ";
39. 
40. cout<<endl<<endl;
41. \}
42. 
43. return 0;
44. \}

#include<iostream>
    using namespace std;
    
    void insertion_sort(int a[],int n)   //插入排序
    {
    	int i,j;
      
    	for(i=2;i<=n;i++)   //n-1次插入操作
    	{
    		a[0]=a[i];     //a[0]是监视哨
    
    		for(j=i-1;j>=0;j--)
    		{
    			if(a[j]>a[0])
    				a[j+1]=a[j];
    			else
    			{
    				a[j+1]=a[0];
    				break;
    			}
    		}
    	}
    }
    		
    int main()
    {
    	int a[101];
    	int i,n;
    
    	while(cin>>n,n)
    	{
    		for(i=1;i<=n;i++)
    			cin>>a[i];
    		
    		insertion_sort(a,n);
    		
    		for(i=1;i<=n;i++)
    			cout<<a[i]<<" ";
    
    		cout<<endl<<endl;
    	}
    
    	return 0;
    }

其中，函数insertion\_sort()，也可用以下这个：

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

1.  void insertion\_sort(int a\[\],int n)
2.  \{
3.  int i,j;
4.  
5.  for(i=2;i<=n;i++) //n-1次插入操作 
6.  \{
7.  a\[0\]=a\[i\]; //用a\[0\]来做监视哨，很巧妙 
8.  j=i-1;
9.  
10. while(a\[j\]>a\[0\])
11. \{
12. a\[j+1\]=a\[j\];
13. j--;
14. \}
15. 
16. a\[j+1\]=a\[0\];
17. \}
18. \}

void insertion_sort(int a[],int n)
    {
    	int i,j;
    
    	for(i=2;i<=n;i++)  //n-1次插入操作
    	{
    		a[0]=a[i];    //用a[0]来做监视哨，很巧妙
    		j=i-1;
    
    		while(a[j]>a[0])
    		{
    			a[j+1]=a[j];
    			j--;
    		}
    
    		a[j+1]=a[0];
    	}
    }

第二种（无监视哨）：

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

1.  \#include<iostream> 
2.  using namespace std;
3.  
4.  void insertion\_sort(int a\[\],int n)
5.  \{
6.  int i,j,tem;
7.  
8.  for(i=1;i<n;i++) //n-1次插入操作 
9.  \{
10. tem=a\[i\]; //待插元素 
11. j=i-1;
12. 
13. while(j>=0 && a\[j\]>tem) //寻找位置，j>=0是数组越界检查 
14. \{
15. a\[j+1\]=a\[j\];
16. j--;
17. \}
18. a\[j+1\]=tem;
19. \}
20. \}
21. 
22. int main()
23. \{
24. int a\[100\];
25. int i,n;
26. 
27. while(cin>>n,n)
28. \{
29. for(i=0;i<n;i++)
30. cin>>a\[i\];
31. 
32. insertion\_sort(a,n);
33. 
34. for(i=0;i<n;i++)
35. cout<<a\[i\]<<" ";
36. 
37. cout<<endl<<endl;
38. \}
39. 
40. return 0;
41. \}

#include<iostream>
    using namespace std;
    
    void insertion_sort(int a[],int n)
    {
    	int i,j,tem;
    
    	for(i=1;i<n;i++)  //n-1次插入操作
    	{
    		tem=a[i];   //待插元素
    		j=i-1;
    
    		while(j>=0 && a[j]>tem)   //寻找位置，j>=0是数组越界检查
    		{
    			a[j+1]=a[j];
    			j--;
    		}
    		a[j+1]=tem;
    	}
    }
    
    int main()
    {
    	int a[100];
    	int i,n;
    
    	while(cin>>n,n)
    	{
    		for(i=0;i<n;i++)
    			cin>>a[i];
    
    		insertion_sort(a,n);
    
    		for(i=0;i<n;i++)
    			cout<<a[i]<<" ";
    
    		cout<<endl<<endl;
    	}
    
    	return 0;
    }

个人觉得插入排序是一种比较基础的排序方法。思想也并不难理解。也就是将数组a\[n\]分为a\[1...j-1\]和a\[j...n\]两部分，其中a\[1...j-1\]已排序，而a\[j...n\]待排序。

那么，每次从a\[j...n\]中取出最前的数，并将其插入到a\[1...j-1\]中。这样的话a\[j...n\]的规模不断减小，而a\[1...j-1\]的规模则不断增大。直到数据全部排序。

Attention:

①插入排序是原地排序。基本上是在原有数组上操作，只需少量的辅助空间，如key和a\[0\]。

②插入排序的空间性能是O\[n^2\]的，空间性能为O\[n\]。

③插入排序每插入一个数，只是暂时确定该数在数组中的位置，也就是说每次插入不能确定一个数的最终位置。

④以上提到两种方法，有无监视哨，监视哨存在的主要目的就是避免数组下标越界检查。值得注意的是：如用a\[0\]作为监视哨，则a\[0\]不能存储有用数据。

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