文档章节

按升序对栈进行排序

一贱书生
 一贱书生
发布于 2016/11/17 09:46
字数 635
阅读 49
收藏 0

按升序对栈进行排序(即最大元素位于栈顶)。最多只能使用一个额外的栈存放临时数据,但不得将元素复制到别的数据结构(如数组)。

该栈支持如下操作:push, pop, peek,和isEmpty

如果可以支持两个栈,我们可以每一次遍历栈1,将最小的元素放入栈2,把栈3作为搜索时的缓冲区

1、方法一:实现初步的排序算法:搜索整个栈,找出最小元素,之后将其压入另一个栈。然后,在剩余元素中找出最小的压入栈。

 

注意:实际上需要三个栈:s1为原栈,s2位最终排好序的栈,s3在搜索s1时用作缓冲区。在s1中搜索最小值,需要弹出s1的元素,并将它们压入缓冲区s3。但最多只能使用一个额外的栈,此方法不合适。

 

 

2、方法二:

/** 
 * 从s1中逐一弹出元素,按顺序插入s2中。
 */

 

我们不需要反复搜索栈1来依次获得最小值,假设栈s是要排序的栈,栈r是已排序的栈

s = [5,10,7]

r = [12,8 ,3,1]

栈顶元素5在r中的正确位置应该是3的上面,我们可以先弹出5,反正5是无论如何都要从s压入r的,然后将12和8压入栈s,然后将5压入栈r

注意这是12和8没有在r中了,但是只要我们不改变它们在s中的顺序,重复上面的步骤,12和8一次从s弹出再压入r还是在5的上面,r依然是有序的。

时间复杂度为O(n^2),空间复杂度O(n)

 

[java] view plain copy

 

  1. import java.util.Stack;  
  2.   
  3.   
  4. public class sort {  
  5.     public static Stack<Integer> sortStk(Stack<Integer> s) {  
  6.         Stack<Integer> r = new Stack<Integer>();  
  7.         while( !s.isEmpty() ) {  
  8.             int temp = s.pop();  
  9.             while ( !r.isEmpty() && r.peek() > temp) {  
  10.                 s.push(r.pop());  
  11.             }  
  12.             r.push(temp);  
  13.         }  
  14.         return r;  
  15.     }  

方法三:

前提:若允许使用的栈数量不限。实现修改版的快速排序和归并排序,要求每层递归都创建两个额外的栈。

 *归并排序:创建两个栈,并将原栈分为两部分。递归排序每个栈,然后将其归并到一起并排好序,放回原来的栈中。

 *快速排序:创建两个额外的 栈,并根据基准元素(pivot element)将这个栈分为两个栈,这两个栈会进行递归排序,然后归并在一起,放回原来的栈中。

© 著作权归作者所有

上一篇: 实现一个栈
下一篇: 实现一个队列
一贱书生
粉丝 20
博文 724
码字总数 600123
作品 0
私信 提问
关于java8排序的实例讲解

java8以前 在java以前为了对集合排序,通常的做法是这样的 bean如下 private static class Person { } //这个例子是对集合中的元素按照年龄进行排序Collections.sort(people, new Comparator...

光与热的博客
2017/12/21
0
0
排序——升序降序的使用

前言 在做项目的过程中,偶尔会用到对集合中数据进行升序降序的排列问题,问题不是很难,但有时处理起来非常浪费时间,于是今天就把排序问题稍微处理了下,整理成一个排序工具类——Compare...

奔跑的佩恩
2017/12/26
0
0
JavaScript强化教程——sort() 方法

本文为 H5EDU 机构官方 HTML5培训 教程,主要介绍:JavaScript强化教程 —— sort() 方法 实例 数组排序:var fruits = ["Banana", "Orange", "Apple", "Mango"]; fruits.sort();fruits 输出......

zhanyingwang
2016/08/30
11
0
qsort(),sort()排序函数

一.qsort()函数 功 能: 使用快速排序例程进行排序头文件:stdlib.h用 法: void qsort(void base,int nelem,int width,int (fcmp)(const void ,const void ));参数: 1 待排序数组首地址 ...

夏雪冬日
2013/11/03
0
0
js数组的sort排序详解

代码: 知识点: 1,sort(function(a,b){return a-b;})对传入的一对值进行比较,然后返回的的值为:小于0,大于0,等于0;(大于0交换位置,反之则不) * 当小于0时,说明b>a,故b的排序靠后(...

文文1
2016/09/18
33
0

没有更多内容

加载失败,请刷新页面

加载更多

策略模式

策略模式封装的是算法,而状态模式侧重的对象状态的转变。 /** * 策略,定义计算报价算法的接口 */public interface Strategy { /** * 计算应报的价格 * @param goo...

铁骨铮铮
35分钟前
0
0
如何用JavaScript写一个区块链?

Part1实现一个基本的区块链 1.区块链 区块链是由一个个任何人都可以访问的区块构成的公共数据库。这好像没什么特别的,不过它们有一个有趣的属性:它们是不可变的。一旦一个区块被添加到区块...

骚年锦时
38分钟前
1
0
HTTP协议

HTTP简介 HTTP协议是Hyper Text Transfer Protocol(超文本传输协议)的缩写,是用于从万维网(WWW:World Wide Web )服务器传输超文本到本地浏览器的传送协议。 HTTP是一个基于TCP/IP通信协议...

惊尘大人
40分钟前
1
0
Feign输出Info级别日志

背景   spring cloud netfix组件中,feign相关的日志默认是不会输出的,需要自定义配置才能输出,并且Feign只对Debug基本的日志做出响应, 实际业务需要输出Info级别的日志,所以需要做自定...

xiaomin0322
46分钟前
3
0
面向解决问题的java编程,spring boot,mybatis generator和坑-1starter

1、start一个spring boot项目 第一课我们也不能免俗,要从starter开始,spring boot的起始项目脚手架可以从spring boot官方starter生成地址开始:https://start.spring.io/ 这张图列出了一个...

wphmoon
46分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部