简述快速排序

快速排序

时间复杂度

• 最佳情况: O(n)
• 最差情况: O(n2)
• 平均情况: O(nlogn)

空间复杂度

• O(n)

演示图

动态过程

分区函数partition

inline vector<int> partition(vector<int>& arr, int l, int r) {
	//2 4 1 0 3 5
	//l         r
	//i
	//l表示左边的数字小于基数，r表示右边的树大于基数
//	int base = arr[randint(l, r)];	//优化平均时间复杂度
	int i = l, left = l - 1, right = r + 1, base = arr[l];
	while (i < right) {
		if (arr[i] > base) swap(arr[i], arr[--right]);
		else if (arr[i] < base) swap(arr[i++], arr[++left]);
		else i++;
	}
	return {left, right};
}

主函数quickSort

inline void quickSort(vector<int>& arr, int l, int r) {
	if (l >= r) return;
	vector<int> border = partition(arr, l, r);				//存放好了分区的两个边界
	quickSort(arr, l, border[0]);
	quickSort(arr, border[1], r);
}

Coding

#include <iostream>
#include <vector>
#include <cstdlib>
#include <time.h>
using namespace std;

int randint(int a, int b) {
	return rand() % (b - a + 1) + a;
}

inline vector<int> partition(vector<int>& arr, int l, int r) {
	//2 4 1 0 3 5
	//l         r
	//i
	//l表示左边的数字小于基数，r表示右边的树大于基数
//	int base = arr[randint(l, r)];	//优化平均时间复杂度
	int i = l, left = l - 1, right = r + 1, base = arr[l];
	while (i < right) {
		if (arr[i] > base) swap(arr[i], arr[--right]);
		else if (arr[i] < base) swap(arr[i++], arr[++left]);
		else i++;
	}
	return {left, right};
}

inline void quickSort(vector<int>& arr, int l, int r) {
	if (l >= r) return;
	vector<int> border = partition(arr, l, r);				//存放好了分区的两个边界
	quickSort(arr, l, border[0]);
	quickSort(arr, border[1], r);
}

int main() {
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);		//关闭同步流
	//关闭同步流相关注意事项：关闭同步流后不能再使用scanf和printf
	srand(time(nullptr));									//用时间来做时间种子（计算机只能实现伪随机）
//	cout << "randnum: " << randint(1, 100) << endl;			//测试随机函数功能
	vector<int> arr = {2, 4, 1, 0, 3, 5};
//	partition(arr, 0, arr.size() - 1);						//测试分区函数partition()的功能
	quickSort(arr, 0, arr.size() - 1);
	for (auto n : arr) cout << n << ' ';					//最后打印数组
}