快排

基本概念

• 分治 思想
• 选定一个数（一般是中间），以这个数为基准，将小于它的数放在它左边，大于的数在右边，（如果要从小到大）等于的数在左边或右边都行。
• 再以这个数为界排序左右分段，最终实现排序
• 最好是 $O(n)$ 最差是 $O(n^2)$

• 具体实现

  • 找分界点，直接相加除2
  • 递归处理各段

• 代码实现

void quick_sort(int a[], int l, int r)
{
 if(l >= r)
     return;
 
 int x = q[l + r >> 1], i = l - 1, j = r + 1;//因为用do，while
   								  //要注意的是，此处的x取值与下面的递归有关系，若x取l，
   								  //下面递归不能用i-1和i，会出现无限循环，在输入为1，2时
 
 while(i < j)
 {
     do i ++;
     while(q[i] < x);//左边找大于x
 
     do  j --;
     while(q[j] > x);//右边找小于x
 
     if(i < j)
   	  swap(q[i], q[j]);
 }
 
 quick_sort(q, l, j);//第一次调整好后，分开再调整
 quick_sort(q, j + 1, r);
}

• 另有快速选择

• 排序一样，只是要找到排序后的第k个数
• 使用返回 递归函数 来实现
• 外加 if 语句来选择每要查找的数在哪一边，只递归那一边就可以

三路排序

void quick_sort(int a[], const int len)
{
	if(len <= 1) return;
	const int pivot = a[rand() % len];
 
	//i,当前操作数
	//a[0, j) 存储小于pivot的元素
	//a[k, len) 存储大于pivo的元素
	
	int i = 0, j = 0, k = len;
	while(i < k)
	{
		if(a[i] < pivot)
			swap(a[i ++], a[j ++]);
		else if(pivot < a[i])
			swap(a[i], a[-- k]);
		else
			i ++;
	}
	quick_sort(a, j);
	quick_sort(a + k, len - k);
}

内省排序

sort实现就是内省排序 当时间复杂度超过限制后转换为堆排序，保证$O(nlogn)$