📄 sort.txt
字号:
}
return ;
}
int Partition(RecType r[],int low,int high)
{
int pivotkey=0;
r[0]=r[low];
pivotkey=r[low].key;
while(low<high)
{
while(low<high && r[high].key>=pivotkey) --high;
r[low]=r[high];
while(low<high && r[low].key<=pivotkey) ++low;
r[high]=r[low];
}
r[low]=r[0];
return low;
}
void QuickSort(RecType r[],int low,int high)
{
int pivotloc=0;
if( low<high )
{
pivotloc=Partition(r, low, high);
QuickSort( r,low,pivotloc-1);
QuickSort( r,pivotloc+1,high);
}
}
void ShellPass(RecType r[],int n,int dk)
{
int i,j;
for(i=dk+1;i<=n;i++)
if(r[i].key<r[i-dk].key)
{
r[0]=r[i];
for(j=i-dk;j>0&&r[0].key<r[j].key;j-=dk)
r[j+dk]=r[j];
r[j+dk]=r[0];
}
return ;
}
void ShellSort(RecType r[],int n)
{
int increment=n;
do
{ increment=increment/2;
ShellPass(r,n,increment);
}while(increment>0);
return ;
}
void HeapAdjust(RecType data[],int s, int m)
{
RecType rc;
int j;
rc=data[s]; /* 保存需调整的数据元素,空出s的记录位置 */
for(j=2*s; j<=m;j*=2) /* j<=m表示s有左孩子序号 j=2*s */
{
if (j<m&&data[j].key<data[j+1].key) /* j<m表示s有右孩子j+1 */
j++; /* 计算s的具有较大关键字的孩子的序号j */
if (rc.key> data[j].key)/* rc在s的结点时满足结点定义,调整完毕 */
break;
data[s]=data[j];s=j; /* s的较大孩子上移,修改s下移 */
} /* 正常结束时, s的结点无孩子结点。 */
data[s]=rc;
}
void HeapSort(RecType data[],int n)
{
register int i;
RecType t;
for(i=n/2;i>0;--i)
HeapAdjust(data,i,n);
for(i=n;i>1;--i)
{
t=data[1];
data[1]=data[i];
data[i]=t;
HeapAdjust(data,1,i-1);
}
}
/********************建立独立的图形初始化****************/
void initgraphics( )
{
int gdriver=DETECT,gmode;
registerbgidriver(EGAVGA_driver);
initgraph(&gdriver, &gmode,"");
}
/************ Swap_Pixels函数 *********************/
/* */
/* 交换两个数组元素,并且改变相应的象素位置 */
/* 通过打开和关闭显示来制作动画效果 */
/* */
/****************************************************/
RecType Swap_Pixels( RecType *array, int i, int j, int delay_factor)
{
RecType h;
h = *(array + i);
putpixel( 3 * i, (*(array + i)).key, 0);
putpixel( 3 * j, (*(array + i)).key, 10 );
*(array + i) = *(array + j);
putpixel( 3 * j, (*( array + j)).key, 0 );
putpixel( 3 * i, (*(array + j)).key, 10 );
*(array + j) = h;
delay( delay_factor );
return( h );
}
/****************** 冒泡排序 ***********************/
/* */
/****************************************************/
void Bubble( RecType *array, int elements, int delay_factor )
{
int i,j;
for ( i = 1; i <elements ; i++ )
for ( j = i + 1; j <=elements ; j++ )
{
if ( (*(array+i)).key > (*(array+j)).key )
Swap_Pixels( array, i, j, delay_factor );
}
}
/************ 延迟交换排序 ************************/
void Delayed( RecType *array, int elements, int delay_factor )
{
int p, h, k, i, j;
for ( p = 1; p < elements; p++ )
{
h = p;
for ( k = p + 1; k <= elements ; k++ )
if( (*(array+k)).key < (*(array+h)).key )
h = k;
if ( p != h )
{
i = h;
j = p;
Swap_Pixels( array, i, j, delay_factor );
}
}
}
/***** 希尔排序 ***********************************/
void Shell( RecType *array, int elements, int delay_factor )
{
int p, f, i, j, m;
p = elements;
while ( p >= 1)
{
p /= 2;
m = elements - p;
do{
f = 0;
for ( j = 1; j <= m; j++ )
{
i = j + p;
if( (*(array + j)).key > (*(array + i)).key )
{
Swap_Pixels( array, i, j, delay_factor );
f = 1;
}
}
} while( f );
}
}
/***** Metzner希尔排序 ****************************/
void Shell_Metzner( RecType *array, int elements, int delay_factor )
{
int p, k, t, i, j;
p = elements;
p /= 2;
while ( p != 0 )
{
k = elements - p;
for ( t = 1; t <= k; t++ )
{
i = t;
while ( i >= 1 )
{
j = i + p;
if( (*(array+j)).key < (*(array + i)).key )
{
Swap_Pixels( array, i, j, delay_factor );
i = i - p;
}
else break;
}
}
p /= 2;
}
}
/***** 快速排序 ***********************************/
void Quick( RecType *array, int left, int right, int delay_factor )
{
int i, j;
RecType t;
if ( right > left )
{
i = left - 1; j = right;
do {
do i++;
while ( array[i].key < array[right].key );
do j--;
while ( array[j].key > array[right].key && j > 0 );
t = Swap_Pixels( array, i, j, delay_factor );
} while ( j > i );
putpixel( 3*j, (*(array + j)).key, 0);
array[j] =array[i];
putpixel( 3*j, (*(array + j)).key, 10 );
putpixel( 3*i, (*(array + i)).key, 0 );
array[i] =array[right];
putpixel( 3*i, (*(array + i)).key, 10 );
putpixel( 3*right, (*(array + right)).key, 0 );
array[right] = t;
putpixel( 3*right, (*(array + right)).key, 10 );
Quick( array, left, i - 1, delay_factor );
Quick( array, i + 1, right, delay_factor );
}
}
/***** 插入排序 ***********************************/
void Insert( RecType *array, int elements, int delay_factor )
{
int p, j;
RecType t;
for ( p = 1; p < elements ; p++ )
{
t = *(array + p + 1);
for ( j = p; j >= 1; j-- )
{
if ( t.key <= (*(array + j)).key )
{
*(array + j + 1) = *(array + j);
putpixel( 3*(j + 1), (*(array + j + 1)).key, 10 );
putpixel( 3*j, (*(array + j + 1)).key, 0 );
delay( delay_factor );
}
else break;
}
*(array + j + 1) = t;
putpixel( 3*(p + 1), t.key, 0 );
putpixel( 3*(j + 1), t.key, 10 );
}
}
void main(void)
{
int key,select; /* 按键选择*/
SeqList *H=NULL; /* 记录表情况 */
int delay_factor;
clock_t start, end;
display_mainmenu( );
while(1)
{
while(bioskey(1)==0); /* 等待按键*/
key=get_key(); /*取键扫描码*/
switch(key)
{
case ALT_F: select=display_fileSM( );
switch(select)
{ case 1: CreatSequence(&H); break;
case 2: Display(H); break;
case 3: exit(0); break;
default: break;
} break;
case ALT_S: select=display_sortSM( );
switch(select)
{
case 1: start = clock();
BubbleSort(H->r,H->length);
end = clock();
printf("\n\n The time: %f\n", (end - start) / CLK_TCK);
break;
case 2: start = clock();
SelectSort(H->r,H->length);
end = clock();
printf("\n\n The time: %f\n", (end - start) / CLK_TCK);
break;
case 3: start = clock();
InsertSort(H->r,H->length);
end = clock();
printf("\n\n The time: %f\n", (end - start) / CLK_TCK);
break;
case 4: start = clock();
BinaryInsertSort(H->r,H->length);
end = clock();
printf("\n\n The time: %f\n", (end - start) / CLK_TCK);
break;
case 5: start = clock();
QuickSort(H->r,1,H->length);
end = clock();
printf("\n\n The time: %f\n", (end - start) / CLK_TCK);
break;
case 6: start = clock();
ShellSort(H->r,H->length);
end = clock();
printf("\n\n The time: %f\n", (end - start) / CLK_TCK);
break;
case 7: start = clock();
HeapSort(H->r,H->length);
end = clock();
printf("\n\n The time: %f\n", (end - start) / CLK_TCK);
break;
default: break;
} break;
case ALT_D: select=display_demoSM( );
switch(select)
{
case 1: printf("\n\n delay_factor:");
scanf("%d",&delay_factor);
initgraphics( );
start = clock();
Bubble( H->r, H->length, delay_factor );
end = clock();
closegraph();
display_mainmenu( );
printf("\n\n The time: %f\n", (end - start) / CLK_TCK);
break;
case 2: printf("\n\n delay_factor:");
scanf("%d",&delay_factor);
initgraphics( );
start = clock();
Delayed( H->r, H->length, delay_factor );
end = clock();
closegraph();
display_mainmenu( );
printf("\n\n The time: %f\n", (end - start) / CLK_TCK);
break;
case 3: printf("\n\n delay_factor:");
scanf("%d",&delay_factor);
initgraphics( );
start = clock();
Shell( H->r, H->length, delay_factor );
end = clock();
display_mainmenu( );
printf("\n\n The time: %f\n", (end - start) / CLK_TCK);
break;
case 4: printf("\n\n delay_factor:");
scanf("%d",&delay_factor);
initgraphics( );
start = clock();
Shell_Metzner( H->r, H->length, delay_factor );
end = clock();
closegraph();
display_mainmenu( );
printf("\n\n The time: %f\n", (end - start) / CLK_TCK);
break;
case 5: printf("\n\n delay_factor:");
scanf("%d",&delay_factor);
initgraphics( );
start = clock();
Quick( H->r, 1, H->length, delay_factor );
end = clock();
closegraph();
display_mainmenu( );
printf("\n\n The time: %f\n", (end - start) / CLK_TCK);
break;
case 6: printf("\n\n delay_factor:");
scanf("%d",&delay_factor);
initgraphics( );
start = clock();
Insert( H->r, H->length, delay_factor );
end = clock();
closegraph();
display_mainmenu( );
printf("\n\n The time: %f\n", (end - start) / CLK_TCK);
break;
default:break;
} break;
default: break;
}
}
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -