假设我有一个数组,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}
具有相同频率的任何值都可以保持升序排列,这就是为什么我在开始时使用选择排序的原因。
最简单的方法是将频率存储在单独的表中。int count [10];
如果仅期望值0
to ,则这种表的简单/天真的实现类似于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] */
有更有效,更高级的方法来执行此操作,但以上内容对于初学者而言就足够了。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句