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 */ }补全该程序实现快速排序
时间: 2023-06-30 17:26:45 浏览: 55
下面是使用 Median3 函数实现的快速排序程序:
```
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 );
}
```
该程序中,若待排序数组大小小于等于 Cutoff,就使用插入排序,否则使用快速排序。在快速排序中,先调用 Median3 函数选取基准元素,然后将小于基准元素的元素放到基准元素左边,大于基准元素的元素放到基准元素右边,最后将基准元素换到正确的位置。然后,递归排序左子序列和右子序列。