给该程序加入主函数
时间: 2024-02-25 12:52:08 浏览: 11
下面是加入主函数的完整代码:
```
#include <stdio.h>
#include <stdlib.h>
#define ElementType int
// 交换两个元素的值
void Swap( ElementType *a, ElementType *b )
{
ElementType temp = *a;
*a = *b;
*b = temp;
}
// 三数中值法选取基准元素
ElementType Median3( ElementType A[], int Left, int Right )
{
int Center = (Left+Right) / 2;
if ( A[Left] > A[Center] )
Swap( &A[Left], &A[Center] );
if ( A[Left] > A[Right] )
Swap( &A[Left], &A[Right] );
if ( A[Center] > A[Right] )
Swap( &A[Center], &A[Right] );
/* 此时A[Left] <= A[Center] <= A[Right] */
Swap( &A[Center], &A[Right-1] ); /* 将基准Pivot藏到右边*/
/* 只需要考虑A[Left+1] … A[Right-2] */
return A[Right-1]; /* 返回基准Pivot */
}
// 插入排序
void InsertionSort( ElementType A[], int N )
{
int P, i;
ElementType Tmp;
for ( P=1; P<N; P++ )
{
Tmp = A[P];
for ( i=P; i>0 && A[i-1]>Tmp; i-- )
A[i] = A[i-1];
A[i] = Tmp;
}
}
// 快速排序
void Qsort( ElementType A[], int Left, int Right )
{
const int Cutoff = 3; // 定义一个常数,用于控制小数组的大小
if ( Left + Cutoff <= Right ) // 当待排序数组大小大于 Cutoff 时,使用快速排序
{
ElementType Pivot = Median3( A, Left, Right ); // 选取基准元素
int i = Left, j = Right - 1;
while ( 1 )
{
while ( A[++i] < Pivot ) {}
while ( A[--j] > Pivot ) {}
if ( i < j ) // 将小于基准元素的元素放到基准元素左边,大于基准元素的元素放到基准元素右边
Swap( &A[i], &A[j] );
else
break; // 当 i >= j 时,跳出循环
}
Swap( &A[i], &A[Right-1] ); // 将基准元素换到正确的位置
Qsort( A, Left, i-1 ); // 递归排序左子序列
Qsort( A, i+1, Right ); // 递归排序右子序列
}
else // 当待排序数组大小小于等于 Cutoff 时,使用插入排序
InsertionSort( A+Left, Right-Left+1 );
}
int main()
{
int N, i;
scanf( "%d", &N ); // 输入待排序序列的大小
ElementType *A = (ElementType*)malloc( N * sizeof(ElementType) );
// 输入待排序序列的元素
for ( i=0; i<N; i++ )
scanf( "%d", &A[i] );
Qsort( A, 0, N-1 ); // 快速排序
// 输出排序后的序列
for ( i=0; i<N; i++ )
printf( "%d ", A[i] );
printf( "\n" );
free( A );
return 0;
}
```
在主函数中,首先输入待排序序列的大小,然后动态分配内存空间,输入待排序序列的元素。接着调用 Qsort 函数进行快速排序,最后输出排序后的序列,并释放内存空间。