QuickSort理解

【复习】 快速排序原理（QuickSort）

题目链接

• 最最常用的经典排序算法之一：快速排序（QuickSort），时间复杂度为$nlogn$，这里复习一遍。

---

快速排序

原理解释

核心步骤：

1. 对于一个无序序列，我们首先随便选取（其实随机选取是最优的，但通常我们都选开头结尾或中间）一个key元素；

2. 经过一顿排序，将序列中小于key元素的元素都置于其左边，大于key元素的元素，都置于其右边；

3. 分别对key元素左右两侧的序列（也是无序的）重复1、2步骤（可以递归实现），直至整个序列有序。

帮助理解的图

伪代码

void qsort(int l,int r){
	int i=l,j=r;
	确定key;
	将小于key的都放到key左边，大于key的都放到key右边；
	if(l<j) qsort(l,j);
	if(r>i) qsort(i,r);
}

模板代码（含注释）

#include<bits/stdc++.h>
using namespace std;

int a[100000005];

void qsort(int l,int r){ //quick sort function
	int i=l,j=r,key=(l+r)>>1; // 中间元素定位key
	do{ //do while循环
		while(a[i]<a[key]) i++; //从左往右找到第一个大于key的元素
		while(a[j]>a[key]) j--; //从右往左找到第一个小于key的元素
		if(i<=j){
			swap(a[i],a[j]); // 交换他们俩
			i++;j--; //别漏了这个
		}
	}while(i<=j);
	if(l<j) qsort(l,j); //递归 分而治之
	if(r>i) qsort(i,r); //同上
}

int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]; //input
	}
	qsort(1,n); //quick sort
	for(int i=1;i<=n;i++){
		cout<<a[i]<<" "; //output
	}
	return 0;
}

---