小编Cah*_*gor的帖子

来自cplusplus.com的 std::sort复杂性定义如下:

复杂

平均大约N*logN比较(其中N是最后一个).在最坏的情况下,最多N2,取决于库实现使用的特定排序算法.

我的应用程序运行时间有一些限制.所以我需要知道我是否应该实现自己的排序算法,否则只会浪费时间.它们是用gcc编译的,所以我需要知道gcc使用哪种排序算法.

编写一个程序,在Mac上用C++演示不同的排序算法.我找到了两个quicksort实现,qsort和qsort_b.

第一个当然是老式的,随处可见的qsort.但是有qsort_b,它采用块而不是函数.这是我的代码:

#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <cstdio>
#include <ctime>

#define DATA 1000000

using namespace std;

int compare(const void* a, const void* b)
{
    return *(int*)a - *(int*)b;
}

int main(int argc, char *argv[])
{
    int* array = new int[DATA];

    srand(time(0));

    for ( int i = 0 ; i < DATA ; ++ i )
    {
        array[i] = rand() % 2147483647;
    }

    clock_t begin = clock();

    qsort(array, DATA, sizeof(array[0]), compare);
    //qsort_b(array, DATA, sizeof(array[0]), ^(const void* a, const void* …