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;
}
}
}
分享到:
相关推荐
快速排序的迭代版本源代码,在vs上调试通过。
什么是Python中的迭代器(Iterator)和可迭代对象(Iterable)? Python中如何处理异常(Exception)?列举一些常见的异常类型。 什么是Python中的命名空间(Namespace)和作用域(Scope)? Python中的深拷贝和...
用分治的思想模拟快速排序的迭代过程,快速排序平均运行时间可以和Heapsort媲美
用MATLAB语言进行Jacobi迭代法、Gauss-Seidel迭代法、SOR迭代法三种算法的计算
-迭代方法求解非线性方程组 -分片二次代数插值
c++迭代实现快速排序。随机产生一定范围内的随机数,进行快速排序。
平行平面镜--自在现模形成过程--Fox-Li数值迭代法 % 参数初始化 clc;clear; lambda=600e-9; %波长 L=100*lambda; %腔长 a=25*lambda; %腔镜线宽 k=2*pi/lambda; %波矢 x1=linspace(-a,a,1000); %取1000个点积分;...
n后问题--非递归迭代回溯.rar n后问题--非递归迭代回溯.rar n后问题--非递归迭代回溯.rar n后问题--非递归迭代回溯.rar n后问题--非递归迭代回溯.rar n后问题--非递归迭代回溯.rar
----icm---条件迭代算法,条件迭代算法基于MRF----ICM----
MATLAB源码集锦-基于Busacker-Gowan迭代算法最小费用流代码
雅克比迭代 数值计算方法 C++实现
有理模型辨识的两类新方法-----混合迭代与柔性最小二乘法.pdf
计算方法实验5--埃特金加速迭代算法 计算方法实验5--埃特金加速迭代算法 计算方法实验5--埃特金加速迭代算法
一部非常优秀的迭代法教程,深入编程者必备。
用C语言实现高斯-赛德尔迭代方法
计算方法实验5--埃特金加速迭代算法.cpp
鉴于基于Newton-Raphson(N-R)迭代的数字图像相关方法对迭代初值的敏感性问题,提出了一种基于N-R迭代与粒子群优化(PSO)算法的数字图像相关方法。该方法利用了PSO算法中的全局搜索能力与N-R迭代中的局部搜索能力...
matlab开发-使用gnewton方法迭代一个变量。程序迭代给定的与x轴相交的函数值。
结合人脸图像的对称性在非迭代双边二维主成分分析(NIB2DPCA)的基础上, 提出了对称非迭代双边二维主成分分析(SNIB2DPCA)的人脸识别方法。该方法引入镜像变换, 根据奇偶分解原理分别生成奇、偶对称样本, 用NIB2...
二维快速傅里叶变换-C语言-迭代法.c 实现方法为:C语言,先对每一行做傅里叶,再对结果的每一列做傅里叶