## 快速排序

2017年12月16日 ⁄ 综合 ⁄ 共 1791字 ⁄ 字号 评论关闭

```#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;
}```

 default (1) ```template void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); ``` ```template void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);```

 efault (1) ```template void partial_sort (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last); ``` ```template 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;
}```