插入排序vs气泡排序vs quicksort算法 [英] insertion sort vs bubble sort vs quicksort algorithm
问题描述
我正在课堂上进行一项研究 我测试了冒泡排序和插入排序以及快速排序，我对随机数进行了测试. 结果表明，插入排序比气泡排序更快，而快速排序最慢.
I am working on a research in the class I tested bubble sort and insertion sort and quick sort , i did the test on random numbers. The results shows that insertion sort is more quicker than bubble sort and quick sort is the most slower one.
所以我在时间方面排在下面
So I have the below ranking in terms of time
- 插入排序(最快)
- 冒泡排序(第二得分)
- 快速排序(最慢)
考虑到插入和冒泡排序的复杂度为O(n2)，而 快速排序O(n log n)和O(n log n)应该更快！
Taking into account that insertion and bubble sort have a complexity of O(n2) while quick sort O(n log n) and O (n log n) should be faster !!!
有人可以和我分享一些解释吗?
Could anybody share with me explanations?
谢谢
(NSMutableArray *)quickSort:(NSMutableArray *)a
{
// Log the contents of the incoming array
NSLog(@"%@", a);
// Create two temporary storage lists
NSMutableArray *listOne = [[[NSMutableArray alloc]
initWithCapacity:[a count]] autorelease];
NSMutableArray *listTwo = [[[NSMutableArray alloc]
initWithCapacity:[a count]] autorelease];
int pivot = 4;
// Divide the incoming array at the pivot
for (int i = 0; i < [a count]; i++)
{
if ([[a objectAtIndex:i] intValue] < pivot)
{
[listOne addObject:[a objectAtIndex:i]];
}
else if ([[a objectAtIndex:i] intValue] > pivot)
{
[listTwo addObject:[a objectAtIndex:i]];
}
}
// Sort each of the lesser and greater lists using a bubble sort
listOne = [self bubbleSort:listOne];
listTwo = [self bubbleSort:listTwo];
// Merge pivot onto lesser list
listOne addObject:[[NSNumber alloc] initWithInt:pivot]];
// Merge greater list onto lesser list
for (int i = 0; i < [listTwo count]; i++)
{
[listOne addObject:[listTwo objectAtIndex:i]];
}
// Log the contents of the outgoing array
NSLog(@"%@", listOne);
// Return array
return listOne;
}
推荐答案
O(nlogn)比O(n^2)更快，但让我们回想一下O标记的含义.
O(nlogn) is "faster" then O(n^2), but let's recall what the big O notation mean.
这意味着，如果算法A对于某些常量N_1和c1，对于每个n>N，其复杂度为O(nlogn)，则算法更快"，则c1*n*log(n).如果算法B具有O(n^2)，则存在一些常量N_2，c2，以使该算法比"c11>的c2 * n^2 * log(n)更快".
It means that if algorithm A has complexity of O(nlogn), for some constants N_1, and c1, for each n>N - the algorithm is "faster" then c1*n*log(n). If algorithm B has O(n^2), there are some constants N_2,c2 such that the algorithm is "faster" then c2 * n^2 * log(n) for n > N_2.
但是-在此N之前会发生什么?这个常数C是什么?我们不知道. 算法B仍可能比算法A更快(对于较小的输入)，但是对于较大的输入-实际上，A会更快(渐近边界更好).
However - what happens before this N? and what is this constant C? We do not know. Algorithm B could still be "faster" then algorithm A for small inputs, but for large inputs - indeed, A will be faster (the asymptotic bound is better).
例如，让我们假设算法A在T_1(n) = 10* nlog(n) ops中运行，而算法B在T_2(n) = n^2中运行.对于n=3-我们得到T_1(3) = 10*3*2 = 60(为log(n)使用工具ceil)，而T_2(3) = 9-算法为B，尽管对于该输入，O(n^2)比A更快.
For example, let's take the case where algorithm A runs in T_1(n) = 10* nlog(n) ops, while algorithm B runs in T_2(n) = n^2. for n=3 - we get that T_1(3) = 10*3*2 = 60 (we tool the ceil for log(n)), and T_2(3) = 9 - thus algorithm B, though O(n^2) is faster then A for this input.
关于快速排序和插入排序:
快速排序通常非常快，在极少数情况下会衰减为二次时间(如果我们选择随机元素作为枢轴，则发生这种情况的可能性很小).
Regarding quick sort and insertion sort:
Quick sort is usually extremely fast, and decays into quadric time in very rare cases (the probability of this happening is slim if we chose a random element as a pivot).
但是，快速排序中大O表示法后面的常数要大于插入排序.因此-可能的优化方案是:使用快速排序直到达到某个阈值(例如30个元素)，然后使用插入排序而不是快速排序对该子数组进行排序. 这篇文章对此进行了讨论优化.
However, the constant behind the big O notation in quicksort is greater then insertion sort. Thus - a possible optimization is: use quicksort until you get to a certain threshold (say 30 elements), and then sort this subarray with insertion sort rather then quicksort. This post discusses this optimization.
对于随机数组，气泡排序(凭经验)是可怕的，但如果数组几乎已排序并且不适当的"元素在其开头，则可能会很好.
Bubble sort is (empirically) terrible for random arrays, but could be good if the array is almost sorted and the "out of place" elements are in its beginning.
这篇关于插入排序vs气泡排序vs quicksort算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
