PAT 1004 成绩排名

1.注意一下，数组大小即可。使用了冒泡排序和快速排序，冒泡稍微简洁点，不过平均时间复杂度来说，快速排序要小些。

#include 
#include 
#include 

using namespace std;



struct stu{
	string name;
	string number;
	int score;
};


// quick sort 快速排序
void Qsort(stu* s, int low, int high){
   
   
   if (high <= low) return;
    int i = low;
    int j = high + 1;
    int key = s[low].score;
    
    string key_name = s[low].name;
    string key_number = s[low].number;
    
    while (true)
    {
        
        while (s[++i].score < key)
        {
            if (i == high){
                break;
            }
        }
        
        while (s[--j].score > key)
        {
            if (j == low){
                break;
            }
        }
        if (i >= j) break;
        
        int temp = s[i].score;
        s[i].score= s[j].score;
        s[j].score = temp;
        
        string temp_name = s[i].name;
        s[i].name = s[j].name;
        s[j].name = temp_name;
        
        string temp_number = s[i].number;
        s[i].number = s[j].number;
        s[j].number = temp_number;
        
        
    }
    
    s[low].score = s[j].score;
    s[j].score = key;
    
    s[low].name = s[j].name;
    s[j].name = key_name;
    
    s[low].number = s[j].number;
    s[j].number = key_number;
    
    Qsort(s, low, j - 1);
    Qsort(s, j + 1, high);
}
 


int main()
{
   stu * s = new stu[10000];
   int n;
   cin>>n;
   
   for(int i=0;i>s[i].name>>s[i].number>>s[i].score;
   }
   
   Qsort(s,0,n-1);  //调用快速排序
   
   cout< s[j+1].score)
//		  	{    
//		  		 temp_score = s[j].score;
//		  		 temp_name = s[j].name;
//		  		 temp_number = s[j].number;
//		  	
//		  		 s[j].score = s[j+1].score;
//		  		 s[j].name = s[j+1].name;
//		  		 s[j].number = s[j+1].number;
//		  		 
//		  		 s[j+1].score = temp_score;
//		  		 s[j+1].name = temp_name;
//		  		 s[j+1].number = temp_number;
//			  }
//		   } 
//   } 
   
  // cout< 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5703444.html