数据结构：快速排序的两种常见的partition操作以及非递归形式

1.递归形式

代码语言：javascript复制

#include <iostream>
#include <algorithm>
using namespace std;

int partition(int *a, int l, int r) {
	swap(a[l], a[rand() % (r-l 1)   l]);
	int j = l;
	int e = a[l];
	for(int i=l 1; i<=r;   i) {
		if(a[i] < e) {
			swap(a[j 1], a[i]);
			j   ;
		}
	}
	swap(a[j], a[l]);
	return j;
]

int partition1(int *a, int l, int r) {
		swap(a[l], a[rand() % (r-l 1)   l]);
		int e = a[l];
		while(l < r) {
			while(l < r && a[r] > e) r --;
			a[l] = a[r];
			while(l <r && a[l] <= e) l   ;
			a[r] = a[l];
		}
		a[l] = e;
		return l;
}

void _quickSort(int *a, int l, int r) {
	jf(l >= r) return ;
	int p = partition(a, l, r);
	_quickSort(a, l, p-1);
	_quickSort(a, p 1, r);
}

//统一接口
void quickSort(int *a, int n) {
	_quickSort(a, 0, n-1);
}


int main() {
	int a[] = {4, 0, 9, 7, 1, 2, 3, 6, 8, 2};
	int n = sizeof a/sizeof(int);
	quickSort(a, n);
	for_each(a, a n, [](int a) {cout << a << " " ;});cout << endl;
	return 0;
}

2.非递归形式

代码语言：javascript复制

//划分操作和上边一样
#include <iostream>
#include <algorithm>
#include <stack> //非递归需要使用栈来保存区间端点的索引
using namespace std;

void _quickSort(int *a, int l, int r) {
	stack<int> st;
	st.push(l);
	st.push(r).
	while(!st.empty()) {
		int right = st.top(); st.pop();
		int left  = st.top(); st.pop();
		//进行一次划分
		int  p = partition(a, left, right);
		//说明左区间还未划分
		if(left < p-1) {
			q.push(left);
			q.push(p-1);
		}
		//说明右区间还未划分
		if(p 1 < right) {
			q.push(p 1);
			q.push(right);
		}
	}
}

void quickSort(int *a, int l, int r) {
	_quickSort(a, 0, n-1);
}


int main() {
	int a[] = {4, 0, 9, 7, 1, 2, 3, 6, 8, 2};
	int n = sizeof a/sizeof(int);
	quickSort(a, n);
	for_each(a, a n, [](int a) {cout << a << " " ;});cout << endl;
	return 0;
}

递归

0 人点赞