一道数组的程序题,帮帮忙
(1). 设计一个程序,完成以下功能:a) 产生一个20个随机数组成的数组,编写快速排序算法完成这些数从小到大排序,并将排序后结果输出;(最好能打印每轮排序结果)
b) 输入其中任何一个数字,编写折半查找算法查找该元素在排序后数组中的位置;
c) 利用分治法求解这组数中的top n元素,既是这组数中第n(n<20)大的数据。
#include <iostream> #include <algorithm> #include <random> //using namespace std; int main( void ) { int arr[20]; // a) 产生一个20个随机数组成的数组,编写快速排序算法完成这些数从小到大排序,并将排序后结果输出 { std::generate( std::begin(arr), std::end(arr), [mt=std::mt19937{std::random_device{}()},dis=std::uniform_int_distribution<>(0,99)]()mutable{return dis(mt);} ); std::sort( std::begin(arr), std::end(arr) ); std::copy( std::begin(arr), std::end(arr), std::ostream_iterator<decltype(*arr)>(std::cout," ") ); std::cout << std::endl; } // b) 输入其中任何一个数字,编写折半查找算法查找该元素在排序后数组中的位置 { std::remove_cvref_t<decltype(*arr)> n; if( !(std::cin>>n) ) return 1; auto p = std::lower_bound( std::begin(arr), std::end(arr), n ); if( p==std::end(arr) || *p!=n ) std::cout << "没发现.\n"; else std::cout << std::distance(std::begin(arr),p) << std::endl; } // c) 利用分治法求解这组数中的top n元素,既是这组数中第n(n<20)大的数据 // 这就奇怪了呀,数组已经排序好了,第i大元素就是 arr[20-1-i] 呀 // 好吧,假设我就当数组没排序过 { size_t n; if( !(std::cin>>n) || n>=std::size(arr) ) return 1; std::nth_element( std::begin(arr), std::next(std::begin(arr),std::size(arr)-1-n), std::end(arr) ); std::cout << arr[std::size(arr)-1-n] << std::endl; } }
#include <iostream> #include <algorithm> #include <random> int main( void ) { std::mt19937 gen{ std::random_device{}() }; std::uniform_int_distribution<> dis(0,99); for( size_t cnt=10; cnt--; ) { int a[20]; for( auto& v : a ) v = dis(gen); for( size_t i=0; i!=std::size(a); ++i ) printf( "%d%c", a[i], " \n"[i+1==std::size(a)] ); } return 0; }
61 36 85 27 78 19 85 28 33 97 87 34 47 38 34 89 3 12 74 98 77 28 29 48 16 6 38 80 44 67 54 55 92 61 40 31 6 98 53 35 78 71 20 55 62 39 89 72 21 32 82 53 7 36 49 50 72 8 96 17 42 88 47 12 45 31 23 2 8 93 42 17 89 92 7 35 99 98 13 0 20 24 37 86 43 34 91 24 56 10 30 39 40 38 82 11 53 91 64 82 22 91 83 65 42 92 68 83 10 49 50 3 71 65 46 60 52 87 14 9 47 94 47 8 99 7 14 78 50 43 2 98 19 69 51 55 54 98 33 11 9 89 53 52 63 93 69 29 28 70 6 33 72 78 14 43 21 9 61 42 46 64 69 20 72 28 96 92 46 81 57 0 69 87 7 8 62 17 81 24 33 86 0 42 48 62 91 53 24 58 24 56 90 86 38 80 83 5 58 16
[此贴子已经被作者于2020-12-24 10:41编辑过]
void quicksort( int a[], size_t len ) { if( len <= 1 ) return; int key = a[0]; size_t i=0, j=len-1; for( ; i!=j; ) { for( ; i!=j && !(a[j]<key); --j ); a[i] = a[j]; for( ; i!=j && !(key<a[i]); ++i ); a[j] = a[i]; } a[i] = key; quicksort( a, i ); quicksort( a+i+1, len-i-1 ); }
void nth_element( int a[], size_t len, size_t nth ) { if( len <= 1 ) return; int key = a[0]; size_t i=0, j=len-1; for( ; i!=j; ) { for( ; i!=j && !(a[j]<key); --j ); a[i] = a[j]; for( ; i!=j && !(key<a[i]); ++i ); a[j] = a[i]; } a[i] = key; if( nth < i ) return nth_element(a, i, nth); if( nth > i ) return nth_element(a+i+1, len-i-1, nth-i-1); }
// 返回第一个大于等于value的元素的下标 size_t lower_bound( const int a[], size_t len, int value ) { const int* p = a; for( size_t n=len; n>0; ) { if( p[n/2] < value ) { p += n/2+1; n -= n/2+1; } else n /= 2; } return p-a; }