1

我正在研究我测试冒泡排序和插入排序和快速排序的课程,我对随机数进行了测试。结果表明,插入排序比冒泡排序快,而快速排序是最慢的排序。

所以我在时间方面有以下排名

  1. 插入排序(最快)
  2. 冒泡排序(第二分)
  3. 快速排序(最慢)

考虑到插入和冒泡排序的复杂度为 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;
}
4

3 回答 3

3

好吧,快速排序严重依赖输入。在进行快速排序之前,您需要 SHUFFLE 输入。如果您的输入已排序,则快速排序的复杂度可能为 O(n2)

对于小数组,插入排序也可以更快

于 2012-10-16T11:08:58.963 回答
2

这取决于数组大小。在小型数组上,简单的算法(例如插入排序)会做得很好,不需要更好的算法。

然而,当 n 很大时(比如 n=10000000),快速排序通常会比插入(或冒泡)排序好得多。

于 2012-10-16T11:12:09.947 回答
2

O(nlogn)那么是“更快” O(n^2),但让我们回想一下大 O 符号的含义。

这意味着如果算法 A 的复杂度为O(nlogn),对于某些常数N_1,并且c1,对于每个n>N- 算法“更快”那么c1*n*log(n)。如果算法 B 有O(n^2),则有一些常数N_2c2这样算法就“更快”c2 * n^2 * log(n)n > N_2

但是 - 在此之前会发生什么N?这个常数是C什么?我们不知道。对于小输入,算法B仍然可能比算法“更快”A,但对于大输入 - 实际上A会更快(渐近界更好)。

例如,让我们以算法AT_1(n) = 10* nlog(n)ops 中运行,而算法BT_2(n) = n^2. for n=3- 我们得到了T_1(3) = 10*3*2 = 60(我们为 ceil 提供工具log(n)),并且T_2(3) = 9- 因此 algorithm B,虽然O(n^2)A这个输入更快。

关于快速排序和插入排序:
快速排序通常非常快,并且在极少数情况下会衰减到二次时间(如果我们选择随机元素作为枢轴,这种情况发生的可能性很小)。

但是,快速排序中大 O 符号后面的常数大于插入排序。因此 -一个可能的优化是:使用快速排序直到达到某个阈值(比如 30 个元素),然后使用插入排序而不是快速排序对这个子数组进行排序。这篇文章讨论了这种优化。

冒泡排序(根据经验)对于随机数组很糟糕,但如果数组几乎已排序并且“不合适”的元素在其开头,则可能会很好。

于 2012-10-16T11:29:46.200 回答