`
daojin
  • 浏览: 689529 次
  • 性别: Icon_minigender_1
  • 来自: 西安
社区版块
存档分类
最新评论

面试题目之 ----使用非迭代方法快速排序

 
阅读更多
1.教科書上使用迭代的方法進行快速排序,原则上所有的迭代都可以用自定义栈来转换为非迭代算法。

假如最少两个构成一段, 当前的分段个数一定不会超过length/2.
用两个数组表示各个分段:
int[] low = new int[length/2];
int[] high = new int[length/2];

每次循环只拆分栈顶的那个分段,用index 变量记录栈顶,并加入第一个根分段:

int index = 0;
low[index] = 0;
high[index] = values.length - 1;

然后使用while循环
while (index >= 0) {
  int plow = low[index];
  int phigh = high[index];
  int pivoit = low[index];
  int pivoitVluae = values[pivoit];
 
  Onetimequicksort();
}

package interview;

public class QuickSortNotRecursive {

	public static void main(String[] args) {
		int[] values = new int[] {
				7, 13, 4, 246
		};
		quickSort(values.length, values);
		for(int i = 0; i < values.length; ++ i) {
			System.out.println(values[i]);
		}
	}

	public static void quickSort(int length, int[] values) {
		int[] low = new int[length];
		int[] high = new int[length];
		int index = 0;
		low[index] = 0;
		high[index] = values.length - 1;
		while (index >= 0) {
			int plow = low[index];
			int phigh = high[index];
			int pivoit = low[index];
			int pivoitVluae = values[pivoit];
			while (plow < phigh) {
				while (plow <= phigh) {
					if (values[phigh] >= pivoitVluae) {
						values[pivoit] = values[phigh];
						pivoit = phigh;
						phigh --;
						break;
					}else {
						phigh --;
					}
				}
				while (plow <= phigh) {
					if (values[plow] < pivoitVluae) {
						values[pivoit] = values[plow];
						pivoit = plow;
						plow++;
						break;
					}else {
						plow ++;
					}
				}
			}
			values[pivoit] = pivoitVluae;

			int topLow = low[index];
			int topHigh = high[index];
			index--;
			if (pivoit - 1 > topLow) {
				index++;
				low[index] = topLow;
				high[index] = pivoit - 1;
			}
			if (pivoit + 1 < topHigh) {
				index++;
				low[index] = pivoit + 1;
				high[index] = topHigh;
			}
		}
	}
}





经过测试,工作正常。

采用教科书的更优化的一趟快速排序
	public static void quickSort2(int length, int[] values) {
		if (values.length < 2) {
			return;
		}
		int[] low = new int[(length) / 2];
		int[] high = new int[(length) / 2];
		int topIndex = 0;
		low[topIndex] = 0;
		high[topIndex] = values.length - 1;
		while (topIndex >= 0) {
			int plow = low[topIndex];
			int phigh = high[topIndex];
			int pivoitVluae = values[plow];

			while (plow < phigh) {
				while (plow < phigh) {
					if (values[phigh] > pivoitVluae) {
						values[plow] = values[phigh];
						break;
					} else {
						phigh--;
					}
				}
				while (plow < phigh) {
					if (values[plow] < pivoitVluae) {
						values[phigh] = values[plow];
						break;
					} else {
						plow++;
					}
				}
			}
			values[plow] = pivoitVluae;
			
			int topLow = low[topIndex];
			int topHigh = high[topIndex];
			topIndex--;
			if (plow - 1 > topLow) {
				topIndex++;
				low[topIndex] = topLow;
				high[topIndex] = plow - 1;
			}
			if (plow + 1 < topHigh) {
				topIndex++;
				low[topIndex] = plow + 1;
				high[topIndex] = topHigh;
			}
		}
	}
1
0
分享到:
评论

相关推荐

    python面试题目-python-python经典面试题目-Python语言的基本概念-常用的功能和特性-编程范式-面试题目

    以上只是部分知识点,Python还有更多如JSON处理、GIL、数据排序、函数式编程、网络编程、虚拟环境、数据库操作、迭代器协议、正则表达式匹配、垃圾回收、上下文管理器等丰富内容。深入理解和掌握这些知识,能让你在...

    面试题目-大数据量海量数据处理.pdf

    这些面试题目聚焦于大数据量和海量数据的处理,涵盖了各种挑战,包括数据过滤、去重、排序、频率统计和热门元素提取。以下是对这些题目的详细解析和相关知识点: 1. **URL共现问题**:这是一个典型的集合交集问题,...

    Python sort面试题目

    - 其他常见排序算法如冒泡排序、选择排序、插入排序的时间复杂度为 **O(n^2)**,而归并排序和快速排序的平均时间复杂度也为 **O(n log n)**。 **应用场景**: - 当数据量较小或对稳定性有要求时,可以选择时间...

    (吐血推荐)暴多面试技巧资料以及面试题目和应对方法

    - 算法题目:如快速排序、归并排序、Dijkstra算法、KMP字符串匹配等。 - 设计模式:实现单例模式、工厂模式、观察者模式等,讨论其适用场景和优缺点。 - C++特性:如模板、RAII(Resource Acquisition Is ...

    MoreWindows白话经典算法之七大排序

    冒泡排序、插入排序、选择排序、希尔排序、归并排序、快速排序和堆排序是七大基础的计算机算法,它们各自有着不同的特点和适用...在面试中,排序算法是常见的面试题目,考察应聘者的基础知识掌握程度及问题解决能力。

    java面试题目集锦

    - 算法:排序(冒泡、选择、插入、快速、归并等)、查找(顺序、二分等)。 3. **多线程** - 线程的创建:通过`Thread`类的子类化或实现`Runnable`接口。 - 同步机制:掌握`synchronized`关键字和`wait()`, `...

    2014-2016java面试题目

    排序算法(冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序)和查找算法(顺序查找、二分查找)是面试中的常见考点。 3. **多线程**:Java提供了内置的多线程支持,面试中可能涉及到线程的创建(Thread...

    .net/C#软件工程师面试题目汇总

    《.NET/C#软件工程师面试题目汇总》 在.NET/C#软件工程师的面试过程中,面试官通常会围绕以下几个核心领域来考察候选人的专业能力:基础知识、C#编程语言、.NET框架、数据库交互、设计模式与架构、软件工程实践以及...

    101算法面试题目

    《101算法面试题目》是一份专门为求职者准备的英文资源,涵盖了101个算法相关的面试问题,旨在帮助应聘者提升在技术面试中的表现。算法是计算机科学的基础,对于任何想要进入IT行业的程序员或者工程师来说,掌握良好...

    小米运维面试题目(1).docx

    ### 小米运维面试知识点详解 #### 第一部分:Linux基础 **题目1:批量下载图片文件及筛选** - **知识点1:使用wget批量下载文件** - 在Linux环境下,可以利用`wget`命令来实现对指定URL的批量下载。例如,可以...

    程序员面试宝典1-16

    排序算法(如冒泡、选择、插入、快速、归并排序)和查找算法(线性、二分、哈希查找)也是面试常考题目。 3. **计算机网络**:理解TCP/IP协议模型,包括应用层、传输层、网络层和数据链路层的功能。HTTP、FTP、DNS...

    Intel的笔试和面试题目

    ### Intel的笔试和面试题目解析 #### 智力题解析 1. **相遇轮船问题**:这个问题实际上是一个经典的数学逻辑题。由于两艘轮船分别从两个地点出发,相向而行,假设今天中午从勒阿佛开出的船会在7天后到达纽约,而在...

    算法大全-面试题-链表-栈-二叉树-数据结构

    - **排序链表**:可以使用归并排序或快速排序的变体来实现链表排序。 - **删除重复元素**:通常使用哈希集合来辅助,记录已出现过的元素,遇到重复就删除。 这些链表操作是面试中常见的问题,对于程序员来说,...

    java程序员面试笔试宝典-何昊

    12. **算法与数据结构**:掌握常见的排序算法(冒泡、选择、插入、快速、归并、堆排序等)、查找算法(二分查找、哈希查找),以及链表、树、图、栈、队列等数据结构。 13. **测试与调试**:单元测试的重要性,...

    百度阿里巴巴腾讯华为小米笔试面试题目总结

    这些压缩包文件集合了中国顶级互联网公司,包括百度、阿里巴巴、腾讯、华为和小米等企业的笔试及面试题目,是求职者准备社招和校招的重要参考资料。这些题目涵盖了多个技术领域,旨在测试候选人的综合素质,特别是...

    java.c++面试题目

    在IT行业的面试中,Java和C++作为两种广泛使用的编程语言,经常出现在技术面试和笔试环节。对于求职者来说,掌握这两门语言的核心概念、语法特性以及编程实践是至关重要的。下面,我们将深入探讨Java和C++面试中可能...

    java笔试面试题目

    Java笔试面试题目是Java开发者在求职过程中必须面对的重要环节,它涵盖了广泛的Java编程知识,包括但不限于基础语法、数据结构、算法、多线程、集合框架、JVM优化、设计模式等。下面将针对这些关键领域进行详细的...

    java超有用的面试题目

    在Java 7及之前版本,对于基本类型,它采用的是快速排序算法;对于对象类型,则采用归并排序。到了Java 8,`Arrays.sort()` 对于基本类型的排序算法被调整为TimSort,这是一种结合了插入排序和归并排序的混合排序...

    常见的笔试和面试题目,涵盖了数据结构、算法、操作系统、网络、数据库.pdf

    ### 常见的笔试和面试题目解析 #### 数据结构与算法 1. **数组与字符串** - **反转一个字符串**: - 字符串是不可变对象,在大多数编程语言中,通常需要借助额外的数据结构(如数组或列表)来实现字符串的反转。...

Global site tag (gtag.js) - Google Analytics