快速排序

\(M:O(log_2n)\)
\(BestT:O(nlog_2n)\)
\(AverageT:O(nlog_2n)\)
\(WorseT:O(n^2)\)

Step

1. 选择基准数（随机或首位）；
2. 把小于基准数的挪到基准左边，大于的挪到右边（双指针）；
3. 递归到两个子序列中分别进行快速排序；
4. 不用合并，因为此时数列已经完全有序。

int a[10034];
void QuickSort(int l ,int r){//[l, r)
	if(l>=r)return;
	if(l+1==r){
		if(a[l]>a[r])swap(a[l], a[r]);
		return;
	}
	int temp=a[l];
	int i=l, j=r;
	while(i<j){
		if(a[j]>temp){
			--j;
			continue;
		}
		if(a[i]<temp){
			++i;
			continue;
		}
		swap(a[i], a[j]); 
	}
	a[i]=temp;
	QuickSort(l, i-1);
	QuickSort(i+1, r);
}

应用

求第\(k\)小元素

分析
为了不\(TLE\)，我们需要高效
在快排递归时判断

if(k>i)return QuickSort(i+1, r);
else if(k<i)return QuickSort(l, i-1);
else return a[i];

归并排序

\(M:O(log_2n)\)
\(BestT:O(n^2)\)
\(AverageT:O(n^2)\)
\(WorseT:O(n^2)\)

Step

1. 将数列划分为两部分；
2. 递归地分别对两个子序列进行归并排序；
3. 合并两个子序列。(双指针)

int a[MAXN], t[MAXN];
void Merge_sort(int ll, int rr) {//[ll, rr)
	if (rr - ll <= 1) return;
	int mid = ll + (rr - ll >> 1);
	merge(ll, mid);
	merge(mid, rr);
	int p = ll, q = mid, s = ll;
	while (s < rr) {
		if (p >= mid || (q < rr && a[p] > a[q])){
			t[s++] = a[q++];
		} 
		else t[s++] = a[p++];
	}
	for (int i = ll; i < rr; ++i) a[i] = t[i];
}

应用

求逆序对数
对于\(i>j, a_i<a_j\)的\((i, j)\)数对被称作一对逆序对

分析
在归并时，若\(a_p>a_q\)，则\(a_{[mid, p]}>a_q\)，所以合并时

while (s < rr) {
	if (p >= mid || (q < rr && a[p] > a[q])){
		t[s++] = a[q++];
  	        ans += mid - p;
	} 
	else t[s++] = a[p++];
}

知识整理-快排/归并

原文：https://www.cnblogs.com/AzZr-site783/p/14479783.html