如何将数组索引从最不频繁排序到最频繁？

Question

假设我有一个数组int[] a = {1, 1, 5, 1, 7, 5}

我想按频率对数组进行排序，就像7在数组中出现了1次，所以它们走在前面，然后第5次出现了2次，最后出现了1次，这是最常见的。

预期的结果应该是{7, 5, 5, 1, 1, 1}

我试图编写一个通用结构，selection_sort只需将数组按升序排序即可。但我不确定这是否有用。

//I know how selection sort works, heres the code I wrote
int selection_sort(int a[], int len) {
    int pos = 0;
    for (int i = 0; i < len - 1; ++i) {
        pos = i;
        for (int j = i + 1; j < len; ++j) {
            if (a[j] < a[pos]) {
                pos = j;
            }
        }
        swap(&a[i], &a[pos]); 
    }
    return a[];
}

a[] = selection_sort(a[], len);
    int i;
    for (i = 0; i < len; i++) {
        while (a[i] == a[i + 1]) {
        //dont know what to put here
        }
    }

编辑:我所举的例子对降序排序有点误导，我将做另一个示例{3, 4, 3, 5, 1, 4, 2} => {1, 2, 5, 3, 3, 4, 4}

任何具有相同频率的值都可以保持升序，这就是为什么我在开始时使用了选择排序。

Answer 1

最简单的方法是将频率存储在一个单独的表中。如果我们只期望从0到9的值，那么这种表的简单/简单实现类似于9。

在这种情况下，您必须迭代数据一次才能映射事件：

for(size_t i=0; i<sizeof a/sizeof *a; i++)
  count[ a[i] ]++;

在那之后，count看起来就像{0, 3, 0, 0, 0, 2, 0, 1, 0, 0}。

现在可以根据此表对a进行排序，方法是让排序算法比较该表中的项：

if( count[ a[x] ] < count[ a[y ] ) 
  /* then place a[x] before a[y] */

有更有效和更先进的方法来做到这一点，但是上面的方法应该足以满足初学者的需要。

Answer 2

您应该对频率进行排序(以及每个频率所指向的索引所指向的信息)；然后运行长度将每个频率解码为索引。

如果索引和频率足够短，则可以将两个值打包到相同的单词：uint32_t sorted_key = (frequency << 16) + index;。对这些键进行排序也将保持索引的(某些)顺序。

本质上，您只需要按频率对元组(1,3)、(5,2)、(7,1)进行排序，如果是tie，则按索引排序。随后，( 1，3)被解码到11 1，(5,2)被解码到5 5，( 7 ,1)被解码到7。