#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] ); Swap( &A[Center], &A[Right-1] ); return A[Right-1]; } void Qsort( ElementType A[], int Left, int Right ){ const int Cutoff = 3; if ( Left + Cutoff <= Right ) { 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; } Swap( &A[i], &A[Right-1] ); Qsort( A, Left, i-1 ); Qsort( A, i+1, Right ); } else { int i, j; for (i = Left + 1; i <= Right; i++) { ElementType temp = A[i]; for (j = i; j > Left && A[j - 1] > temp; j--) { A[j] = A[j - 1]; } A[j] = temp; } }} int main() { int N, i; printf("请输入待排数的个数:"); scanf( "%d", &N ); ElementType A = (ElementType)malloc( N * sizeof(ElementType) ); printf("请输入要排序的数:"); 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; }删去插入排序的部分
时间: 2024-01-28 12:03:51 浏览: 19
好的,删去插入排序的部分后的代码如下:
```c
#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] );
Swap( &A[Center], &A[Right-1] );
return A[Right-1];
}
void Qsort( ElementType A[], int Left, int Right ){
const int Cutoff = 3;
if ( Left + Cutoff <= Right ) {
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;
}
Swap( &A[i], &A[Right-1] );
Qsort( A, Left, i-1 );
Qsort( A, i+1, Right );
}
}
int main() {
int N, i;
printf("请输入待排数的个数:");
scanf( "%d", &N );
ElementType A = (ElementType)malloc( N * sizeof(ElementType) );
printf("请输入要排序的数:");
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;
}
```
这是一个快速排序的实现,其中采用了三数取中法来选择枢轴元素,以减少快排的最坏时间复杂度。
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![image/gif](https://img-home.csdnimg.cn/images/20210720083352.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)