什么是排序百万整数整数时，从区间[1100]最快的方法是什么？ [英] What is the fastest way to sort 1 million integers when integers are from the range [1,100]?

问题描述

注：我想过基数排序，桶排序，计数排序

Notes: I've thought about Radix sort, bucket sort, counting sort.

反正是有实现大O（N）？

Is there anyway to achieve big O(n)?

推荐答案

您可以使用计数排序。

计数排序（有时被称为超排序或数学排序）是一个排序算法（如桶排序）利用知道数字的范围的阵列中被排序（数组A）。

Counting sort (sometimes referred to as ultra sort or math sort) is a sorting algorithm which (like bucket sort) takes advantage of knowing the range of the numbers in the array to be sorted (array A).

计数排序是一个稳定的排序，并具有Θ第（n + k），其中n和k是阵列A的长度（输入数组）和C（计数阵列），分别的运行时间。为了使这种算法是有效的，K必须不大于n大得多。

Counting sort is a stable sort and has a running time of Θ(n+k), where n and k are the lengths of the arrays A (the input array) and C (the counting array), respectively. In order for this algorithm to be efficient, k must not be much larger than n.

在这种情况下，k为100，n为百万

In this case k is 100 and n is 1000000.

这篇关于什么是排序百万整数整数时，从区间[1100]最快的方法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！