插入排序VS冒泡排序VS快速排序算法(insertion sort vs bubble sort v

我工作在I类测试冒泡排序和插入排序和快速排序的一个研究，我做了随机数的测试。结果表明：插入排序比冒泡排序和快速排序更多更快是最慢的一个。

所以，我在时间上的排名如下

插入排序（最快）
冒泡排序（第二得分）
快速排序（最慢）

考虑到插入和冒泡排序有一个O（N2），同时快速排序为O（n log n）的和为O（n log n）的复杂性应该会更快！

可能有人跟我解释分享？

谢谢

(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;
}

Answer 1:

O(nlogn)是“快”，然后O(n^2)但是让我们来回顾一下大O符号的意思。

这意味着，如果算法A具有的复杂性O(nlogn)对于一些常量N_1 ，和c1 ，对于每个n>N -算法是“更快”然后c1*n*log(n) 如果算法B具有O(n^2)也有一些常量N_2 ， c2 ，使得该算法是“更快”然后c2 * n^2 * log(n)为n > N_2 。

但是-这是什么之前发生N ？什么是这个常数C ？我们不知道。 算法B可能仍然是“快”，那么算法A对小投入 ，但对于大的投入-事实上， A会更快（渐近界是更好）。

例如，让其中算法的采取的情况下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)和T_2(3) = 9 -因而算法B ，虽然O(n^2)更快然后A此输入。