背景:
假設(shè)有一教師依學(xué)生座號輸入考試分?jǐn)?shù)，現(xiàn)希望在輸入完畢後自動顯示學(xué)生分?jǐn)?shù)的排行，當(dāng)然學(xué)生的分?jǐn)?shù)可能相同。
實現(xiàn)思路:
這個問題基本上要解不難，只要使用額外的一個排行陣列走訪分?jǐn)?shù)陣列就可以了，直接使用下面的程式片段作說明：
for(i = 0; i < count; i++) {
juni[i] = 1;
for(j = 0; j < count; j++) {
if(score[j] > score[i])
juni[i]++;
}
}
printf("得分\t排行\(zhòng)n");
for(i = 0; i < count; i++)
printf("%d\t%d\n", score[i], juni[i]);
上面這個方法雖然簡單，但是反覆計算的次數(shù)是n^2，如果n值變大，那麼運算的時間就會拖長；改變juni陣列的長度為n+2，並將初始值設(shè)定為0，如下所示：
接下來走訪分?jǐn)?shù)陣列，並在分?jǐn)?shù)所對應(yīng)的排行陣列索引元素上加1，如下所示：
將排行陣列最右邊的元素設(shè)定為1，然後依序?qū)⒂疫叺脑刂导又磷筮呉粋€元素，最後排行陣列中的「分?jǐn)?shù)+1」」就是得該分?jǐn)?shù)的排行，如下所示：
這樣的方式看起來複雜，其實不過在計算某分?jǐn)?shù)之前排行的人數(shù)，假設(shè)89分之前的排行人數(shù)為x人，則89分自然就是x+1了，這也是為什麼排行陣列最右邊要設(shè)定為1的原因；如果89分有y人，則88分自然就是x+y+1，整個陣列右邊元素向左加的原因正是如此。
如果分?jǐn)?shù)有負(fù)分的情況，由於C/C++或Java等程式語言無法處理負(fù)的索引，所以必須加上一個偏移值，將所有的分?jǐn)?shù)先往右偏移一個範(fàn)圍即可，最後顯示的時候記得減回偏移值就可以了。
實現(xiàn)算法:
1 package 算法.得分排序;
2
3 import java.io.*;
4
5 public class 得分排序 {
6 public static void main(String[] args) throws NumberFormatException,
7 IOException {
8 final int MAX = 5;
9 final int MIN = 0;
10 int[] score = new int[MAX + 1];
11 int[] juni = new int[MAX + 2];
12 System.out.println();
13 BufferedReader reader = new BufferedReader(new InputStreamReader(
14 System.in));
15 int count = 0;
16 do {
17 System.out.print("輸入分?jǐn)?shù)，-1結(jié)束：");
18 score[count++] = Integer.parseInt(reader.readLine());
19 } while ((score[count - 1] != -1));
20 count--;
21 for(int i = 0; i< count; i++)
22 juni[score[i]]++;//將分?jǐn)?shù)的排行列陣置為1
23 juni[MAX + 1] = 1;//將元素下標(biāo)為ＭＡＸ＋１的位置置為１，也即是第一名，之后不會再改變了
24 for (int i = MAX; i >= MIN; i--)
25 juni[i] = juni[i] + juni[i + 1];//排名陣列元素向左加
26 System.out.println("得分\t排行");
27 for (int i = 0; i < count; i++) {
28 //score[i]的排名對應(yīng)是juni[score[i] + 1]的值
29 System.out.println(score[i] + "\t" + juni[score[i] + 1]);
30 }
31 /*
32 for (int i = 0; i < count; i++) {
33 System.out.print("score[" + i + "] = " + score[i] +" " );
34 }
35 System.out.println();
36 for (int i = 0; i < count; i++) {
37 System.out.print("jnui[" + i + "] = " + juni[i] +" " );
38
39 }
40 System.out.println(juni[5]+" "+ juni[6]);
41 */
42 }
43 }
44