blocks|key|252343|text|type|unstyled|depth|inlineStyleRanges|entityRanges|data|252344|数组元素是从1到10的数字。|blockquote|252345|252346|252347|有了这个限制，counting+sort将比任何通用排序算法效率高得多-它是O(n)|offset|length|252348|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Counting_sort^0|0|0|0|0|7|D|0|0^^$0|@$1|2|3|-4|4|5|6|R|7|@]|8|@]|9|$]]|$1|A|3|B|4|C|6|S|7|@]|8|@]|9|$]]|$1|D|3|-4|4|5|6|T|7|@]|8|@]|9|$]]|$1|E|3|-4|4|5|6|U|7|@]|8|@]|9|$]]|$1|F|3|G|4|5|6|V|7|@]|8|@$H|W|I|X|1|Y]]|9|$]]|$1|J|3|-4|4|5|6|Z|7|@]|8|@]|9|$]]]|K|$L|$4|M|N|O|9|$P|Q]]]]

<blockquote>
 the array elements are number from 1 - 10.
</blockquote>

With this restriction, <a href="http://en.wikipedia.org/wiki/Counting_sort" rel="noreferrer">counting sort</a> will be far more efficient than any general purpose sorting algorithm - it's O(n)

blocks|key|255702|text|这是我的计数排序示例|type|unstyled|depth|inlineStyleRanges|entityRanges|data|255703|static+int[]+countingSort(int[]+numbers)+{
++++int+max+=+numbers[0];
++++for+(int+i+=+1;+i+<+numbers.length;+i%2B%2B)+{
++++++++if+(numbers[i]+>+max)
++++++++++++max+=+numbers[i];
++++}

++++int[]+sortedNumbers+=+new+int[max%2B1];

++++for+(int+i+=+0;+i+<+numbers.length;+i%2B%2B)+{
++++++++sortedNumbers[numbers[i]]%2B%2B;
++++}

++++int+insertPosition+=+0;

++++for+(int+i+=+0;+i+<=+max;+i%2B%2B)+{
++++++++++++for+(int+j+=+0;+j+<+sortedNumbers[i];+j%2B%2B)+{
++++++++++++++++++++numbers[insertPosition]+=+i;
++++++++++++++++++++insertPosition%2B%2B;
++++++++++++}
++++}
++++return+numbers;
}|code-block|syntax|javascript|255704|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

This is my counting sort example

<pre><code>static int[] countingSort(int[] numbers) {
 int max = numbers[0];
 for (int i = 1; i &lt; numbers.length; i++) {
 if (numbers[i] &gt; max)
 max = numbers[i];
 }

 int[] sortedNumbers = new int[max+1];

 for (int i = 0; i &lt; numbers.length; i++) {
 sortedNumbers[numbers[i]]++;
 }

 int insertPosition = 0;

 for (int i = 0; i &lt;= max; i++) {
 for (int j = 0; j &lt; sortedNumbers[i]; j++) {
 numbers[insertPosition] = i;
 insertPosition++;
 }
 }
 return numbers;
}
</code></pre>

blocks|key|252363|text|如果只有10个元素，你甚至不值得去担心它。如果有一百万，它可能会开始变得重要。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|252364|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

If there are only 10 elements it isn't worth your while to even worry about it. If there are a million it might start to become significant.

blocks|key|3149094|text|编辑:考虑到元素的范围仅为1-10，计数排序可能是最优的。应用于此问题的计数排序将在O(n)时间内运行。合并排序(我在下面推荐的)运行时间不会超过O(nlogn)。并行化计数排序可能很有趣。只需为每个处理器分配一个具有n/p个元素子数组。每个处理器都有自己的计数数组，大小为9。这一步应该需要O(n/p)时间。然后将所有计数数组合并到一个数组中，这应该需要O(p)时间。我还没有完全考虑过计数排序中元素按顺序排列的最后一步，但似乎只要count数组的元素是原子的，您就可以将原始数组的n/p部分分配给各个处理器，并实现一些并行化。然而，在count数组的各个元素上会有争用，这可能会大大降低并发性。如果元素分布得相当均匀，您可以将计数数组的子部分分配给p个处理器，并返回O(n/p)运行时，但您将被限制为10个处理器。如果元素不是均匀分布的，那么一个或多个处理器可能会完成更大比例的工作。这是一个很好的问题；你能在O(n/p)时间内进行计数排序吗？|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3149095|快速排序是一个很好的就地排序算法，运行速度快，节省内存。但是，给定元素的范围仅为1-10，如果您正在对大量元素进行排序，则无论是最初还是在排序过程中的中间时间，最终都会得到相同数量的大量运行。有序数组或子数组确实会降低快速排序的性能。|3149096|如果你不关心内存，一个简单的Mergesort就足够了。Mergesort拥有最快的标准排序算法。|3149097|Java7中默认的Collections.sort()实现是从“TimSort”改编的合并排序算法。Java7中默认的Arrays.sort()实现是双轴快速排序。|3149098|如果您希望并行，并行快速排序可以在处理器数量较少的大型数组上获得良好的结果，但具有与顺序快速排序相同的限制。PSRS可以帮助扩展到更多的处理器。|3149099|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|M|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|N|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|O|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|P|8|@]|9|@]|A|$]]|$1|J|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|K|$]]

Edit: A counting sort is probably optimal given the constraint that the elements only range from 1-10. A counting sort applied to this problem will run in O(n) time. A merge sort (as I recommended below) will run in no better than O(nlogn) time. Parallelizing a counting sort could be interesting. Simply assign a subarray with n/p elements to each processor. Each processor would have its own count array of size 9. This step should take O(n/p) time. Then consolidate all the count arrays into a single array, which should take O(p) time. I haven't fully thought through the last step in the counting sort where the elements are placed in order, but it seems as long as the elements of the count array are atomic, you could assign n/p sections of the original array to individual processors and achieve some parallelization. There would be contention at individual elements of the count array, however, potentially substantially reducing concurrency. You might be able to assign subsections of the count array to p processors and you are back to O(n/p) runtime, if the elements are distributed fairly evenly, but you would be limited to 10 processors. If the elements are not distributed evenly, one or more processors could be doing a larger proportion of the work. This is great question; can you do a counting sort in O(n/p) time?

Quicksort is a great in-place sort algorithm that runs fast and conserves memory. However, given the elements only range from 1-10, if you are sorting large numbers of elements, you will end up with large runs of the same number, either initially, or at interim times during the sort. In-order arrays or sub-arrays can really bog down a Quicksort's performance.

If you don't care about memory, a simple Mergesort would suffice. Mergesort is up there with the fastest standard sort algorithms. 

The default Collections.sort() implementation in Java 7 is a Mergesort algorithm adapted from 'TimSort.' The default Arrays.sort() implementation in Java 7 is a dual pivot Quicksort.

If you would like to go parallel, a Parallel Quicksort can achieve good results on large arrays with small numbers of processors, but with the same limitations as the sequential Quicksort. PSRS can help scale to larger numbers of processors.

blocks|key|3149151|text|您应该考虑在复杂性图表Complexity+Comparison+Chart中查看此内容。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|3149152|排序算法的比较基于时间和空间的最佳、平均、最坏情况complexity.Based在此图表上，您可以看到Counting+Sort方法在空间和时间复杂度上都是最好的。其他可比较的方法是基数排序。|3149153|“计数排序”的最差时间，空间复杂度:-+O(n%2Bk)，O(k)。|3149154|“基数排序”的最差时间和空间复杂度:-+O(nk)，O(n%2Bk)。|3149155|entityMap|0|LINK|mutability|MUTABLE|url|http://bigocheatsheet.com/|1|https://www.google.com.np/url?sa=t&rct=j&q=&esrc=s&source=web&cd=3&cad=rja&uact=8&ved=0ahUKEwiNo4bI7JHPAhXEjpQKHaPxCY4QFggkMAI&url=https%253A%252F%252Fen.wikipedia.org%252Fwiki%252FCounting_sort&usg=AFQjCNHg-0u-X-On-o4QJHEyiC0DMhLIqQ&sig2=YIQzlrWxEkYxPdURtqmtmw^0|B|R|0|0|1G|D|1|0|0|0^^$0|@$1|2|3|4|5|6|7|T|8|@]|9|@$A|U|B|V|1|W]]|C|$]]|$1|D|3|E|5|6|7|X|8|@]|9|@$A|Y|B|Z|1|10]]|C|$]]|$1|F|3|G|5|6|7|11|8|@]|9|@]|C|$]]|$1|H|3|I|5|6|7|12|8|@]|9|@]|C|$]]|$1|J|3|-4|5|6|7|13|8|@]|9|@]|C|$]]]|K|$L|$5|M|N|O|C|$P|Q]]|R|$5|M|N|O|C|$P|S]]]]

You should consider looking at this for complexity chart <a href="http://bigocheatsheet.com/" rel="nofollow noreferrer">Complexity Comparison Chart</a>.

The comparison of sorting algorithm is based on their Best, Average, Worst case scenario for time and space complexity.Based on this chart you can see <a href="https://www.google.com.np/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=3&amp;cad=rja&amp;uact=8&amp;ved=0ahUKEwiNo4bI7JHPAhXEjpQKHaPxCY4QFggkMAI&amp;url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FCounting_sort&amp;usg=AFQjCNHg-0u-X-On-o4QJHEyiC0DMhLIqQ&amp;sig2=YIQzlrWxEkYxPdURtqmtmw" rel="nofollow noreferrer">Counting Sort</a> approach is best on both space and time complexity. Other comparable method is Radix Sort.

Worst [Time,Space] complexity of "Counting Sort" :- [O(n+k),O(k)].

Worst [Time,Space] complexity of "Radix Sort" :- [O(nk),O(n+k)].

blocks|key|2934581|text|这是一个简单排序(插入排序)的例子|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2934582|private+static+void+insertionSort(int[]+a)+{

++++//+[230,+23,+45,+34,+98]
++++for+(int+j+=+2;+j+<+a.length;+j%2B%2B)+{

++++++++int+key+=+a[j];
++++++++int+i+=+j+-+1;

++++++++while+(i+>+0+&&+a[i]+>+key)+{
++++++++++++a[i+%2B+1]+=+a[i];
++++++++++++i--;
++++++++}
++++++++a[i+%2B+1]+=+key;
++++}

++++System.out.println("sorted+array:+"+%2B+Arrays.toString(a));
}|code-block|syntax|javascript|2934583|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

this is an example of simple sort (Insertion sort)

<pre><code>private static void insertionSort(int[] a) {

 // [230, 23, 45, 34, 98]
 for (int j = 2; j &lt; a.length; j++) {

 int key = a[j];
 int i = j - 1;

 while (i &gt; 0 &amp;&amp; a[i] &gt; key) {
 a[i + 1] = a[i];
 i--;
 }
 a[i + 1] = key;
 }

 System.out.println("sorted array: " + Arrays.toString(a));
}
</code></pre>

blocks|key|254563|text|在这种情况下，计数排序将是最好的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|254564|假设数据是0-k范围内的整数。创建一个大小为K的数组来跟踪出现了多少项(值为0的3项，值为1的4项，依此类推)。有了这个计数，你就可以知道项目的位置--所有的1必须在0之后，其中有3。因此，1从项目#4开始。因此，我们可以扫描项目并将它们插入到正确的位置。|254565|创建计数数组是O(N)将项插入到它们的适当位置是O(N)+I在这里被过度简化-有计数的总和，以及保持排序稳定的从大到小的排序。|254566|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

Counting sort will be best in this scenario. 

Assuming the data are integers, in a range of 0-k. Create an array of size K to keep track of how many items appear (3 items with value 0, 4 items with value 1, etc). Given this count, you can tell the position of an item — all the 1’s must come after the 0’s, of which there are 3. Therefore, the 1’s start at item #4. Thus, we can scan the items and insert them into their proper position.

Creating the count array is O(N)
Inserting items into their proper position is O(N)
I oversimplified here — there is a summation of the counts, and a greatest-to-least ordering which keeps the sort stable.

blocks|key|2934675|text|QuickSort是一种分而治之的算法。它选取一个元素作为枢轴，并围绕所选取的枢轴对给定的数组进行分区，然后重复该过程。有许多不同版本的quickSort以不同的方式选择pivot|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2934676|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot and then repeats the process. There are many different versions of quickSort that pick pivot in different ways

As per question title, if the array is of an odd length and the array elements are numbered 1 - 10. 

Example, 

<blockquote>
 3 6 8 1 3 7 7 9 4 1
</blockquote>

I was thinking of using heapsort? Since it is an array, merge sort and insertion sort requires shifting, and would not be so efficient.

What is the best sorting algorithm to sort an array of small integers?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

EdgeOne AI 安全实战专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

根据题目，如果数组的长度为奇数，并且数组元素的编号为1- 10。例如， 3 6 8 1 3 7 7 9 4 1我在考虑使用堆排序？由于它是一个数组，合并排序和插入排序需要移位，因此效率不高。

问对小整数数组进行排序的最佳排序算法是什么？
EN

回答 8

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问对小整数数组进行排序的最佳排序算法是什么？EN

回答 8

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问对小整数数组进行排序的最佳排序算法是什么？
EN