快速排序

算法思想：

• 注意与归并排序分界点的不同在于，快速排序的分界点是数组里的值，而归并排序的分界点是下标位置。
• 手写的作用：比如说让你排序字符串！
• 快速排序是不稳定的。
• 快速排序的时间复杂度是nlogn
• 递归处理左右两段的时候，如果用j度量，x可以取q[l]和q[l+r>>1],如果用i度量，x可以取q[r]和q[l+r>>1]。
• C++的sort是优化了的快速排序，sort在小范围的时候用插入排序，大范围的时候用快速排序。

代码体现：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int p[maxn];
void quick_sort(int l,int r)
{
    if(l>=r) return;
    int x=p[l+r>>1];
    int i=l-1;
    int j=r+1;
    while(i<j)
    {
        do i++; while(p[i]<x);
        do j--; while(p[j]>x);
        if(i<j) swap(p[i],p[j]);
    }
    quick_sort(l,j);
    quick_sort(j+1,r);
}

快速选择

代码实现：

返回第k小的数
int quick_sortse(int q[],int l,int r,int k)
{
	if(l==r) return q[l];
	int x=q[(l+r)>>1];
	int i=l-1;
	int j=r+1;
	while(i<j)
	{
		do i++; while(q[i]<x);
		do j--; while(q[j]>x);
		if(i<j) swap(q[i],q[j]);
	}
	if(k<=j-l+1) return quick_sortse(q,l,j,k);
	else return quick_sortse(q,j+1,r,k-j+l-1);
}

快速排序

原文：https://www.cnblogs.com/codertea/p/12798120.html