C语言 在 C 中对数组进行排序？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3893937/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Sorting an array in C?
提问by Rajeev
Which is the best sorting technique to sort the following array and if there are duplicates how to handle them:
哪个是对以下数组进行排序的最佳排序技术，如果有重复如何处理它们：
int a= {1,3,6,7,1,2};
Also which is the best sorting technique of all?
另外，哪个是最好的排序技术？
void BubbleSort(int a[], int array_size)
{
int i, j, temp;
for (i = 0; i < (array_size - 1); ++i)
{
for (j = 0; j < array_size - 1 - i; ++j )
{
if (a[j] > a[j+1])
{
temp = a[j+1];
a[j+1] = a[j];
a[j] = temp;
}
}
}
}
回答by Alex Reece
In C, you can use the built in qsortcommand:
在 C 中，您可以使用内置qsort命令：
int compare( const void* a, const void* b)
{
int int_a = * ( (int*) a );
int int_b = * ( (int*) b );
if ( int_a == int_b ) return 0;
else if ( int_a < int_b ) return -1;
else return 1;
}
qsort( a, 6, sizeof(int), compare )
see: http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/
见：http: //www.cplusplus.com/reference/clibrary/cstdlib/qsort/
To answer the second part of your question: an optimal (comparison based) sorting algorithm is one that runs with O(n log(n)) comparisons. There are several that have this property (including quick sort, merge sort, heap sort, etc.), but which one to use depends on your use case.
要回答问题的第二部分：最佳（基于比较的）排序算法是运行 O(n log(n)) 比较的算法。有几种具有此属性（包括快速排序、合并排序、堆排序等），但使用哪一种取决于您的用例。
As a side note, you can sometime do better than O(n log(n)) if you know something about your data - see the wikipedia article on Radix Sort
作为旁注，如果您对数据有所了解，有时可以比 O(n log(n)) 做得更好 - 请参阅关于基数排序的维基百科文章
回答by kriss
In your particular case the fastest sort is probably the one described in this answer. It is exactly optimized for an array of 6 ints and uses sorting networks. It is 20 times(measured on x86) faster than library qsort. Sorting networks are optimal for sort of fixed length arrays. As they are a fixed sequence of instructions they can even be implemented easily by hardware.
在您的特定情况下，最快的排序可能是此答案中描述的排序。它完全针对 6 个整数的数组进行了优化，并使用了排序网络。它比库 qsort 快20 倍（在 x86 上测量）。排序网络最适合对固定长度数组进行排序。由于它们是固定的指令序列，它们甚至可以通过硬件轻松实现。
Generally speaking there is many sorting algorithms optimized for some specialized case. The general purpose algorithms like heap sort or quick sort are optimized for in place sorting of an array of items. They yield a complexity of O(n.log(n)), n being the number of items to sort.
一般来说，有许多针对某些特殊情况优化的排序算法。诸如堆排序或快速排序之类的通用算法针对项目数组的就地排序进行了优化。它们产生 O(n.log(n)) 的复杂度，n 是要排序的项目数。
The library function qsort() is very well coded and efficient in terms of complexity, but uses a call to some comparizon function provided by user, and this call has a quite high cost.
库函数 qsort() 在复杂度方面编码得很好，效率也很高，但是使用了对用户提供的一些比较函数的调用，这种调用的成本相当高。
For sorting very large amount of datas algorithms have also to take care of swapping of data to and from disk, this is the kind of sorts implemented in databases and your best bet if you have such needs is to put datas in some database and use the built in sort.
为了对大量数据进行排序，算法还必须负责与磁盘交换数据，这是在数据库中实现的排序类型，如果您有此类需求，最好的选择是将数据放入某个数据库中并使用内置排序。
回答by haylem
Depends
要看
It depends on various things. But in general algorithms using a Divide-and-Conquer/ dichotomicapproach will perform well for sorting problems as they present interesting average-case complexities.
这取决于各种事情。但在一般情况下，使用分而治之/二分法的算法将在排序问题上表现良好，因为它们呈现出有趣的平均情况复杂性。
Basics
基本
To understand which algorithms work best, you will need basic knowledge of algorithms complexityand big-O notation, so you can understand how they rate in terms of average case, best case and worst case scenarios. If required, you'd also have to pay attention to the sorting algorithm's stability.
要了解哪种算法效果最好，您需要了解算法复杂性和大 O 符号的基本知识，以便您了解它们在平均情况、最佳情况和最坏情况方面的评分情况。如果需要，您还必须注意排序算法的稳定性。
For instance, usually an efficient algorithm is quicksort. However, if you give quicksort a perfectly inverted list, then it will perform poorly (a simple selection sort will perform better in that case!). Shell-sort would also usually be a good complement to quicksort if you perform a pre-analysis of your list.
例如，通常一种有效的算法是快速排序。然而，如果你给快速排序一个完全倒排的列表，那么它的表现会很差（在这种情况下，简单的选择排序会表现得更好！）。如果您对列表进行预分析，Shell-sort 通常也是快速排序的一个很好的补充。
Have a look at the following, for "advanced searches" using divide and conquer approaches:
查看以下内容，了解使用分而治之方法的“高级搜索”：
And these more straighforward algorithms for less complex ones:
这些更简单的算法用于不太复杂的算法：
Further
更远
The above are the usual suspects when getting started, but there are countless others.
以上是入门时常见的疑点，但还有无数其他的。
As pointed out by R. in the comments and by kriss in his answer, you may want to have a look at HeapSort, which provides a theoretically better sorting complexity than a quicksort (but will won't often fare better in practical settings). There are also variants and hybrid algorithms(e.g. TimSort).
正如 R. 在评论中和 kriss 在他的回答中指出的那样，您可能想看看HeapSort，它在理论上提供了比快速排序更好的排序复杂性（但在实际设置中通常不会表现得更好）。还有变体和混合算法（例如TimSort）。
回答by Thomas
I'd like to make some changes: In C, you can use the built in qsortcommand:
我想进行一些更改：在 C 中，您可以使用内置的qsort命令：
int compare( const void* a, const void* b)
{
int int_a = * ( (int*) a );
int int_b = * ( (int*) b );
// an easy expression for comparing
return (int_a > int_b) - (int_a < int_b);
}
qsort( a, 6, sizeof(int), compare )
回答by Pankti
The best sorting technique of all generally depends upon the size of an array. Merge sort can be the best of all as it manages better space and time complexity according to the Big-O algorithm (This suits better for a large array).
最好的排序技术通常取决于数组的大小。合并排序可能是最好的，因为它根据 Big-O 算法管理更好的空间和时间复杂度（这更适合大型数组）。
