部分排序数组C.
我有一个看起来像这样的数组：
int array[] = {4.53, 3.65, 7.43, 9.54, 0.72, 0.0} 我只是想知道我可以使用什么方法来对这个数组进行部分排序，以便将前三个最大的双打带到前面。 我正在寻找最有效的方法来获得这个数组中前三个最高的数字。
到目前为止，我一直在使用qsort ，但我只是在寻找另一种方法来做到这一点，甚至更快。 我知道qsort在最好的情况下是O(nlogn) ，在最坏的情况下是O(n^2) ，但有没有更有效的方法来实现这个问题？ 高效的意思是比O(nlogn)更好的方法。
任何帮助都会很棒
只需保持第一，第二，第三。
first = array[0]; second = array[1]; third = array[2]; /* scratch sort for three elements */ if(first < second) swap(first, second); if(first < third) swap(first, third); if(second < third) swap(second, third); /* now go through, bubbling up if we have a hit */ for(i=3;i
我不会尝试扩大到k = 4。 我认为三是关于硬编码的限制。 随着k变大，你需要转向正式的方法。
这并没有回答你实际问的问题，这是如何部分排序，但它似乎是你想要的。
如果您希望进行部分排序，可以使用快速排序，并在枢轴超出您感兴趣的边界时简单地返回。 所以我们的第一个支点分为五个，两个。 忽略最后两个，只实际执行最后五个的子排序。 但是虽然它比快速排序更快，但它不会改变游戏规则。 如果你可以得到第k个项目的保守上限（例如，它在最小值和平均值之间总是最多25％），你可以快速消除大部分数据。 如果你弄错了，那只是另一两遍。
使用快速排序方法
int sortfirstk_r(int *array, int N, int k) { int pivot = 0; int j = n -1; int i = 1; while(i <= j) { if(array[pivot] < array[i]) swap(array[i], array[j--]) else i++; } sortfirstk_r(array, i, k < i ? k : i); if(i < k) sortfirstk_r(array +i, N -i, k - i); }
（未经测试，在稍微棘手的排序逻辑中可能存在错误）。
然而，我们天真地使用第一个元素作为支点。 如果我们对大型数据集进行排序，并且它具有正态分布，并且我们想要前1％，则z得分为2.326。 多花点时间让我们得到一些抽样误差，然后我们首先使用一个枢轴设置，比平均值高出2.3个标准偏差。 然后我们将分布分为两组，前1％加一点，其余的。 我们不需要进一步处理剩下的事情，只需对顶层组进行排序。
对于您的特定问题，最快的方法是执行类似于下面的操作，因为您只需要三个元素:(可能更快使用优先级队列或不同的数据结构，但速度不会非常明显）
#include"stdio.h" void moveThreeMaxToFront(double * arr, int length); void moveMaxToFront(double*arr, int length); int main() { int i; double meh[]={ 5,3,1,7,2,9,11}; moveThreeMaxToFront(meh, 7); for(i=0; i<7; i++) printf("%f \n", meh[i]); } void moveThreeMaxToFront(double * arr, int length) { for(int i=0; i<3; i++) moveMaxToFront(arr++, length-i); } void moveMaxToFront(double* arr, int length) { int i; for(i=1; iarr[0]) { double tmp=arr[i]; arr[i]=arr[0]; arr[0]=tmp; } } }
但是，如果k变得非常大，以实现Quickselect或使用我认为实现快速选择的partial_sort方法，它可能会更快。 然而，给定情况的快速选择算法的平均常数约为3.4-4.4，略高于（3）以上的常数。 另请注意，quickselect的平均运行时间为O（n）。 使用中位数3可以保证运行时间，但不建议这样做，因为它会显着增加平均常数。 Intro-select正确处理这个以防止最坏情况下的quickselect同时保留其平均情况。
我建议基数排序它是这种情况下最有效的排序方法，并具有复杂度O（n）。 当找到三个最大数字时，你甚至可以稍微改变它。 你可以找到 – 理解基数短： https ： //www.cs.usfca.edu/~galles/visualization/RadixSort.html
如果我们应该找出三个最大的数字，那么我们可以运行findMax方法三次，一旦找到最大值，用数组中的最大值替换适当的索引(1, 2 or 3) 。 这样我们就会在c * O(n)时间复杂度的数组开始处为数组提供3最大的元素。
注意：事实上我必须找到前三个最大双打
double findMax(double arr[i], double prevMax){ double maximum = -100000000000; for(int i = 0; i < arr.length; i++){ if(arr[i] < prevMax) maximum = max(arr[i], maximum); } return maximum; }