前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据结构:快速排序的两种常见的partition操作以及非递归形式

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

作者头像
lexingsen
发布2022-02-24 19:08:18
2760
发布2022-02-24 19:08:18
举报
文章被收录于专栏:乐行僧的博客乐行僧的博客

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;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档