快速排序和快速选择

用同样的划分，完成不同的目的~

快速排序在  的平均时间复杂度完成排序。

快速选择在  的平均时间复杂度找出第 k 大的元素。

因为 quickSelect 只需要对划分的其中一边递归。

int partition(int a,int l, int r)
{
	int pivot = a[r];
	int i = l - 1;  //若令 i = l,然后将 i++ 放在 swap 后面会死循环 且无法正常进行划分
	//因为 i 的含义是目前小于 pivot 的最大下标，改变次序后会导致不断“与自己交换”
	for (int j = l; j <= r - 1; j++)
	{
		if (a[j] <= pivot)
		{
			i++;
			swap(a[i], a[j]);
		}
	}
	swap(a[r], a[i + 1]);
	return i + 1;
}

void quickSort(int a,int l, int r)
{
	if (l < r)
	{
		int p = partition(l, r);
		quicksort(l, p - 1);  //对于 p 位置已经排到了正确位置
		quicksort(p + 1, r);
	}
	return;
}

int partition(int a[], int l, int r)
{
	int pivot = a[r];
	int i = l - 1;
	for (int j = l; j <= r - 1; j++)
	{
		if (a[j] <= pivot)
		{
			i++;
			swap(a[i], a[j]);
		}
	}
	swap(a[r], a[i + 1]);
	return i + 1;
}

int quickSelect(int a[], int l, int r,int k) //在[l...r]区间中找第 k 大的元素
{
	if (l == r) return a[l];
	int p = partition(a, l, r);

	int i = p - l + 1; //在这个区间内是第 i 大的元素

	if (i == k)        //说明 pivot 即 ans
		return a[p];
	else if (p > k)
		return quickSelect(a, l, p - 1, k); //仍在前半区间寻找第 k 大元素
	else if (p < k)
		return quickSelect(a, p + 1, r, k - i); //在后半区间寻找第 k - i 大元素
}