Raj*_*eev 28 c sorting algorithm
int a= {1,3,6,7,1,2};
哪种是对以下数组进行排序的最佳排序技术,如果存在重复,则如何处理它们.也是最好的分拣技术....
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;
}
}
}
}
Ale*_*ece 44
在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 )
请参阅:http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/
要回答问题的第二部分:最佳(基于比较)排序算法是使用O(n log(n))比较运行的算法.有几个具有此属性(包括快速排序,合并排序,堆排序等),但使用哪个取决于您的用例.
作为旁注,如果您对数据有所了解,有时可以比O(n log(n))更好 - 请参阅有关Radix Sort的维基百科文章
kri*_*iss 12
在您的特定情况下,最快的排序可能是本答案中描述的排序.它针对6个整数的数组进行了精确优化,并使用了排序网络.它比库qsort快20倍(在x86上测量).排序网络对于某种固定长度的阵列是最佳的.由于它们是固定的指令序列,因此甚至可以通过硬件轻松实现.
一般来说,有一些针对某些特殊情况优化的排序算法.堆排序或快速排序等通用算法已针对项目数组的就地排序进行了优化.它们产生O(n.log(n))的复杂度,n是要排序的项目数.
库函数qsort()在复杂性方面编码非常好并且有效,但是使用了对用户提供的某些比较函数的调用,并且该调用具有相当高的成本.
对于排序非常大量的数据算法也需要处理数据与磁盘的交换,这是在数据库中实现的那种排序,如果你有这样的需求,最好的办法是将数据放入某个数据库并使用内置排序.
这取决于各种各样的事情.但是一般来说,使用Divide-and-Conquer/dichotomic方法的算法在排序问题时表现良好,因为它们呈现出有趣的平均情况复杂性.
要了解哪种算法效果最好,您需要具备算法复杂度和大O符号的基本知识,因此您可以了解它们在平均情况,最佳情况和最差情况方面的评分.如果需要,您还必须注意排序算法的稳定性.
例如,通常一种有效的算法是快速排序.但是,如果你给quicksort一个完美的倒置列表,那么它的表现会很差(在这种情况下,简单的选择排序会表现得更好!).如果对列表进行预分析,Shell-sort通常也是quicksort的一个很好的补充.
对于使用分而治之的方法进行"高级搜索",请查看以下内容:
对于不太复杂的算法,这些更直接的算法:
上面是开始时常见的嫌疑人,但也有无数其他人.
正如R.在评论中和kriss在他的回答中指出的那样,你可能想看看HeapSort,它提供了理论上比快速排序更好的排序复杂性(但在实际环境中通常不会更好).还有变体和混合算法(例如TimSort).
小智 5
我想进行一些更改：在 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 )