数据结构课程上讲过的,今天终于有机会实现啦。
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int N = 1e6 + 5; int a[N]; void quick_sort(int l,int r) { if(l >= r) return ; int magic = rand() % (r - l) + l + 1; swap(a[l],a[magic]); int i = l, j = r; while(true) { while(i < j && a[j] >= a[i]) j--; if(i == j) break; swap(a[i++],a[j]); while(i < j && a[i] <= a[j]) i++; if(i == j) break; swap(a[i],a[j--]); } quick_sort(l,i-1); quick_sort(j+1,r); } int main() { int n; while(~scanf("%d",&n)) { for(int i=0;i<n;i++) scanf("%d",&a[i]); quick_sort(0,n-1); for(int i=0;i<n;i++) printf("%d ",a[i]); puts(""); } return 0; }
扩展:找第K大元素。复杂度O(n),不需要对整个数组进行排序。
发现 STL 有实现,叫 nth_element(),复杂度 O(n)。
default (1) |
template <class RandomAccessIterator> void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); |
---|---|
custom (2) |
template <class RandomAccessIterator, class Compare> void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp); |
再扩展一个叫 partial_sort(),保留前K大,复杂度 O(n * log k)。
efault (1) |
template <class RandomAccessIterator> void partial_sort (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last); |
---|---|
custom (2) |
template <class RandomAccessIterator, class Compare> void partial_sort (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp); |
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int N = 1e4 + 5; int a[N]; int quick_select(int l,int r,int k) { int magic = rand() % (r - l) + l + 1; swap(a[l],a[magic]); int i = l, j = r; while(true) { while(i < j && a[j] >= a[i]) j--; if(i == j) break; swap(a[i++],a[j]); while(i < j && a[i] <= a[j]) i++; if(i == j) break; swap(a[i],a[j--]); } if(k == i - l + 1) return a[i]; else if(k < i - l + 1) return quick_select(l,i-1,k); else return quick_select(j+1,r,k-(i-l+1)); } int main() { int n,k; while(~scanf("%d%d",&n,&k)) { for(int i=0;i<n;i++) scanf("%d",&a[i]); printf("%d\n",quick_select(0,n-1,n+1-k)); } return 0; }