（求 大哥大姐们帮助）利用分治策略，在n个不同元素中找出第k个最小元素 【 最好有算法】
把n个元素放在顺序表中，然后取第k个元素作为标准m，把n个元素重新排列，分成两个区间：小于标准m的元素区间1~j，大于标准m的元素区间j+1~n，接下来有三种情况：
1）j=k，则找到第k个元素。
2）j<k，则第k个元素在区间j+1~n。
3）j>k，则第k个元素在区间1~j。
在情况2和3中继续寻找。
[解决办法]
- C/C++ code
#include <stdio.h>#include <stdlib.h>int FindMinK(int data[], int l, int r, int k){ int m = data[l+k-1], t = 0; int i, j; data[l+k-1] = data[r], data[r] = m; for (i = l-1, j = l; j != r; ++j) if (data[j]<m) t=data[++i], data[i]=data[j], data[j]=t; t=data[++i], data[i]=data[j], data[j]=t; if (k==i-l+1) return m; if (k>i-l+1) return FindMinK(data, i+1, r, k-i+l-1); else return FindMinK(data, l, i-1, k);}int main(){ int data[]={8,6,6,4,4,3,2,1}; for (int i = 1; i <= sizeof(data)/sizeof(data[0]); ++i) printf("%d\n", FindMinK(data, 0, 7, i)); return 0;}
[解决办法]
STL的nth_element的实现：
- C/C++ code
template<typename _RandomAccessIterator> void nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last) { typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType; while (__last - __first > 3) { _RandomAccessIterator __cut = std::__unguarded_partition(__first, __last, _ValueType(std::__median(*__first, *(__first + (__last - __first) / 2), *(__last - 1)))); if (__cut <= __nth) __first = __cut; else __last = __cut; } std::__insertion_sort(__first, __last); } template<typename _RandomAccessIterator> void __insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) { if (__first == __last) return; for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) { typename iterator_traits<_RandomAccessIterator>::value_type __val = *__i; if (__val < *__first) { std::copy_backward(__first, __i, __i + 1); *__first = __val; } else std::__unguarded_linear_insert(__i, __val); } }
[解决办法]
[解决办法]
- C/C++ code
#include <stdio.h> #include <stdlib.h> #define MAXSIZE 100 typedef int datatype; typedef struct { datatype data[MAXSIZE]; int last; }SeqList; SeqList *CreatSeqList() { SeqList *L; int temp,i=0; L=(SeqList *)malloc(sizeof(SeqList)); L->last=-1; printf("please input the numbers:(End with any character)\n"); while(scanf("%d",&temp)) L->data[i++]=temp; --i; L->last=i; return L; } datatype part(SeqList *L,int a,int b,int k) { int i,j; datatype m,t; datatype* data = L->data; m=data[a+k-1], data[a+k-1] = data[b],data[b] = m; for (i=a-1, j = a; j != b; ++j) if (data[j] < m) t=data[++i], data[i]=data[j], data[j]=t; t=data[++i], data[i]=data[j], data[j]=t; if (k==i-a+1) return m; if (k>i-a+1) return part(L, i+1, b, k-i+a-1); else return part(L, a, i-1, k);} int main() { SeqList *L; datatype x; int k,n; L=CreatSeqList(); n=L->last; printf("The total number is %d\n",n+1); printf("Now you can enter number k(1 <=k <=%d):\n",n+1); fflush(stdin); scanf("%d",&k); x=part(L,0,L->last,k); printf("The %d smallest is %d",k,x); // getch(); return 0;}please input the numbers:(End with any character)1 3 4 5 7 9bThe total number is 6Now you can enter number k(1 <=k <=6):3The 3 smallest is 4Press any key to continue
[解决办法]