------------------------------------------
声明：本帖的主体内容和思想不属于我的原创。在我看《C算法》（Algorithms In C Third Edition， 作者：Robert Sedgewick）的电子书时，看到排序的时候作者用了这样的图来描述动态特征，我觉得非常有趣。因此在这里我采用TC绘图方式实现描述排序的动态特征，可以看到不同排序方法中的排序过程。
------------------------------------------
    在这里示范了选择，插入，冒泡，摇摆，希尔，快速等基本排序的动态特征，除了ShakedBubble属于课后习题是我自己写的以外，其他排序代码基本原样引用该书第一卷第6章中的代码。有时间再补充其他排序方法。下面给出的是用散点表示的代码，排序前为随机散落的点，排序以后会点会落到对角线上。在附件中还包含用柱状线表示的动态排序过程（动态柱线的代码类似，因此省略）。

/*
    演示基本排序的动态特征图形
    code by hoodlum1980
    2008年10月9日
*/
#include <stdio.h>
#include <graphics.h>
#include <stdlib.h> /* random() */
#include <dos.h> /* delay() */
#include <time.h> /* clock() */

typedef void (*SORTFUNC)(int [], int, int); /*定义排序方法的指针*/

/*排序元素的数量*/
#define NMAX         1000
/*要排序的数组*/
int a[NMAX];

/*矩形边界坐标*/
#define BLEFT         150
#define BTOP             50
#define BWIDTH         200
#define BHEIGHT     200
#define BBOTTOM     (BTOP+BHEIGHT)
#define BRIGHT        (BLEFT+BWIDTH)

/*把数组索引换算为横坐标，把被排序元素的值换算为纵坐标*/
#define GET_X(pindex)    (int)(BLEFT + BWIDTH*1.0/NMAX*(pindex))
#define GET_Y(pvalue)    (int)(BTOP + BHEIGHT*1.0/NMAX*(NMAX-1-(pvalue)))

/*初始化数组，根据type分别初始化为随机，有序，逆序*/
/*type= 0: random; 1: ascent , 2: descent */
void InitArray(int a[], int length, int type)
{
    int i;
    setcolor(WHITE);
    setfillstyle(SOLID_FILL, BLACK);
    bar(BLEFT-1,BTOP-1,BLEFT+BWIDTH+1, BTOP+BHEIGHT+1);
    rectangle(BLEFT-1,BTOP-1,BLEFT+BWIDTH+1,BTOP+BHEIGHT+1);
    rectangle(BLEFT-12,BTOP-12,BLEFT+BWIDTH+12, BTOP+BHEIGHT+12);
    setfillstyle(SOLID_FILL, DARKGRAY);
    floodfill(BLEFT-5, BTOP-5, getcolor());
    for(i=0;i<length;i++)
    {
        switch(type)
        {
            case 1: a[i]=i; break;
            case 2: a[i]=length-1-i;break;
            default: a[i]=random(length); break;
        }
        putpixel(GET_X(i),GET_Y(a[i]),YELLOW);
    }
}

/*在矩形的下方，显示一个字符串信息*/
void DisplayText(char* text)
{
    setcolor(WHITE);
    setfillstyle(SOLID_FILL, BLACK);
    bar(BLEFT-1,BTOP+BHEIGHT+20,BLEFT+BWIDTH+200, BTOP+BHEIGHT+60);
    outtextxy(BLEFT+2, BTOP+BHEIGHT+22, text);
}

/*改变数组a某个位置的值*/
void ChangeValue(int a[], int index, int newValue)
{
    putpixel(GET_X(index), GET_Y(a[index]), BLACK);
    a[index]=newValue;
    putpixel(GET_X(index), GET_Y(a[index]), YELLOW);
}

/*交换两个元素*/
void exch(int a[], int t1, int t2)
{
    int temp;
    temp=a[t1];
    ChangeValue(a, t1, a[t2]);    /*a[t1]=a[t2];*/
    ChangeValue(a, t2, temp);        /*a[t2]=temp;*/
}

/*比较并在必要时交换，让 第二项 >= 第一项*/
void compexch(int a[], int t1, int t2)
{
    if(a[t1]>a[t2])
        exch(a, t1, t2);
}

/*选择排序：（移动数据次数最少的排序方法）
  代码引用自：<<C算法（第一卷 基础、数据结构、排序和搜索）（第三版）>>

 */
void Selection(int a[], int left, int right)
{
    int i,j,min;
    for(i=left; i<right; i++)
    {
        min=i;
        for(j=i+1; j<=right; j++)
            if(a[j]<a[min]) min=j;
        exch(a, i, min);
    }
}

/*插入排序：效率低，但代码简洁一些

 */
void InsertionSlow(int a[], int left, int right)
{
    int i, j;
    for(i=left+1;i<=right;i++)
        for(j=i;j>left;j--)
            compexch(a, j-1, j);
}

/*插入排序：是对InsertionSlow的改进和提速
  代码引用自：<<C算法（第一卷 基础、数据结构、排序和搜索）（第三版）>>

 */
void Insertion(int a[], int left, int right)
{
    int i, j, temp;
    for(i=left+1; i<=right; i++)/*扫描一遍，把最小值放在第一个位置*/
        compexch(a, left, i);
    for(i=left+2; i<=right; i++)
    {
        j=i;
        temp=a[i];/*缓存待插入值*/
        while(temp<a[j-1]) /*找出要插入的位置j*/
        {
            ChangeValue(a, j, a[j-1]); /*a[j]=a[j-1]; 大于插入值的数据整体向后移动*/
            j--;
        }
        ChangeValue(a, j, temp); /*插入该值*/
    }
}

/*希尔排序：改进插入排序数据移动距离长而缓慢的缺点
  代码引用自：<<C算法（第一卷 基础、数据结构、排序和搜索）（第三版）>>

 */
void ShellSort(int a[], int left, int right)
{
    int i, j, h, temp;/*h为间隔*/
    /*求出h初始间隔*/
    for(h=1; h<=(right-1)/9; h=3*h+1);
    /*对h的递减序列进行 h间隔插入排序*/
    for(; h>0; h/=3)
    {
        for(i=left+h; i<=right; i++)
        {
            j=i;
            temp=a[i];
            while(j >= left+h && temp<a[j-h])
            {
                ChangeValue(a, j, a[j-h]); /*a[j]=a[j-h];*/
                j-=h;
            }
            ChangeValue(a, j, temp); /*a[j]=temp;*/
        }
    }
}

/*冒泡排序：
  代码引用自：<<C算法（第一卷 基础、数据结构、排序和搜索）（第三版）>>

 */
void Bubble(int a[], int left, int right)
{
    int i, j;
    for(i=left;i<right;i++)
        for(j=right;j>i;j--)
            compexch(a, j-1, j);
}

/*摇摆式冒泡排序：扫描方向交替，但貌似并不比普通冒泡快

 */
void ShakedBubble(int a[], int left, int right)
{
    int j;
    /*摇摆式扫描！交替上浮下沉，未排序区间左右摇摆，逐渐缩小到到中点*/
    while(left<right)
    {
        /*选一个最小的下沉*/
        for(j=right;j>left;j--)
            compexch(a, j-1, j);
        left++;

        /*选一个最大的上浮*/
        for(j=left+1;j<=right;j++)
            compexch(a, j-1, j);
        right--;
    }
}

/*快速排序的划分函数，QSort会调用该函数进行划分*/
int Partition(int a[],int left,int right)
{
    int i=left,j=right+1;
    int key=a[left],temp;    /*缓存最左边元素的值，以该值划分！*/
    while(1)
    {
        while(a[++i]<key && i<right);
        while(a[--j]>key);
        /*如果i和j相遇，说明扫描一次结束*/
        if(i>=j)
            break;
        exch(a,i,j);/* swap(a[i],a[j] */
    }
    /*swap(a[left],a[j]*/
    ChangeValue(a, left, a[j]);    /*a[left]=a[j];*/ /*把key所在位置的元素放到最左端的key的位置*/
    ChangeValue(a, j, key);            /*a[j]=key;*/            /*把key移动到正确的位置，即它最终在有序列中的位置*/
    return j;
}

/*快速排序*/
void QSort(int a[],int left,int right)
{
    int p, i, key;
    if(left<right)/*回归条件*/
    {
        key=a[left];
        p=Partition(a,left,right);
        QSort(a,left,p-1);    /*左半段排序*/
        QSort(a,p+1,right); /*右半段排序*/
    }
}

void main()
{
    int             gdriver=DETECT, gmode, i, j;
    clock_t     timebase, time[10][3];
    char            text[128];
    char*            orders[] = {"random  ",    "asc     ", "desc    "}; /*被排序数组的类型*/
    char*         names[] =    
        {
            "InsertionSlow", "Insertion    ", "ShellSort    ",    "Bubble       ", 
            "ShakedBubble ", "Selection    ",    "QSort        "
        };
    SORTFUNC     funcs[]={InsertionSlow, Insertion, ShellSort, Bubble, ShakedBubble, Selection, QSort };

    initgraph(&gdriver,&gmode,"");
    for(i=0; i< sizeof(funcs)/sizeof(funcs[0]);i++)
    {
        for(j=0; j<3; j++) /*做不同的初始化*/
        {
            sprintf(text, "%s-%s", names[i], orders[j]);
            DisplayText(text);
            InitArray(a, NMAX, j);
            timebase=clock();
            (funcs[i])(a, 0, NMAX-1);
            time[i][j]=clock()-timebase;
            getch();
        }
    }
    closegraph();

    /*输出计时时间*/
    printf(" ------------------------------------------ \n");
    printf("                |  random      asc     desc \n");
    printf(" ------------------------------------------ \n");
    for(i=0; i< sizeof(funcs)/sizeof(funcs[0]);i++)
    {
        printf("  %s |", names[i]);
        for(j=0; j<3; j++) printf("%8ld ", time[i][j]);
        printf("\n ------------------------------------------ \n");
    }
    getch();
}

[[it] 本帖最后由 hoodlum1980 于 2008-10-11 15:00 编辑 [/it]]