Iterative (non-recursive) Quick Sort

Iterative (non-recursive) Quick Sort

An iterative way of writing quick sort:

#include <iostream>
#include <stack>
#include <utility>
using namespace std;

void quickSort(int A[], int n) {
	stack<pair<int, int>> stk;
	stk.push(make_pair(0, n-1));
	while (!stk.empty()) {
		pair<int, int> p = stk.top();
		stk.pop();
		int r = rand() % (p.second-p.first+1) + p.first;
		swap(A[r], A[p.first]);
		int j = p.first;
		for (int i=p.first+1; i<=p.second; ++i) {
			if (A[i] < A[p.first]) swap(A[++j], A[i]);
		}
		swap(A[p.first], A[j]);
		if (j-1 > p.first) stk.push(make_pair(p.first, j-1));
		if (j+1 < p.second) stk.push(make_pair(j+1, p.second));
	}
}

int main() {
	int A[8] = {4, 3, 5, 2, 1, 3, 2, 3};
	quickSort(A, 8);
	for (int i=0; i<8; ++i) cout<<A[i]<<" ";
	return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/119221.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • js数组字符串转数组对象_js数组对象排序

    js数组字符串转数组对象_js数组对象排序js对象使用<script>//js对象是一种无序的集合{}表示varobj={name:”张三”,age:18}//取值console.log(obj.name)//张三console.log(obj[“name”])/…

  • python安装教程[通俗易懂]

    python安装教程[通俗易懂]python安装教程本章节我们将向大家介绍如何在本地搭建Python开发环境。Python可应用于多平台包括Linux和MacOSX。你可以通过终端窗口输入"python&

  • java quartz 性能_[译]如何优化Quartz调度器性能

    java quartz 性能_[译]如何优化Quartz调度器性能译文由杰微刊兼职译者刘晓冬翻译,杰微刊审校及发布。Quartz是一个流行的Java应用开源作业调度库。eBay在自己的很多项目中用它来调度作业。Quartz在低负载时运行良好,但在高负载时会遇到问题。许多触发器会失效,导致执行线程无法得到任务,大量作业阻塞在触发器表中。所以我们必须进行性能调优。本章描述我们是如何逐步解决问题并优化Quartz的。问题在哪?1.Quartz作业不能被调度和执行。2….

  • idea2021 激活码【中文破解版】

    (idea2021 激活码)最近有小伙伴私信我,问我这边有没有免费的intellijIdea的激活码,然后我将全栈君台教程分享给他了。激活成功之后他一直表示感谢,哈哈~https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~S32P…

  • 中国名花异草故事

    中国名花异草故事中国名花异草故事作者:刘桂莉、余绮中国名花异草故事—总序  我不是旅行家,几十年来到过的地方却不少。每到一地,工作之余,对当地的一些人情、习俗、山川、风物,以至特殊的传说故事,都颇感兴趣。在谈论或介绍本地的特产时,当地人往往绘声绘色而且充满着喜悦与自豪,连带讲到的一些掌故与传奇,我也感觉兴味盎然。因为其中有些内容,活泼生动,不仅使我扩大了见闻,觉得新鲜有趣,还能增进我对这些地方历史、社会的

  • docker下载安装教程_安卓安装docker

    docker下载安装教程_安卓安装docker前言Docker提供轻量的虚拟化,你能够从Docker获得一个额外抽象层,你能够在单台机器上运行多个Docker微容器,而每个微容器里都有一个微服务或独立应用,例如你可以将Tomcat运行在一个D

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号