查找最接近 S 中位数的 k 个数字的 C++ 程序,其中 S 是一组 n 个数字
这是一个C++程序,用于查找最接近S中位数的k个数字,其中S是一组n个数字。
算法
Begin function partition() for partitioning the array on the basis of values at high as pivot value: Arguments: a[]=an array. l=low H=high Body of the function: Declare variables pivot, in, i Initialize in = l Set pivot = h For i=l to h-1 if(a[i] < a[pivot]) swap a[i] and a[in]) increment in. swap a[pivot] and a[in] return in. End Begin function QuickSort() to implement quicksort algorithm to sort the data elements: Arguments: a[]=an array. l=low h=high Body of the function: declare pindex if(l < h) index = Partition(a, l, h) QuickSort(a, l, pindex-1); QuickSort(a, pindex+1, h); Return 0. End Begin Function main(), If the number of the data element are odd, Assign the middle index to low and the index next to it to high and calculate median. Run a loop for k times and print the element which his closer to the median. Else The median will be an average of two middle values . Run a loop for k times and print the element which his closer to the median. End
示例
#includeusing namespace std; void swap(int *x, int *y) { //交换两个值 int tmp; tmp = *x; *x = *y; *y = tmp; } int Partition(int a[], int l, int h) { int pivot, in, i; in = l; pivot = h; for(i=l; i < h; i++) { if(a[i] < a[pivot]) { swap(&a[i], &a[in]); in++; } } swap(&a[pivot], &a[in]); return in; } int QuickSort(int a[], int l, int h) { int pindex; if(l < h) { pindex = Partition(a, l, h); QuickSort(a, l, pindex-1); QuickSort(a, pindex+1, h); } return 0; } int main() { int n, i, h, l, k; double d1,d2, median; cout<<"输入数据集中元素的数量: "; cin>>n; int a[n]; for(i = 0; i < n; i++) { cout<<"\nEnter "<>a[i]; } cout<<"\nEnter the number of element nearest to the median required: "; cin>>k; QuickSort(a, 0, n-1); cout<<"最接近中位数的K元素是: "; if(n%2 == 1) { median = a[n/2]; h = n/2+1; l= n/2; while(k > 0) { if((median-a[l] <= a[h]-median) && l >= 0) { cout<<" "< a[h]-median) && h <= n-1) { cout<<" "< 0) { d1 = a[l]; d2 = a[h]; if((median-d2 <= d1-median) && l >= 0) { cout<<" "< d1-median) && h <= n-1) { cout<<" "<输出结果 输入数据集中元素的数量: 7 Enter 1 element: 7 Enter 2 element: 6 Enter 3 element: 5 Enter 4 element: 4 Enter 5 element: 3 Enter 6 element: 2 Enter 7 element: 1 Enter the number of element nearest to the median required: 2 最接近中位数的K元素是: 4 3