指針數組在排序算法中的應用

基本思路

排序算法雖然好用，但會破壞掉原有數組的順序。有時候，我們并不想這樣（例如在使用結構體、共用體）。

這時候，我們可以創建一個指針數組，分別指向原數組中的每個元素，對指針數組進行排序。基本思想就是在冒泡排序時定義的中間臨時變量是一個指針變量，冒泡時交換的是指針，即可在不破壞原有數組的順序下得到排序結果。若想調用排序前的直接調用原數組，若想調用排序后的數組，只需要對排序后的指針數組進行解引用即可。

代碼實現

以下是以最簡單的排序方法——冒泡排序法實現的C語言代碼：

//指針數組排序
#include<stdio.h>
int main(){
    int m[10]={10,80,89,66,54,1708,108,1816,1024,1712};
    int *p[10];
    printf("before:\n");
    printf("ori arr:\n");
    for(int i=0;i<10;i++){
        printf("%d\t",m[i]);
    }
    printf("pointer arr:\n");
    for(int i=0;i<10;i++)
        p[i]=&m[i];
    for(int i=0;i<10;i++){
        printf("%d(%p)\t",*p[i],p[i]);
    }
    //開始排序(冒泡法)
    for(int j=0;j<10-1;j++){//冒泡輪數=已排序指針個數
        for(int i=0;i<10-1-j;i++){
            if(*p[i]>*p[i+1]) {//冒泡:和相鄰項做比較
                int *t;
                t=p[i+1];
                p[i+1]=p[i];
                p[i]=t;
            }
        }
    }
    printf("after:\n");
    printf("ori arr:\n");
    for(int i=0;i<10;i++){
        printf("%d\t",m[i]);
    }
    printf("pointer arr:\n");
    for(int i=0;i<10;i++){
        printf("%d(%p)\t",*p[i],p[i]);
    }
    return 0;
}

例:初進ACM

描述

歡迎大家來參加計算機科學與工程學院ACM競賽；既然來參加比賽，想必也知道，比賽的排名的規則吧；

首先我們按出題量排名，出題量多者，排名靠前，其次出題量一樣是看出題的時間，但當時間一樣時，看你的姓名的字典序排名，但名次一樣；當然提交錯誤，會有懲罰，每提交錯一次，罰時20分鐘；（提示：一共有5道題，題目沒有通過不罰時）

輸入

首先輸出一個整數n，代表n個人；（0 < n < 100）

再有n行，每一行有一個人名，（每個人名都是由小寫字母組成，且長度不超過10）在人名后面有10個數，前5個數代表出每一道題所用的時間（時間的不超過120.），后5個數代表每一道題提交錯誤的次數（錯誤次數不超過10.）；當時間為0時，說明這道題沒做出來；

輸出

輸出排名，每一個人一行；

輸入樣例 1 

2
wula 5 10 0 0 0 0 1 3 0 0
sese 18 5 17 0 0 2 0 2 0 0
4
bsd 0 0 1 5 9 1 1 1 2 2
aerwt 0 3 0 7 25 10 1 1 1 2
ciuu 10 20 30 40 50 2 3 4 5 6
dyrtu 11 22 33 44 55 1 2 3 3 6

輸出樣例 1

1st sese
2st wula
1st dyrtu
2st ciuu
3st aerwt
3st bsd

#include <stdio.h>
#include<string.h>
int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        //對每個ACMer的名字、AC數、AC時間、WA數的數據獲取，并計算加入罰時后的總時間
        struct acm {
            char name[11];
            int single[5];
            int wa[5];
            int ac;
            int sum;
            int rank;
        } stu[n];
        memset(stu, 0, sizeof(stu));//初始化結構體數組為0，避免被裝入垃圾數據
        struct acm *p[n];
        for (int i = 0; i < n; i++)
            p[i] = &stu[i];
        for (int i = 0; i < n; i++) {
            scanf("%s", stu[i].name);
            for (int k = 0; k < 5; k++) {
                scanf("%d", &stu[i].single[k]);
                if (p[i]->single[k] != 0) {
                    p[i]->ac++;
                }
                p[i]->sum += p[i]->single[k];
            }
            for (int k = 0; k < 5; k++) {
                scanf("%d", &stu[i].wa[k]);
                if (p[i]->single[k] != 0) {
                    p[i]->sum += (p[i]->wa[k] * 20);
                }
            }
        }
        //下面對AC數進行指針排序
        for (int j = 0; j < n - 1; j++) {
            for (int i = 0; i < n - 1 - j; i++) {
                if (p[i]->ac < p[i + 1]->ac) {
                    struct acm *t;
                    t = p[i + 1];
                    p[i + 1] = p[i];
                    p[i] = t;
                } else if (p[i]->ac == p[i + 1]->ac) {
                    if (p[i]->sum > p[i + 1]->sum) {
                        struct acm *t;
                        t = p[i + 1];
                        p[i + 1] = p[i];
                        p[i] = t;
                    } else if (p[i]->sum == p[i + 1]->sum) {
                        if (strcmp(p[i]->name, p[i + 1]->name) > 0) {
                            struct acm *t;
                            t = p[i + 1];
                            p[i + 1] = p[i];
                            p[i] = t;
                        }
                    }
                }
            }
        }
        int count = 1; // 初始化計數器為1
        for(int i=0;i<n;i++){
            if(i==0){
                p[i]->rank=1;
            }else{
                if(p[i]->ac==p[i-1]->ac && p[i]->sum==p[i-1]->sum){
                    p[i]->rank=p[i-1]->rank; // 如果當前元素與前一個元素并列，則他們的排名相同
                    count++; // 并列的元素數量加一
                }else{
                    p[i]->rank=p[i-1]->rank+count; // 如果當前元素與前一個元素不并列，則他的排名應該是前一個元素的排名加上并列的元素數量
                    count=1; // 重置并列的元素數量為1
                }
            }
        }
            for (int i = 0; i < n; i++) {
                printf("%dst ", p[i]->rank);
                printf("%s\n", p[i]->name);
            }
    }
    return 0;
}

中間處理并列時的思路很巧妙。