根据出现的次数排序

今天在题库发芽网上看到一个排序的题目，觉得很有意思。
题目：

根据出现的次数排序

---

[1,2,3,5,3,2,3,2,1,3]
=>
[3,3,3,3,2,2,2,1,1,5]

同样多的话，大的排后面

---

刚看到这个题目，最直接的解法就是先统计数组中各个数出现的次数，并做一一对应存储起来，然后对次数进行排序，最后输出。
这里，我的方法是利用堆，而且是大根堆。堆的节点是一个数据结构

struct node
{
    int count;
    int key;
};

其中count表示出现次数，key表示关键字。该堆对count进行排序，如果遇到count相等，那么对key进行排序。每次插入时，都需要检查该key是否已经存在，如果存在，那么就将该key的count加1，并调整堆；否则，就插入堆中。
输出时，每次都取堆的第一个元素，然后调整堆。不过似乎堆在这种情况下，并没有提高性能。代码如下：
heap.h

#ifndef __HEAP_H__
#define __HEAP_H__

struct node
{
    int count;
    int key;
};
//数组是从1号位置开始存放数据，第0号位置存放的是数组的长度
typedef struct node datatype;

datatype heap_remove_max(datatype A[]);

void show(datatype A[])
{
    int i=0, j=0;
    datatype x;
    int k= A[0].count;
    for(i = 1; i<= k; i++)
    {
        x = heap_remove_max(A);
        for(j=0; j < x.count; j++)
            printf("%d ", x.key);
    }
    printf("\n");
}

int heap_find(datatype A[], int x)
{
    int end = A[0].count;
    int i=0;
    int child;
    int parent = 1;
    for(i=1 ; i <= end; i++)
    {
        if(x == A[i].key) //find

            return i;
    }
    return 0;
}

//插入是先查找，若不存在，则新建节点插入，否则，将更新节点
void heap_insert(datatype A[], int x)
{
    int child, parent;
    datatype temp;
    int ret = heap_find(A, x);
    if(ret)//find
    {
        A[ret].count ++;
        parent = ret/2;
        while(parent >= 1)
        {
            if( (A[parent].count < A[ret].count) ||
                ((A[ret].count == A[parent].count) && (A[ret].key < A[parent].key)) )
            {
                temp = A[ret];
                A[ret] = A[parent];
                A[parent] = temp;
                ret = parent;
                parent = parent/2;
            }
            else
                parent = 0;
        }
        return;
    }
    A[0].count = A[0].count + 1;
    child = A[0].count;
    A[child].count = 1;
    A[child].key = x;
     parent = child/2;
    while(parent>=1)
    {
        if( (A[child].count == A[parent].count) && (A[child].key < A[parent].key) )
        {
            temp = A[child];
            A[child] = A[parent];
            A[parent] = temp;
            child = parent;
            parent = parent/2;
        }
        else
            parent = 0;
    }
}

datatype heap_remove_max(datatype A[])
{
    int child,parent,n;
    datatype temp, max;
    n = A[0].count;
    if(n == 0)
        return max;
    
    max = A[1];
    A[1] = A[n];
    parent = 1;
    child = 2;
    while(child < n)
    {
        if( (A[child].count < A[child+1].count) ||
            ((A[child].count == A[child+1].count)&&(A[child].key > A[child+1].key)))
            child = child+1;
        if( (A[parent].count < A[child].count) ||
            (A[child].count == A[parent].count) && (A[child].key < A[parent].key) )
        {
            temp = A[parent];
            A[parent] = A[child];
            A[child] = temp;
            parent = child;
            child = 2*child;
        }
        else
            child = n;
    }
    A[0].count--;
    return max;
}
#endif

main.c

#include <stdio.h>
#include "heap.h"

int main()
{
    datatype A[100] = {0,0};
    int buf[17] = {1,2,3,5,3,2,3,2,1,3,6,7,8,9,10,3,5};
    int i=0;
    for(i=0; i<17; i++)
        heap_insert(A, buf[i]);
    show(A);
    return 0;
}

执行结果：

---

[root@localhost test]# gcc main.c -o main
[root@localhost test]# ./main
3  3  3  3  3  2  2  2  1  1  5  5  6  7  8  9  10 

---

如果有更好的解决方法，欢迎评论交流。