快速、冒泡、选择、归并、基数、堆排序N个整数及性能比较

各个排序具体的思路在网上比比皆是，在此之作简要概括。

快速排序：

1、在待排序的对象中选择一个标志位（通常选择第一个元素），根据其他元素与其相比较的结果，将其他元素分为两集合，大于标准位的一个集合，小于标志位的一个集合，

2、再分别对两个集合递归进行步骤一，直到每个集合只有一个元素为止。

冒泡排序：

1、依次比较每个元素与其后面的元素，如果后面的元素小，则交换。这样将所以的元素比较完以便后，最后的元素一定是最大的。

2、在余下的元素，重复进行步骤1，直到余下的元素个数为1，至此所有元素已有序，此方法需要两层嵌套循环，效率较低。

选择排序：

1、依次比较每个元素与其后面的元素，记录最大元素出现的位置，当比较完一遍后，将最大位置的元素，与最后一个元素交换，这样能保证最后一个元素最大。

2、重复对余下元素进行相同操作，直到余下元素个数为1，至此所以元素已有序。此方法同样需要两层嵌套，效率较低。

归并排序：

1、先让队列局部有序，再逐渐扩大局部的范围。例如先让每两个元素之间有序列，再让扩大有序的范围，让每四个元素间有序，依次类推。最后实现整个队列有序。

基数排序：

1、先统计所有元素一共占有几位，比如元素最大位数到百位。

2、依次访问元素，将元素按个位分类，0-9不同类，此处可用链表实现

3、在步骤2的基础上，从0到9依次将元素按十位分类，此处若用带指针的节点，比较方便。

4、依次执行N次，比较到元素的最高位，此时有10个链表0-9，从链表头到链表尾，依次有序，顺序赋值给相应元素即可。

堆排序：

1、初始化，将所以元素构造成一个大值堆，此时数组的第0个元素即为最大值。

2、将第0个元素与最后一个元素交换，此时最后一个元素为最大，再将最后一个元素的位置剔除出堆。此事由于修改了第0个元素，破坏了堆的特性，再对堆进行调整。

3、重复步骤2，直到堆内剩余1个元素，排序结束，元素有序。

各排序算法时间复杂度及排序排序N个数所有时间：

注：以上测试结果均未进行多次统计求平均值的过程，只是为了比较当排序数量按指数增长时，各个排序算法的性能的横向和纵向比较关系。

由结果分析可得，随着待排序元素个数随着呈指数增长，冒泡排序和选择排序的时间呈平方倍数增长。而其他排序增长相对平缓。所以测试结果基本与时间复杂度相符。

空间复杂度：

下面贴出具体测试代码：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>

#define NUM 1000000

int number[NUM];

// 初始化NUM个数 
void initNumber()
{
    int i = 0;
    for (i = 0; i < NUM;++i)
        number[i] = i;
}

// 打乱NUM个数
void upsetNumber()
{
    int i = 0, r1, r2, temp;
    srand((int)time(0));
    for (i = 0;i < NUM;++i)
    {
        r1 = rand() % NUM;
        r2 = rand() % NUM;
        temp = number[r1];
        number[r1] = number[r2];
        number[r2] = temp;
    }
}

// 输入当前数组中元素
void outputNumber()
{
    int i = 0;
    for (i = 0; i< NUM;++i)
        printf(((i + 1)%20 == 0)?"%5d\n":"%5d", number[i]);
    printf("=======================================>\n");
}

// 快速排序:
// 参数 front，需要比较第一个元素的位置，behind需要比较最后一个元素位置
void quickSort(int front, int behind)
{
    int f = front + 1, b = behind, temp;
    if (front >= behind)
        return;
    while (f != b)
    {
        if (number[f] > number[front])
        {
            temp = number[f];
            number[f] = number[b];
            number[b] = temp;
            --b;
        }
        else
        {
            ++f;
        }
    }
    // 将标志位放到数组中间
    if (number[f] > number[front])
        --f;
    temp = number[front];
    number[front] = number[f];
    number[f] = temp;
    // 分别对不同分组递归进行快速排序
    quickSort(front, f - 1);
    quickSort(f + 1, behind);
}

// 冒泡排序
void bubbleSort()
{
    int i = 0,j = 0, temp;
    for (i = 0;i < NUM;++i)
        for (j = 0;j < NUM - 1 - i;++j)
        {
            if (number[j] > number[j + 1])
            {
                temp = number[j];
                number[j] = number[j + 1];
                number[j + 1] = temp;
            }
        }
}

// 选择排序
void selectSort()
{
    int min, i, temp, j;
    for (i = 0;i < NUM;++i)
    {
        for (min = i, j = i + 1;j < NUM;++j)
        {
            if (number[j] < number[min])
            {
                min = j;
            }
        }
        temp = number[min];
        number[min] = number[i];
        number[i] =temp;
    }
}

// 归并排序子函数
// front 已有序的第一个序列的起点，mid 已有序第二个序列的起点，behind 已有序第二个序列的终点
void mergechild(int front, int mid, int behind)
{
    int n = behind - front;
    int temp[n], a, b ,c;

    for (a = front, b = mid, c = 0; c < n;++c)
    {
        if (a == mid )
        {
            temp[c] = number[b++];
            continue;
        }
        if (b == behind)
        {
            temp[c] = number[a++];
            continue;
        }
        temp[c] = (number[a] < number[b])?number[a++]:number[b++];
    }
    for (c = 0; c < n;++c)
        number[front + c] = temp[c];
}

// 归并排序
void merge()
{
    int i = 0, j = 0;
    // 呈2倍扩大，有序数组的大小
    for (i = 1; i < NUM; i *= 2)
    {
        for (j = 0;j < NUM;j += 2*i)
        {
            mergechild(j, (j + i < NUM)?(j + i):NUM, (j + 2*i < NUM)?(j+2*i):NUM);
        }
    }
}

// 基数排序
void LSD()
{
    struct node
    {
        int value;
        struct node* next;
    };
    // 由于需要用到计数参数较多，具体参数在每个程序块内作用可能不同，未一一注释
    int num = NUM, i = 1, j, k, m = 10;
    while (num /= 10)
        i *= 10;
    struct node* dig[10], *tail[10], *temp[10], *p;

    for (j = 0;j < 10;++j)
    {
        dig[j] = NULL;
        temp[j] = NULL;
        tail[j] = NULL;
    }
    // 将元素放在以个位分类的10个链表中
    for (j = 0;j < NUM;++j)
    {
        p = (struct node*)malloc(sizeof(struct node));
        p->value = number[j];
        p->next = NULL;
        k = number[j] - number[j]/10*10;
        if (dig[k] == NULL)
        {
            dig[k] = tail[k] = p;
        }
        else
        {
            tail[k]->next = p;
            tail[k] = p;
        }
    }    
    // 依次再以十位， 百位分类
    while (i >= m)
    {
        for (k = 0;k < 10;++k)
        {
            int l;
            while ((p = dig[k]))
            {
                dig[k] = dig[k]->next;
                l = p->value%m/(m/10);
                p->next = NULL;
                if (temp[l] == NULL)
                {
                    temp[l] = tail[l] = p;
                }
                else
                {
                    tail[l]->next = p;
                    tail[l] = p;
                }
            }
        }
        for (k = 0;k < 10;++k)
        {
            dig[k] = temp[k];
            temp[k] = NULL;
        }
        m *= 10;
    }
    // 将已排序好的元素， 复制到数组中
    for (k = 0, i = 0;k < 10;++k)
    {
        while ((p = dig[k]))
        {
            dig[k] = dig[k]->next;
            number[i++] = p->value;
            free(p);
        }
    }
}

// 调整从位置p，到位置i的堆的结构
void heap_sort(int p, int i)
{
    int k, j;
    while(1)
    {
        if ((2*p+1) > i)
            break;
        else
        {
            if ((2*p+1) == i)
                k = 2*p+1;
            else
                k = (number[2*p + 1]>number[2*p + 2])?(2*p + 1):(2*p + 2);
            if (number[k] > number[p])
            {
                j = number[k];
                number[k] = number[p];
                number[p] = j;
                p = k;
            }
            else
                break;
        }
    }   
}
// 堆排序
void heap()
{
    int i, j;
    // 分别替换第一个元素到结尾，再重新调整堆的结构
    for(i = NUM - 1;i >= 0;i--)
    {
        j = number[0];
        number[0] = number[i];
        number[i] = j;
        heap_sort(0, i - 1);
    }                      
}

// 堆的初始化，建立一个大值堆
void heap_init()
{
    int i;
    
    for (i = NUM/2;i >= 0;i--)
        // 从堆的最后一个含有子节点的元素开始调整堆，依次向上调整
        heap_sort(i, NUM - 1);
}

int main(int argc, char** argv)
{
    struct timeval beg, end;
    initNumber();
    outputNumber();
    upsetNumber();
    outputNumber();
    gettimeofday(&beg, NULL);
    //heap_init();
    //heap();    
    //quickSort(0, NUM - 1);
    bubbleSort();
    //selectSort();
    //merge();
    //LSD();
    gettimeofday(&end, NULL);
    outputNumber();
    printf("Time: %ld\n", (end.tv_sec - beg.tv_sec)*1000000 + (end.tv_usec - beg.tv_usec));
    return 0;
}

快速、冒泡、选择、归并、基数、堆排序N个整数及性能比较

原文：http://my.oschina.net/u/2313065/blog/522554