#include<stdio.h> #include<stdlib.h> #define Cutoff 20 #define MaxSize 100 typedef int ElementType; void InsertionSort ( ElementType A[ ], int N ) { int j, P; ElementType Tmp; for ( P = 1; P < N; P++ ) { Tmp = A[ P ]; for ( j = P; j > 0 && A[ j - 1 ] > Tmp; j-- ) A[ j ] = A[ j - 1 ]; A[ j ] = Tmp; } } void Swap(int *x,int *y) { int temp; temp=*x; *x=*y; *y=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 ] ); Swap( &A[ Center ], &A[ Right - 1 ] ); return A[ Right - 1 ]; } void Qsort( ElementType A[ ], int Left, int Right ) { int i, j; ElementType Pivot; if ( Left + Cutoff <= Right ) { (1)_______________________________; i = Left; j = Right - 1; for( ; ; ) { (2)_______________________________; (3)_______________________________; if ( i < j ) Swap( &A[ i ], &A[ j ] ); else break; } Swap( &A[ i ], &A[ Right - 1 ] ); (4)_________________________________; (5)_________________________________; } else InsertionSort( A + Left, Right - Left + 1 ); } void QuickSort( ElementType A[ ], int N ) { Qsort( A, 0, N - 1 ); /* A: the array */ /* 0: Left index */ /* N - 1: Right index */ } int main() { int N; int i; ElementType A[MaxSize]; scanf("%d",&N); for(i=0;i<N;i++) scanf("%d",&A[i]); QuickSort(A,N); for(i=0; i<N; i++) printf("%d ", A[i]); }

这段代码是快速排序的实现，其中使用了三个函数：InsertionSort、Median3和Qsort。其中，InsertionSort函数是插入排序，用于在小范围内对数组排序；Median3函数是找到左、中、右三个位置上的元素，并将它们按照升序排列，最后将中间元素与倒数第二个元素进行交换，并返回中间元素；Qsort函数是快速排序的核心，它首先查看数组大小是否超过了Cutoff，如果超过，就使用快速排序；否则，就使用插入排序。

在Qsort函数中，(1)处使用了Median3函数来选择主元，(2)处使用了左右指针分别向中间移动的方式来进行元素的比较和交换，(3)处是元素比较的具体实现，(4)处是将主元放回正确的位置，(5)处是对主元左右两个子数组进行递归调用。