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;
}
}
}
分享到:
相关推荐
以上只是部分知识点,Python还有更多如JSON处理、GIL、数据排序、函数式编程、网络编程、虚拟环境、数据库操作、迭代器协议、正则表达式匹配、垃圾回收、上下文管理器等丰富内容。深入理解和掌握这些知识,能让你在...
这些面试题目聚焦于大数据量和海量数据的处理,涵盖了各种挑战,包括数据过滤、去重、排序、频率统计和热门元素提取。以下是对这些题目的详细解析和相关知识点: 1. **URL共现问题**:这是一个典型的集合交集问题,...
- 其他常见排序算法如冒泡排序、选择排序、插入排序的时间复杂度为 **O(n^2)**,而归并排序和快速排序的平均时间复杂度也为 **O(n log n)**。 **应用场景**: - 当数据量较小或对稳定性有要求时,可以选择时间...
- 算法题目:如快速排序、归并排序、Dijkstra算法、KMP字符串匹配等。 - 设计模式:实现单例模式、工厂模式、观察者模式等,讨论其适用场景和优缺点。 - C++特性:如模板、RAII(Resource Acquisition Is ...
冒泡排序、插入排序、选择排序、希尔排序、归并排序、快速排序和堆排序是七大基础的计算机算法,它们各自有着不同的特点和适用...在面试中,排序算法是常见的面试题目,考察应聘者的基础知识掌握程度及问题解决能力。
- 算法:排序(冒泡、选择、插入、快速、归并等)、查找(顺序、二分等)。 3. **多线程** - 线程的创建:通过`Thread`类的子类化或实现`Runnable`接口。 - 同步机制:掌握`synchronized`关键字和`wait()`, `...
排序算法(冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序)和查找算法(顺序查找、二分查找)是面试中的常见考点。 3. **多线程**:Java提供了内置的多线程支持,面试中可能涉及到线程的创建(Thread...
《.NET/C#软件工程师面试题目汇总》 在.NET/C#软件工程师的面试过程中,面试官通常会围绕以下几个核心领域来考察候选人的专业能力:基础知识、C#编程语言、.NET框架、数据库交互、设计模式与架构、软件工程实践以及...
《101算法面试题目》是一份专门为求职者准备的英文资源,涵盖了101个算法相关的面试问题,旨在帮助应聘者提升在技术面试中的表现。算法是计算机科学的基础,对于任何想要进入IT行业的程序员或者工程师来说,掌握良好...
### 小米运维面试知识点详解 #### 第一部分:Linux基础 **题目1:批量下载图片文件及筛选** - **知识点1:使用wget批量下载文件** - 在Linux环境下,可以利用`wget`命令来实现对指定URL的批量下载。例如,可以...
排序算法(如冒泡、选择、插入、快速、归并排序)和查找算法(线性、二分、哈希查找)也是面试常考题目。 3. **计算机网络**:理解TCP/IP协议模型,包括应用层、传输层、网络层和数据链路层的功能。HTTP、FTP、DNS...
### Intel的笔试和面试题目解析 #### 智力题解析 1. **相遇轮船问题**:这个问题实际上是一个经典的数学逻辑题。由于两艘轮船分别从两个地点出发,相向而行,假设今天中午从勒阿佛开出的船会在7天后到达纽约,而在...
- **排序链表**:可以使用归并排序或快速排序的变体来实现链表排序。 - **删除重复元素**:通常使用哈希集合来辅助,记录已出现过的元素,遇到重复就删除。 这些链表操作是面试中常见的问题,对于程序员来说,...
12. **算法与数据结构**:掌握常见的排序算法(冒泡、选择、插入、快速、归并、堆排序等)、查找算法(二分查找、哈希查找),以及链表、树、图、栈、队列等数据结构。 13. **测试与调试**:单元测试的重要性,...
这些压缩包文件集合了中国顶级互联网公司,包括百度、阿里巴巴、腾讯、华为和小米等企业的笔试及面试题目,是求职者准备社招和校招的重要参考资料。这些题目涵盖了多个技术领域,旨在测试候选人的综合素质,特别是...
在IT行业的面试中,Java和C++作为两种广泛使用的编程语言,经常出现在技术面试和笔试环节。对于求职者来说,掌握这两门语言的核心概念、语法特性以及编程实践是至关重要的。下面,我们将深入探讨Java和C++面试中可能...
Java笔试面试题目是Java开发者在求职过程中必须面对的重要环节,它涵盖了广泛的Java编程知识,包括但不限于基础语法、数据结构、算法、多线程、集合框架、JVM优化、设计模式等。下面将针对这些关键领域进行详细的...
在Java 7及之前版本,对于基本类型,它采用的是快速排序算法;对于对象类型,则采用归并排序。到了Java 8,`Arrays.sort()` 对于基本类型的排序算法被调整为TimSort,这是一种结合了插入排序和归并排序的混合排序...
### 常见的笔试和面试题目解析 #### 数据结构与算法 1. **数组与字符串** - **反转一个字符串**: - 字符串是不可变对象,在大多数编程语言中,通常需要借助额外的数据结构(如数组或列表)来实现字符串的反转。...