拿到这个问题,我首先想到的是:一个完全不懂编程的人碰到这个问题,他会怎么做? 我觉得,一般人会把根据花色分成四堆,然后分别排序(这里怎么排每个人就会有不同的方法了),最后再收集起来。这个思想就很类似于基数排序了。

基数排序是比较稳定而且相对高效率的排序算法。于是我就用基数排序实现了。
先根据点数分成13堆,收集起来,再根据花色分成4堆,再收集,就okay了。

值得一提的是,我必须使用链表来组织牌堆,因为如果用数组的话,用基排就有“直接计算下标”的嫌疑,就犯规了;而现实中整理扑克的时候,我们的桌子上并没有52个格子,来让你排放扑克牌,所以用链表来表示还是比较符合实际情况的……实际上,这个问题其实还是直接根据牌面计算下标最快——但是规则不允许这么做——所以我们实际上是在寻找尽可能快但是不能是最快的算法。但是如果把问题改成“排序缺失了若干张未知牌的一副扑克”,就不存在这个问题了。而使用链表的基数排序仍然可以解决——所以我说了这么多,用意其实是在于说明,我没有犯规……

以下是C语言代码:

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

typedef struct poker poker;

struct poker{
    int suit;//0-spade, 1-heart, 2-flower, 3-box;
    int number;//J-11, Q-12, K-13, A-14;
    poker* next;
};

int _random(x){
    srand((int)time(0));
    return rand()%x;
}

poker* create_pile(){
    int n, i;
    int a[52];
    for(i = 0; i < 52; i++)
        a[i] = i;
    poker* pile = 0;
    for(n = 52; n > 0; n--){
        int t = _random(n);
        poker* p = malloc(sizeof(poker));
        p->suit = a[t]/13;
        p->number = a[t]%13 + 2;
        p->next = pile;
        pile = p;
        a[t] = a[n-1];
    }
    return pile;
}

poker* sort(poker* pile){
    poker* head[13];
    poker* tail[13];
    int i;
    for(i = 0; i < 13; i++){
        head[i] = tail[i] = 0;
    }
    //first round allocate;
    while(pile != 0){    
        poker* p = pile;
        pile = pile->next;
        p->next = 0;

        int number = p->number;
        if(tail[number-2] == 0){
            head[number-2] = tail[number-2] = p;
        }
        else{
            tail[number-2]->next = p;
            tail[number-2] = p;
        }
    }
    //collect;
    pile = head[0];
    for(i = 0; i < 12; i++){
        tail[i]->next = head[i+1];
        head[i] = tail[i] = 0;
    }
    //second round allocate;
    while(pile != 0){    
        poker* p = pile;
        pile = pile->next;
        p->next = 0;

        int suit = p->suit;
        if(tail[suit] == 0){
            head[suit] = tail[suit] = p;
        }
        else{
            tail[suit]->next = p;
            tail[suit] = p;
        }
    }
    //collect;
    pile = head[0];
    for(i = 0; i < 3; i++){
        tail[i]->next = head[i+1];
        head[i] = tail[i] = 0;
    }
    return pile;
}

int main(){
    poker* pile = create_pile();
    poker* p = pile;
    printf("Before sorted:\n");
    while(p != 0){
        printf("%d, %d\n", p->suit, p->number);
        p = p->next;
    }
    printf("=============\nAfter sorted:\n");
    pile = sort(pile);
    p = pile;
    while(p != 0){
        printf("%d, %d\n", p->suit, p->number);
        p = p->next;
    }
    return 0;
}

关于基数排序的介绍