无标题文档

排序算法

1.冒泡排序(从小到大排序)：
#include<iostream>
#include<iomanip>
using namespace std;
int main(){
	int n,i,j,k,a[1001];
	cin>>n;
	for(i=1;i<=n;i++)cin>>a[i];
	for(i=1;i<=n-1;i++)
	   for (j=1;j<=n-i;j++)
	   if(a[j]>a[j+1]){
	   	  k=a[j];
	   	  a[j]=a[j+1];
	   	  a[j+1]=k;
	   }
	for(i=1;i<=n;i++)cout<<setw(4)<<a[i];
	
}  
改进的冒泡排序：

#include<iostream>
#include<iomanip>
using namespace std;
int main(){
	int n,i,j,k,a[1001],f;
	cin>>n;
	for(i=1;i<=n;i++)cin>>a[i];
	for(i=1;i<=n-1;i++){
	    f=1;
	   for (j=1;j<=n-i;j++)
	   if(a[j]>a[j+1]){
	   	  k=a[j];
	   	  a[j]=a[j+1];
	   	  a[j+1]=k;
	   	  f=0;
	   }
	   if (f==1)break;
	}   
	for(i=1;i<=n;i++)cout<<a[i]<<" ";
	return 0;
	
}

思考：看程序写结果：
#include<iostream>
using namespace std;
int main(){
int  i,j,k ,a[6];

for(i=1;i<=5;i++)cin>>a[i] ;
  for(i=1;i<=4;i++)
for(j=5;i>=i+1;i--){
      
        if (a[j]<a[j-1]) {
            k=a[j];
            a[j]=a[j-1];
            a[j-1]=k;  
       }
   for(i=1;i<=5;i++)cout<<a[i] ;
  return 0;
}
输入：5 3 6 4 8
输出：3   4   5   6   8

2.选择排序(从小到大排序)：
#include<iostream>
#include<iomanip>
using namespace std;
int main(){
	int n,i,j,k,a[1001],f;
	cin>>n;
	for(i=1;i<=n;i++)cin>>a[i];
	for(i=1;i<=n-1;i++){   
	   for (j=i+1;j<=n;j++)
	   if(a[j]<a[i]){
	   	  k=a[j];
	   	  a[j]=a[i];
	   	  a[i]=k;
	   }
	    
	}   
	for(i=1;i<=n;i++)cout<<a[i]<<" ";
	return 0;
	
}

改进的选择排序：
#include<iostream>
#include<iomanip>
using namespace std;
int main(){
	int n,i,j,k,a[1001],f;
	cin>>n;
	for(i=1;i<=n;i++)cin>>a[i];
	for(i=1;i<=n-1;i++) 
	{
	    f=i;  
	   for (j=i+1;j<=n;j++) 
	    if(a[j]<a[f]) f=j;
	    if (f!=i){
		    k=a[i];
	        a[i]=a[f];
	        a[f]=k;	
		}    
	    
	}     
	for(i=1;i<=n;i++)cout<<a[i]<<" ";
	return 0;
	
}

3.插入排序:

#include<iostream>
#include<iomanip>
using namespace std;
int main(){
	int n,i,j,k,a[1001],r;
	cin>>n;
	for(i=1;i<=n;i++)cin>>a[i];
	for(i=2;i<=n;i++) 
	{
	    r=a[i];j=i-1;  
        while (r<a[j]&&j>0) {
        	a[j+1]=a[j];
        	j--;
		}
	    a[j+1]=r;
	}     
	for(i=1;i<=n;i++)cout<<a[i]<<" ";
	return 0;
	
}

4.数学黑洞6174。已知：一个任意的四位正整数（全相同的除外，如1111）。将数字重新组合成一个最大的数和最小的数相减，重复这个过程，最多七步，必得6174。即：7641－1467＝6174。将永远出不来。
求证：所有四位数数字（全相同的除外），均能得到6174。输出掉进黑洞的步数。	（★★★）

样例：
输入：
3294
输出：
4
{分析：3294先分解最大值和最小值
9432-2349=7083 第1步
8730-0378=8352 第2步
8532-2358=6174 第3步
7641-1476=6174 第4步：因为目前的结果在前面步骤的结果中出现过所以说掉进了黑洞。
}
程序：

#include<iostream>
#include<iomanip>
using namespace std;
int main(){
	int f,i,j,k,m,n,x,y,t,buzhou,a[5],b[11];
	t=0;buzhou=0;
	cin>>n;
	do{
		t++;
		b[t]=n;
		k=0;
		while(n>0){
			k++;
			a[k]=n%10;
			n=n/10;
		}
		for(i=1;i<=3;i++)
		  for(j=i+1;j<=4;j++)
		  if (a[j]<a[i]){
		  	m=a[j];a[j]=a[i];a[i]=m;
		  }
		x=0;y=0;
		for(i=4;i>=1;i--) x=x*10+a[i];
		for(i=1;i<=4;i++)y=y*10+a[i];
		k=x-y;f=0;
		for(i=1;i<=t;i++)
		if (k==b[i]){
			f=1;break;
		} 
		buzhou++;
		n=k;
	} while(f==0);
	cout<<buzhou;
	return 0;
	
}