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_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. 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 回答