选择排序算法的标准是什么？ [英] What are the criteria for choosing a sorting algorithm?
问题描述
我正在阅读排序方法，包括气泡排序，选择排序，合并排序，堆排序，桶排序等。它们还包含时间复杂性，这有助于我们知道哪个排序是有效的。所以我有一个基本的问题。如果我们包含数据，我们将如何选择排序。时间复杂性是帮助我们决定排序方法的参数之一。但是，我们还有另一个参数来选择排序方法吗？
I was reading sorting method which include bubble sort, selection sort, merge sort, heap sort, bucket sort etc.. They also contain time complexity which help us to know which sorting is efficient. So I had a basic question. If we contain data than how will we be choose sorting. Time complexity is one of parameter which help us to decide sorting method. But do we have another parameter to choose sorting method?.
只是试图找出更好的理解排序。
Just trying to figure out sorting for better understanding.
有关堆排序的一些查询：
Having some query about heap sort:
-
我们在哪里使用堆排序？
Where do we use heap sort?
堆排序的更大优点（除了时间复杂度O（n log n））？
What is bigger advantage of heap sort (except time complexity O(n log n))?
堆排序？
堆的构建时间是什么？ （我听说O（n）但我不确定。）
What is build time for heap? (I heard O(n) but I'm not sure.)
任何情况下，我们必须使用堆排序或堆排序是更好的选择优先级队列）？
Any scenario where we have to use heap sort or heap sort is better option (except priority queue)?
在对数据应用堆排序之前，我们会查看什么参数？
Before applying the heap sort on data, what are the parameter will we look into data?
推荐答案
排序算法的两个主要理论特征是时间复杂性和空间复杂性。
The two main theoretical features of sorting algorithms are time complexity and space complexity.
一般来说，时间复杂度可让我们了解效能的算法随着数据集的大小的增加而改变。需要考虑的因素：
In general, time complexity lets us know how the performance of the algorithm changes as the size of the data set increases. Things to consider:
- 您希望排序的数据量是多少？
- 您的数据如何排序？它会被部分排序吗？随机排序？这可能影响排序算法的时间复杂性。大多数算法会有最坏的和最好的情况 - 你想确保你不使用算法对最坏情况的数据集。
- 时间复杂性不一样。请记住，时间复杂度仅描述算法的性能随着数据集大小的增加而变化的方式。一个总是对所有输入执行一次遍历的算法将是O（n） - 它的性能与输入的大小线性相关。但是，总是对数据集执行两次遍历的算法也是O（n） - 即使常数（和实际运行时间）不同，相关性仍然是线性的。
- How much data are you expecting to sort? This will help you know whether you need to look for an algorithm with a very low time complexity.
- How sorted will your data be already? Will it be partly sorted? Randomly sorted? This can affect the time complexity of the sorting algorithm. Most algorithms will have worst and best cases - you want to make sure you're not using an algorithm on a worst-case data set.
- Time complexity is not the same as running time. Remember that time complexity only describes how the performance of an algorithm varies as the size of the data set increases. An algorithm that always does one pass over all the input would be O(n) - it's performance is linearly correlated with the size of the input. But, an algorithm that always does two passes over the data set is also O(n) - the correlation is still linear, even if the constant (and actual running time) is different.
同样，空间复杂性描述了算法需要运行多少空间。例如，简单排序（如插入排序）需要额外固定的空间量来存储当前元素的值插入。这是O（1）的辅助空间复杂度 - 它不随输入的大小而改变。但是，合并排序会在内存中运行时创建额外的数组，辅助空间复杂度为O（n）。这意味着它需要的额外空间量与输入的大小线性相关。
Similarly, space complexity describes how much space an algorithm needs to run. For example, a simple sort such as insertion sort needs an additional fixed amount of space to store the value of the element currently being inserted. This is an auxiliary space complexity of O(1) - it doesn't change with the size of the input. However, merge sort creates extra arrays in memory while it runs, with an auxiliary space complexity of O(n). This means the amount of extra space it requires is linearly correlated with the size of the input.
当然，算法设计通常是时间和空间之间的折衷 - 具有低空间复杂度的算法可能需要更多的时间，而具有低时间复杂度的算法可能需要更多的空间。
Of course, algorithm design is often a trade-off between time and space - algorithms with a low space complexity may require more time, and algoithms with a low time complexity may require more space.
有关更多信息，您可能会发现本教程非常实用。
For more information, you may find this tutorial useful.
要回答您更新的问题，您可以在堆排序中找到维基百科页面。
To answer your updated question, you may find the wikipedia page on Heap Sort useful.
这篇关于选择排序算法的标准是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
