备战考研算法笔记（五）成绩排序

题目描述：: 用一维数组存储学号和成绩，然后，按成绩排序输出。

输入：: 输入第一行包括一个整数N(1<=N<=100)，代表学生的个数。
接下来的N行每行包括两个整数p和q，分别代表每个学生的学号和成绩。

输出：: 按照学生的成绩从小到大进行排序，并将排序后的学生信息打印出来。
如果学生的成绩相同，则按照学号的大小进行从小到大排序。

样例输入：

样例输出：

2 87
1 90
3 92

 1 #include <stdio.h>
 2 #include "StdAfx.h"
 3 #include <malloc.h>
 4 
 5 //快速排序
 6 void quick_sort(int s[], int l, int r,int stu[])
 7 {
 8     if (l < r)
 9     {
10               
11         int i = l, j = r, x = s[l],y=stu[l];
12         while (i < j)
13         {
14             while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
15                             j--; 
16             if(i < j)
17                          {   s[i++] = s[j];
18             stu[i-1]=stu[j];}
19             
20             while(i < j && s[i] <x) // 从左向右找第一个大于等于x的数
21                             i++; 
22             if(i < j)
23             {
24                 if(s[i]==x)
25                 {
26                     if(stu[i]>y)
27                     {
28                             s[j--] = s[i];
29                             stu[j+1]=stu[i];
30                     }
31                 }
32                 else
33                 {  
34                             s[j--] = s[i];
35                             stu[j+1]=stu[i];
36                 }
37             }
38         }
39         s[i] = x;
40         stu[i]=y;
41         quick_sort(s, l, i - 1,stu); // 递归调用
42         quick_sort(s, i + 1, r,stu);
43     }
44 }
45 
46 int main()
47 {
48   int length;
49   while(scanf("%d",&length)!=EOF&&length>=1&&length<=100)
50   {
51     int *stu;
52     int *grade;
53     stu=(int*)malloc(length*sizeof(int));
54     grade=(int*)malloc(length*sizeof(int));
55     for(int i=0;i<length;i++)
56     {
57         scanf("%d %d",&stu[i],&grade[i]);
58     }
59     quick_sort(grade,0,length-1,stu);
60     //printf("
");
61     for(int i=0;i<length;i++)
62     {
63         printf("%d %d
",stu[i],grade[i]);
64     }
65   }
66 
67   return 0;
68 }

又是WA，我也不知道原因，真是蛋疼啊！

的确发现了错误，但不知道原因，难道这里不适合用快速排序？

后来发现了问题，理解了快速排序的精髓

#include <stdio.h>
 
#include <malloc.h>
 
//快速排序
void quick_sort(int s[], int l, int r,int stu[])
{
    if (l < r)
    {
               
        int i = l, j = r, x = s[l],y=stu[l];
        while (i < j)
        {
            while(i < j && (s[j] > x||(s[j]==x&&stu[j]>y)))// 从右向左找第一个小于x的数 或者等于x但是学号小于y
                            j--; 
 
            if(i < j)
            {
                 
                     s[i++] = s[j];
                     stu[i-1]=stu[j];
                  
            }
            while(i < j && (s[i] <x||(s[i]==x&&stu[i]<y))) // 从左向右找第一个大于x的数或者等于x但是学号大于y
                            i++; 
            if(i < j)
            {
                            s[j--] = s[i];
                            stu[j+1]=stu[i];
                 
            }
        }
        s[i] = x;
        stu[i]=y;
        quick_sort(s, l, i - 1,stu); // 递归调用
        quick_sort(s, i + 1, r,stu);
    }
}
 
int main()
{
  int length;
  while(scanf("%d",&length)!=EOF&&length>=1&&length<=100)
  {
    int *stu;
    int *grade;
    stu=(int*)malloc(length*sizeof(int));
    grade=(int*)malloc(length*sizeof(int));
    for(int i=0;i<length;i++)
    {
        scanf("%d %d",&stu[i],&grade[i]);
    }
    quick_sort(grade,0,length-1,stu);
    //printf("
");
    for(int i=0;i<length;i++)
    {
        printf("%d %d
",stu[i],grade[i]);
    }
  }
 
  return 0;
}
/**************************************************************
    Problem: 1196
    User: joilee
    Language: C++
    Result: Accepted
    Time:40 ms
    Memory:1416 kb
****************************************************************/