如何提高 C 中大数据排序的执行速度

Question

我成功完成了插入排序例程，如图所示：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct{
    int n;
    char l;
    char z;
} dat;

void sortx(dat* y){
    char tmp[sizeof(dat)+1];
    dat *sp=y;
    while(y->l){
        dat *ip=y;
        while(ip>sp && ip->n < (ip-1)->n){
            memcpy(tmp,ip,sizeof(dat));
            memcpy(ip,ip-1,sizeof(dat));
            memcpy(ip-1,tmp,sizeof(dat));
            ip--;
        }
        y++;
    }
}

void printa(dat* y){
    while(y->l){printf("%c %d,",y->l,y->n);y++;}
    printf("\n");
}

int main(int argc,char* argv[]){
    const long sz=10000;
    dat* new=calloc(sz+2,sizeof(dat));
    dat* randx=new;
    //fill struct array with random values
    int i;
    for (i = 0 ; i < sz ; i++) {
        randx->l = (unsigned char)(65+(rand() % 25));
        randx->n = (rand() % 1000);randx++;
    }
    //sort - takes forever
    sortx(new);
    printa(new);
    free(new);
    return 0;
}

我的排序程序部分源自：http://www.programmingsimplified.com/c/source-code/c-program-insertion-sort 但是因为我正在根据结构中的数值对数组进行排序，memcpy 到目前为止对我有用。

我用来执行此代码的计算机有一个 Pentium 1.6Ghz 处理器，当我将 main 函数中的 sz 至少更改为 20000 时，我注意到我必须等待两秒钟才能在屏幕上看到结果.

我之所以测试大数字是因为我想用C处理服务器日志，并且会按时间戳对信息进行排序，有时日志会变得非常大，我不想放太多对 CPU 施加压力，因为它是运行其他进程，例如 apache。

我是否可以改进此代码，这样我就不必等待两秒钟来查看 20000 个结构排序？

Answer 1

使用快速排序、堆排序或自底向上归并排序。 Wiki 在他们的文章中有这些示例，并且通常在每篇文章的讨论页上都有更完整的示例。

Answer 2

插入排序的时间复杂度为 O(n^2)，还有其他算法的时间复杂度为 O(nlogn)，例如归并排序、快速排序和堆排序。看起来您正在按整数排序，因此您可能还想考虑使用 LSD 基数排序，这是 O(n) 时间复杂度。

Answer 3

已经有一个函数可以执行此操作，并且它内置于 C 标准库中：qsort。你只需要提供合适的比较功能即可。

这个函数必须 return -1 如果作为左参数的项目应该按照所需的顺序放在前面，1 如果应该放在后面，或 0 如果项目被认为相等 qsort.

int dat_sorter(const void* l, const void* r)
{
    const dat* left = (const dat*)l;
    const dat* right = (const dat*)r;
    if(left->n > right->n)
        return 1;
    else if(left->n < right->n)
        return -1;
    else
        return 0;
}

void sortx(dat* y)
{
    /* find the length */
    dat* it = y;
    size_t count = 0;
    while(it->l)
    {
        count++;
        it++;
    }
    /* do the sorting */
    qsort(y, count, sizeof(dat), dat_sorter);
}

如果你想加快速度，你可以让sortx函数获取数组的长度，这样函数就不需要自己计算了。

如何提高 C 中大数据排序的执行速度

How to improve execution speed on large data sort in C

c

performance

sorting

insertion-sort