POJ 2388 Who's in the Middle 排序

本文主要是介绍POJ 2388 Who's in the Middle 排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：输出一串数字的中间数。
题解：

#include <iostream>
using namespace std;
void quiksort ( int * array, int left, int right )
{
if ( left < right )
{
int s = array [( left + right ) / 2];
int l = left - 1, r = right + 1;
while ( 1 )
{
while ( array[++l] < s ); 
while ( array[--r] > s );
if ( l >= r )
break;
swap ( array[l], array[r] );
}
quiksort ( array, left, l - 1  );  
quiksort ( array, r + 1, right );  
}                                      
}                                          
int main()
{
int n, array[10010];
cin >> n;
for ( int i = 0; i < n; i++ )
cin >> array[i];
quiksort(array,0,n-1);
cout << array[n/2] << endl;
return 0;
}
或者
#include <iostream>
using namespace std;
int array[10010];
int part ( int left, int right )
{
int i = left - 1;
int s = array[right];
for ( int j = left; j < right; j++ )
{
if ( array[j] <= s )
{
i++;
swap ( array[i], array[j] );
}
}
swap ( array[right], array[i+1] );
return i + 1;
}
void Qsort ( int left, int right )
{
if ( left >= right )
return;
int p = part ( left, right );
Qsort(left,p-1);
Qsort(p+1,right);
}
int main()
{
int n;
cin >> n;
for ( int i = 0; i < n; i++ )
cin >> array[i];
Qsort(0,n-1);
cout << array[n/2] << endl;
return 0;
}

这篇关于POJ 2388 Who's in the Middle 排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---