几种排序方法的动态特征（TC图形模式表述）
------------------------------------------声明：本帖的主体内容和思想不属于我的原创。在我看《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]]
Sort_JFD.rar
