hoodlum1980 发布留言 2008-10-9 05:21 几种排序方法的动态特征（TC图形模式表述）------------------------------------------ 声明：本帖的主体内容和思想不属于我的原创。在我看《C算法》（Algorithms In C Third Edition， 作者：Robert Sedgewick）的电子书时，看到排序的时候作者用了这样的图来描述动态特征，我觉得非常有趣。因此在这里我采用TC绘图方式实现描述排序的动态特征，可以看到不同排序方法中的排序过程。 ------------------------------------------ 在这里示范了选择，插入，冒泡，摇摆，希尔，快速等基本排序的动态特征，除了ShakedBubble属于课后习题是我自己写的以外，其他排序代码基本原样引用该书第一卷第6章中的代码。有时间再补充其他排序方法。下面给出的是用散点表示的代码，排序前为随机散落的点，排序以后会点会落到对角线上。在附件中还包含用柱状线表示的动态排序过程（动态柱线的代码类似，因此省略）。 [code]/* 演示基本排序的动态特征图形 code by hoodlum1980 2008年10月9日 */ #include
#include
#include /* random */
#include /* delay */
#include /*clock*/
typedef void (*SORTFUNC)(int [], int, int); /*定义排序方法的指针*/
/*排序元素的数量*/
#define NMAX 1000
/*要排序的数组*/
int a[NMAX];
/*矩形边界坐标*/
#define BLEFT 100
#define BTOP 20
#define BWIDTH 100
#define BHEIGHT 100
/*把数组索引换算为横坐标，把被排序元素的值换算为纵坐标*/
#define GET_X(pindex) (int)((pindex)*1.0/NMAX*BWIDTH + BLEFT)
#define GET_Y(pvalue) (int)((pvalue)*1.0/NMAX*BHEIGHT + BTOP)
/*初始化数组*/
void InitArray(int a[], int length)
{
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);
for(i=0;i {
a),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某个位置的值, ShellSort会调用这个方法*/
void ChangeValue(int a[], int index, int newValue)
{
putpixel(GET_X(index), GET_Y(a), BLACK);
a=newValue;
putpixel(GET_X(index), GET_Y(a), YELLOW);
}
/*交换两个元素*/
void exch(int a[], int t1, int t2)
{
int temp;
putpixel(GET_X(t1),GET_Y(a[t1]),BLACK);
putpixel(GET_X(t2),GET_Y(a[t2]),BLACK);
temp=a[t1];
a[t1]=a[t2];
a[t2]=temp;
putpixel(GET_X(t1),GET_Y(a[t1]),YELLOW);
putpixel(GET_X(t2),GET_Y(a[t2]),YELLOW);
}
/*比较并在必要时交换，让 第二项 >= 第一项*/
void compexch(int a[], int t1, int t2)
{
if(a[t1]>a[t2])
exch(a, t1, t2);
}
/*选择排序：（移动数据次数最少的排序方法）
代码引用自：<>
*/
void Selection(int a[], int left, int right)
{
int i,j,min;
for(i=left; i {
min=i;
for(j=i+1; j<=right; j++)
if(a[j] exch(a, i, min);
}
}
/*插入排序：
代码引用自：<>
*/
void Insertion(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);
}
/*希尔排序：改进插入排序数据移动距离长而缓慢的缺点
代码引用自：<>
*/
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)
{
ChangeValue(a, j, a[j-h]); /*a[j]=a[j-h];*/
j-=h;
}
ChangeValue(a, j, temp); /*a[j]=temp;*/
}
}
}
/*冒泡排序：
代码引用自：<>
*/
void Bubble(int a[], int left, int right)
{
int i, j;
for(i=left;i for(j=right;j>i;j--)
compexch(a, j-1, j);
}
/*摇摆式冒泡排序：扫描方向交替，但貌似并不比普通冒泡快
*/
void ShakedBubble(int a[], int left, int right)
{
int j;
/*摇摆式扫描！交替上浮下沉，未排序区间左右摇摆，逐渐缩小到到中点*/
while(left {
/*选一个最小的下沉*/
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] while(a[--j]>key);
/*如果i和j相遇，说明扫描一次结束*/
if(i>=j)
break;
exch(a,i,j);/* swap(a */
}
/*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 {
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;
clock_t timebase, time[10];
char* names[]={"Insertion", "ShellSort", "Bubble", "ShakedBubble", "Selection", "QSort"};
SORTFUNC funcs[]={ Insertion, ShellSort, Bubble, ShakedBubble, Selection, QSort };
initgraph(&gdriver,&gmode,"");
for(i=0; i< sizeof(funcs)/sizeof(funcs[0]);i++)
{
DisplayText(names)(a, 0, NMAX-1);
time);i++)
{
printf("%s: \t %-8d\n", names);
}
}[/code]
[ 本帖最后由 hoodlum1980 于 2008-10-9 18:04 编辑 [/it]]
页: [1]
特别说明：如网页特效代码中有引用图片文件等，请自己下载到本地调试！ |
