经典排序算法归纳笔记(4)

    前面三篇博文我们分别回顾了冒泡排序、选择排序、插入排序、希尔排序、归并排序、堆排序和快速排序。关于排序算法有几种分类标准，稳定与非稳定、内部与外部。

   所谓稳定的排序算法，意思是如果待排序序列有相同元素，经过排序算法处理后他们的相对顺序和排序前在序列里的相对顺序一样，这样我们就称该排序算法是稳定；否则就是非稳定的。

   所谓内部排序算法，意思是待排序序列数据量规模较小，排序直接在内存里就可以完成的排序算法；而外部排序是针对数据量特别大，不能一次性将所有数据调入内存来，在排序过程中要不断地访问外部存储设备的排序算法。我们这里介绍的七种排序算法，还有一个没有介绍的基数排序，它们都是内部排序算法。

   下面我们用实际数据来测试一下这几种算法的性能。通过前面几篇博文的复习，我已经将这七种排序算法写成了一个单独的工程：
   头文件innersort.h：

/**********************************************
 filename: innersort.h
 **********************************************/
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

void bubble_sort(int a[],int len);
void select_sort(int a[],int len);
void insert_sort(int a[],int len);
void shell_sort(int a[],int len);
void merge_sort(int a[],int len);
void heap_sort(int a[],int len);
void quick_sort(int a[],int low,int high);

    源文件innersort.c：

/******************************************
 filename:innersort.c
 ******************************************/
#include "innersort.h"

//交换两个数
void swap(int *a,int *b)
{
    int t;
    t = *a;
    *a = *b;
    *b = t;
}

//冒泡排序
void bubble_sort(int a[],int len)
{
    int i,goon;
    goon = 1;
    while(goon && len--){
        goon = 0;
        for(i=0;i<len;i++){
            if(a[i]>a[i+1]){
                swap(&a[i],&a[i+1]);
                goon =1;
            }
        }
    }
}

//选择排序
void select_sort(int a[],int len)
{
    int i,j,min;
    for(i=0;i<len-1;i++){
        min = i;
        for(j=i+1;j<len;j++)
            if(a[min]>a[j])
                min = j;
        if(min != i){
            swap(&a[i],&a[min]);
        }
    }
}

//插入排序
void insert_sort(int a[],int len)
{
    int i,j,tmp;
    for(i=1;i<len;i++){
        for(j=i,tmp=a[i];j>0 && tmp < a[j-1];j--){
            a[j] = a[j-1];
        }
        a[j] = tmp;
    }
}

//希尔排序
void shell_sort(int a[],int len)
{
    int i,j,tmp,d=len;
    while((d/=2)>0){
        for(i=d;i<len;i++){
            for(j=i,tmp=a[i];j>=d && tmp < a[j-d];j-=d){
                a[j] = a[j-d];
            }
            a[j] = tmp;
        }
    }
}

//归并操作，被归并排序使用
inline void merge_ops(int a[],int alen,int b[],int blen)
{
        int i,j,k,len=alen+blen;
        int *tmp = (int*)malloc(sizeof(int)*len);

        i=j=k=0;
        while(i<alen && j<blen){
            tmp[k++] = ((a[i]<b[j]) ? a[i++]:b[j++]);
        }

        if(i>=alen && j<blen){
            memcpy(tmp+k,b+j,sizeof(int)*(blen-j));
        }
        if(j>=blen && i<alen){
            memcpy(tmp+k,a+i,sizeof(int)*(alen-i));
        }
        memcpy(a,tmp,sizeof(int)*len);
        free(tmp);
}

//归并排序
void merge_sort(int a[],int len)
{
        if(len == 1){
                return;
        }
        merge_sort(a,len/2);
        merge_sort(a+len/2,len-len/2);
        merge_ops(a,len/2,a+len/2,len-len/2);
}

//用于堆排序，计算节点i的左子节点
inline int leftChildIndex(int i)
{
        return (2*i+1);
}

//用于堆排序，计算节点i的右子节点
inline int rightChildIndex(int i)
{
        return (2*i+2);
}

//将堆调整成大根堆的元操作函数
inline void adjustHeap(int a[],int len,int i)
{
        int l,r,bigger;
        l = leftChildIndex(i);
        r = rightChildIndex(i);

        while(l<len || r<len){
                if(r<len){
                    bigger = ((a[l]>a[r])?l:r);
                }else if(l<len){
                    bigger = l;
                }else{
                    break;
                }
                if(a[bigger]>a[i]){
                    swap(&a[i],&a[bigger]);
                    i = bigger;
                    l = leftChildIndex(i);
                    r = rightChildIndex(i);
                }else
                    break;
        }
}

//建立大根堆
inline void buildHeap(int a[],int len)
{
        int i;
        for(i=len/2-1;i>=0;i--){
            adjustHeap(a,len,i);
        }
}

//堆排序
void heap_sort(int a[],int len)
{
        int i;
        buildHeap(a,len);

        while(--len > 0){
            swap(&a[0],&a[len]);
            adjustHeap(a,len,0);
        }
}

//快速排序中用于拆分子序列的操作接口
inline int partoff(int a[],int low,int high)
{
        int key = a[low];
        while(low<high)
        {
                while(low<high&&key<=a[high])
                        high--;
                if(low<high)
                        a[low++] = a[high];

                while(low<high && key >= a[low])
                        low++;
                if(low<high)
                        a[high--] = a[low];
        }
        a[low] = key;
        return low;
}

//快速排序
void quick_sort(int a[],int low,int high)
{
    int index=0;
    if(low<high)
    {
        index = partoff(a,low,high);
        quick_sort(a,low,index-1);
        quick_sort(a,index+1,high);
    }
}

    关于测量函数执行时间有很多方式，clock(), times(), gettimeofday(), getrusage()等，还有通过编译程序时，打开gcc的-pg选项，然后用gprof来测量，下面是我在网上找到的一个计算函数执行时间的版本，非常感谢博客园的“静心尽力”朋友，稍加改造一下，我们就可以通过编译时给Makefile传递不同的宏选项，打开不同的时间测量方式：

/*****************************************************
 filename: common.h
            如果定义了TEST_BY_CLOCK，则采用clock()方式计量函数的执行时间；
            如果定义了TEST_BY_TIMES，则采用times()方式计量函数的执行时间；
            如果定义了TEST_BY_GETTIMEOFDAY，则采用gettimeofday()方式计量函数的执行时间；
            如果定义了TEST_BY_GETRUSAGE，则采用getrusage()方式计量函数的执行时间；
 *****************************************************/
#include <sys/time.h>
#include <sys/resource.h>
#include <unistd.h>
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>

//用于生成随机待排序序列
#define random(x) (rand()%x)

static clock_t clockT1, clockT2;
static double doubleT1, doubleT2;

//非快速排序的统一回调测试接口
typedef void (*sfun)(int a[],int len);
//快速排序的测试接口
typedef void (*sfun2)(int a[],int low,int high);

/***************************************************
 功能说明：生成随机待排序序列
 输入参数：len-随机序列长度，range-随机序列里元素的取值范围
 输出参数：无
 返 回 值：随机序列首地址
 ***************************************************/
int *genArray(int len,int range)
{
    int i = 0;
    int *p = (int*)malloc(sizeof(int)*len);
    if(NULL == p)
        return NULL;
    srand((int)time(0));
    for(i=0;i<len;i++){
        p[i] = random(range);
    }
    return p;
}

/***************************************************
 功能说明：逐次打印给定序列里的每一个元素
 输入参数：title-提示符，a-序列首地址，len-序列长度
 输出参数：无
 返 回 值：无
 ***************************************************/
void printforeach(char *title,int a[],int len)
{
    int i = 0;
    printf("%s: ",title);
    for(i=0;i<len;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
}

double getTimeval()
{
    struct rusage stRusage;
    struct timeval stTimeval;
#ifdef TEST_BY_GETTIMEOFDAY
    gettimeofday(&stTimeval, NULL);
#endif

#ifdef TEST_BY_GETRUSAGE
    getrusage(RUSAGE_SELF, &stRusage);
    stTimeval = stRusage.ru_utime;
#endif
    return stTimeval.tv_sec + (double)stTimeval.tv_usec*1E-6;
}

void start_check(){
#ifdef TEST_BY_CLOCK
    clockT1 = clock();
#endif

#ifdef TEST_BY_TIMES
    times(&clockT1);
#endif

#ifdef TEST_BY_GETTIMEOFDAY
    doubleT1 = getTimeval();
#endif

#ifdef TEST_BY_GETRUSAGE
    doubleT1 = getTimeval();
#endif
}

void end_check(){
#ifdef TEST_BY_CLOCK
    clockT2 = clock();
    printf("Time result tested by clock = %10.30f\n",
            (double)(clockT2 - clockT1)/CLOCKS_PER_SEC);
#endif

#ifdef TEST_BY_TIMES
    times(&clockT2);
    printf("Time result tested by times = %10.30f\n",
            (double)(clockT2 - clockT1)/sysconf(_SC_CLK_TCK));
#endif

#ifdef TEST_BY_GETTIMEOFDAY
    doubleT2 = getTimeval();
    printf("Time result tested by gettimeofday = %10.30f\n",
            (double)(doubleT2 - doubleT1));
#endif

#ifdef TEST_BY_GETRUSAGE
    doubleT2 = getTimeval();
    printf("Time result tested by getrusage = %10.70f\n",
            (double)(doubleT2 - doubleT1));
#endif
}

void do_test(sfun fun_ptr,int a[],int len){
    start_check();
    (*fun_ptr)(a,len);
    end_check();
}

void do_test2(sfun2 fun_ptr,int a[],int low,int high){
    start_check();
    (*fun_ptr)(a,low,high);
    end_check();
}

    最终的测试代码如下：

#include "common.h"
#include "innersort.h"

#ifdef NOECHO
#define printforeach(...) {}
#endif

int main(int argc,char** argv){
    if(3 != argc){
        printf("Usage: %s total range \n",argv[0]);
        return 0;
    }
    int len = atoi(argv[1]);
    int range = atoi(argv[2]);

    int *p = genArray(len,range);
    int *data = (int*)malloc(sizeof(int)*len);

    memcpy(data,p,4*len);
    printforeach("Pop before",data,len);
    do_test(bubble_sort,data,len);
    printforeach("Pop after ",data,len);

    memcpy(data,p,4*len);
    printforeach("select before",data,len);
    do_test(select_sort,data,len);
    printforeach("select after ",data,len);

    memcpy(data,p,4*len);
    printforeach("Insert before",data,len);
    do_test(insert_sort,data,len);
    printforeach("Insert after ",data,len);

    memcpy(data,p,4*len);
    printforeach("Shell before",data,len);
    do_test(shell_sort,data,len);
    printforeach("Shell after ",data,len);

    memcpy(data,p,4*len);
    printforeach("merge before",data,len);
    do_test(merge_sort,data,len);
    printforeach("merge after ",data,len);

    memcpy(data,p,4*len);
    printforeach("heap before",data,len);
    do_test(heap_sort,data,len);
    printforeach("heap after ",data,len);

    memcpy(data,p,4*len);
    printforeach("quick before",data,len);
    do_test2(quick_sort,data,0,len-1);
    printforeach("quick after ",data,len);

    free(p);
    free(data);
    return 0;
}

    Makefile文件的长相如下：

TARGET = test
SRC = test.c innersort.c
OBJS = $(SRC:.c=.o)
CC = gcc
DEBUG += -pg
INCLUDE = -I.

all:$(TARGET)
$(TARGET):$(OBJS)
    $(CC) $(INCLUDE) $(DEBUG) $(CFLAGS) $(OBJS) -o $(TARGET)

%.o : %.c
    $(CC) $(INCLUDE) $(DEBUG) $(CFLAGS) -c $<
clean:
    rm -fr $(TARGET) *.out $(OBJS)

    最终，测试工程文件夹下的文件结构列表：

    如果要关闭排序前后序列的输出信息，则执行“make CFLAGS+="-DNOECHO"”，需要采用gettimeofday()来计量函数的实行时间，则执行“make CFLAGS+="-DTIME_BY_GETTIMEOFDAY -DNOECHO"”；同理需要用clock()来计量，则将TIME_BY_GETTIMEOFDAY替换成TEST_BY_CLOCK。一次测试结果如下：

    在数据量很小的情况下希尔排序的性能要比快速排序稍微好一点点，但是当数据上量级别后，在七种内部排序算法里，经过100次测试后发现，快速排序的性能绝对是最优的：
   (测试环境：CPU-AMD 速龙双核2.1GHz，内存-2G，操作系统-Fedora 17，内核版本-3.3.4)

   在下面的对比图里我们可以看到，当数据量上10万后，冒泡排序算法明显力不从心了，选择排序和插入排序性能相当，但也有点不可接受。但是当数据量达到百万后前三种算法已经跑不出结果了，但快速排序和归并排序算法排列一百万条数只需不到1秒钟的时间。当数据量达到一千万时，快速排序也只需3.8秒左右。所以，结论已经很明显了。

   当然，上述是我用gettimeofday()测量出的算法性能，感兴趣的朋友还可以用其它几种方式，或者再对比一下gprof的统计结果，看看快速排序到底是不是真汉子。
   这四篇博文是比较简单的笔记，也仅复习了常见的几种内部排序，外部排序算法还有其他新的算法都没有涉及，有机会再补充。