#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]); }
时间: 2024-01-24 08:02:06 浏览: 35
这是一个使用经典的快速排序算法实现的 C 代码。在此代码中,使用了经典的快速排序算法和三数取中法来优化算法的效率,同时也加入了插入排序以优化小数组的排序速度。这样的实现可以在大多数情况下保持较好的效率。
```c
#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 )
{
Pivot = Median3( A, Left, Right );
i = Left; j = Right - 1;
for( ; ; )
{
while( A[ ++i ] < Pivot ) {}
while( A[ --j ] > Pivot ) {}
if ( i < j )
Swap( &A[ i ], &A[ j ] );
else
break;
}
Swap( &A[ i ], &A[ Right - 1 ] );
Qsort( A, Left, i - 1 );
Qsort( A, i + 1, Right );
}
else
InsertionSort( A + Left, Right - Left + 1 );
}
void QuickSort( ElementType A[ ], int N )
{
Qsort( A, 0, N - 1 );
}
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]);
}
```
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)