最适合的排序算法 [英] Most suitable sorting algorithm

问题描述

我要排序大数组大小100000双打的。

I have to sort a large array of doubles of size 100000.

的一点是，我不希望整个数组排序，但只找到降序排列最大的20000元。

The point is that I do not want to sort the whole array but only find the largest 20000 elements in descending order.

目前我使用的选择排序。任何的方式来提高性能？​​

Currently I am using selection sort. Any way to improve the performance?

推荐答案

100,000不是一个非常大的阵列上最先进的设备。你确定你不能只是排序所有的人都用一个标准库排序功能？

100,000 is not a very large array on most modern devices. Are you sure you can't just sort all of them using a standard library sorting function?

您可以通过使用堆排序的变化避免完全排序。通常，在一个堆排序构建整个数据集的堆（你的情况100000元）。相反，只允许堆增长到20000元。保留的最大的元素在堆的顶部。一旦堆已满（20000元素），则比较设置到堆摊的顶部的数据的每一后续元件。如果下一个数据集元素比所述堆的顶部时，只是跳过它。如果它比堆的顶部变小，弹出堆的顶部，并插入从数据集的元素

You can avoid a full sort by using a variation of heapsort. Normally in a heapsort you build a heap of the entire data set (100,000 elements in your case). Instead, only allow the heap to grow to 20,000 elements. Keep the largest element at the top of the heap. Once the heap is full (20,000 elements), you compare each subsequent element of the data set to the top of the heap. If the next data set element is larger than the top of the heap, just skip it. If it's smaller than the top of the heap, pop the top of the heap and insert the element from the data set.

一旦你把整个数据集走了，你的数据集的20,000个最小元素的堆。你可以弹出他们一个接一个到一个数组中有一个排序的数组。

Once you've gone through the entire data set, you have a heap of the 20,000 smallest elements of the data set. You can pop them one-by-one into an array to have a sorted array.

这个算法为O（N日志K）的时间，其中N是数据集的大小（100,000在你的例子）和K是你想保留（20,000在你的例子）元素的数量。

This algorithm runs in O(N log K) time, where N is the size of the data set (100,000 in your example) and K is the number of elements you want to keep (20,000 in your example).

这篇关于最适合的排序算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！