OT有谁知道迭代快速排序？ [英] OT anyone know iterative quicksort?

问题描述

只需将以下内容粘贴到记事本中，称之为iqsort.html双击它

并且您的IE浏览器将运行它。 （整洁！通用编程

语言，我们都可以运行！）


它从排序程序中脱落。我得到了javascript quicksort

运行，它很快但是在大约5000

元素后它会出现堆栈溢出。


Am我将数组作为参数传递好吗？我认为javascript

默认是传递指针，可以是全局的。


Herc



< script language =" javascript">


l = 0

r = 0

stack = 0

卡住=新数组

ARRAY_MAX = 10

函数PUSH（l，r）{

stack ++

卡住[stack] = l

stack ++

卡住[stack] = r

}

函数POP（l，r）{

r =卡住[stack]

stack--

l =卡住[stack]

stack--

}


函数main（）

{

i = 0

array1 = new Array

array2 = new Array


alert（"数组由以下组成价值）


for（i = 0; i< ARRAY_MAX; i ++）{

array1 [i] = parseInt（Math.random（1）* 100）

array2 [i] = array1 [i]

}


alert（array1 [1] +"" ; + array1 [2] +&qu OT; " + array1 [3] +" " +

array1 [4] +" " + array1 [5]）


iterative_qsort（array2,0，ARRAY_MAX-1）;


alert（array2 [1] +" " + array2 [2] +"" + array2 [3] +"" +

array2 [4] +"" + array2 [5]）


}

函数iterative_qsort（tarray，left，right）

{


i = 0

last = 0

temp = 0

position = 0

if（left< right ）$

/ *将-1'推入堆栈，作为我们已经达到谷底的

未来的信号。 * /


PUSH（-1，-1）;

PUSH（左，右）;


完成= false

while（！完成）{


POP（左，右）;


if（b） （左== -1）&&（右== -1））{

完成= true

}

else {


if（left< right）{

position = parseInt（（left + right）/ 2）


temp = tarray [left];

tarray [left] = tarray [position];

tarray [position] = temp;


last = left;


for（i = left + 1; i< = right; i ++）

if（tarray [i]< ; tarray [left]）{

last ++;

temp = tarray [last];

tarray [last] = array [i];

tarray [i] = temp;

}


temp = tarray [left];

tarray [left] = tarray [last];

tarray [last] = temp;


PUSH（left，last-1）;

PUSH（最后+ 1，右）;

}

}

}

}

}


main（）


< / script>

解决方案

建议阅读关于quicksort的这篇（内容翔实的）文章
http://www.angelfire.com/pq/jamesbar...rtIsBroken.htm

讨论通常与

快速排序，以及如何减轻它们。


这是关于一般排序的好系列的一部分。
http://www.angelfire.com/pq/jamesbar...ngOverview.htm


此外，我认为交叉发布被视为不良形式.. :-)

HERC777写道：

只需将下面的内容粘贴到记事本中，称之为iqsort.html双击它
并且您的IE浏览器将运行它。 （整洁！一种通用编程语言我们都可以运行！）

它从排序过程中消失了。我得到了javascript quicksort
运行，它很快但是在大约5000个
元素之后会出现堆栈溢出。

我是否将数组作为参数传递好？我认为javascript
默认是传递指针，可以是全局的。

< script language =" javascript">

语言属性已折旧，类型是必需的。


< script type =" text / javascript"> ;


好​​的，你有我。这个''Quicksort'有什么意义？我根本不工作

，我无法调试它。下面是一个脚本，

使用20行代码生成任意长度的数组，任何

范围，然后按升序或降序排序。用

测试最多100,000个术语。


脚本改编自：

< URL ：http：//www.coedu.usf.edu/wwwprog/sort_demo.html>


顺便说一下，使用上面的链接，''quicksort''需要超过5,000

比较并在我的旧笔记本电脑上花了近20秒来分类100

数字。 jsSort算法花了0.05秒在Firefox中做了1000

的数字，在IE中用了0.15秒。


所以问题仍然是：什么是快速排行的点除了

显示算法的速度有多慢？


-

Fred


< script type =" text / javascript">

function genArray（n，r）{

var a = [];

while（n--）{a [n] = Math.floor（Math.random（）* r）}

返回a;

}

函数doSort（n，d，r）{

var z = genArray（n，r）;

var start = new Date（）。getTime（）;

（''''= = d）？ z.sort（compA）：z.sort（compD）;

var end = new Date（）。getTime（）;

document.getElementById（''result' '）.innerHTML =

''花了''+（结束 - 开始）+''毫秒< br>''

+ z.join（''， ''）;

}

函数compD（a，b）{

return（（a< b）？1 :(（ a> b）？ - 1：0））;

}

函数compA（a，b）{

return（（a） < b）？ - 1：（（a> b）？1：0））;

}

< / script>

< form action ="">

< input type =" text"大小= QUOT; 10" name =" num">术语数< br>

< input type =" text"大小= QUOT; 10" name =" range">数字范围< br>

< input type =" button" value ="升序排序" onclick ="

doSort（this.form.num.value，'a''，this.form.range.val ue）;

">

< input type =" button" value =" Sort descending" onclick ="

doSort（this.form.num.value，'d''，this.form.range.val ue）;

">

< / form>< br>

< span id =" result">结果在此处< / span>

>建议阅读关于quicksort

http： //www.angelfire.com/pq/ja mesbarbetti / articles / sorting / 0

01_Quicks ...


这篇文章的作者似乎没有意识到Bentley-McIlroy

3-way quicksort。鉴于这是Java中的现代quicksort

实现（对于原始类型）和C（qsort），

这似乎是一个非常严重的遗漏。像许多排序

算法一样，quicksort有一些积极的和一些消极的

功能。如果你想学习排序，请阅读Sedgewick的X或Knuth中的
算法。

just paste the below into notepad, call it iqsort.html double click it
and your IE browser will run it. (neat! a universal programming
language we can all run!)

it falls out from the sort procedure. I got javascript quicksort
running, it''s quick but it gets stack overflow after about 5000
elements.

Am I passing the array as a parameter alright? I think javascript
default is to pass pointers, that can be global.

Herc


<script language = "javascript">

l=0
r=0
stack=0
stuck = new Array
ARRAY_MAX = 10

function PUSH(l, r) {
stack++
stuck[stack] = l
stack++
stuck[stack] = r
}
function POP(l, r) {
r = stuck[stack]
stack--
l = stuck[stack]
stack--
}

function main()
{
i = 0
array1 = new Array
array2 = new Array

alert("The array is composed of the following values")

for(i=0; i<ARRAY_MAX; i++) {
array1[i] = parseInt(Math.random(1) * 100)
array2[i] = array1[i]
}

alert (array1[1] + " " + array1[2] + " " + array1[3] + " " +
array1[4] + " " + array1[5])

iterative_qsort(array2, 0, ARRAY_MAX-1);

alert (array2[1] + " " + array2[2] + " " + array2[3] + " " +
array2[4] + " " + array2[5])

}
function iterative_qsort(tarray, left, right)
{

i=0
last=0
temp=0
position=0

if(left < right) {

/* Push -1''s onto the stack as a signal to us in the
future that we''ve reached the bottom. */

PUSH(-1, -1);
PUSH(left, right);

finished = false
while (!finished) {

POP(left, right);

if((left == -1) && (right == -1)){
finished = true
}
else {

if(left < right) {
position = parseInt((left + right) / 2)

temp = tarray[left];
tarray[left] = tarray[position];
tarray[position] = temp;

last = left;

for(i=left+1; i<=right; i++)
if(tarray[i] < tarray[left]) {
last++;
temp = tarray[last];
tarray[last] = array[i];
tarray[i] = temp;
}

temp = tarray[left];
tarray[left] = tarray[last];
tarray[last] = temp;

PUSH(left, last-1);
PUSH(last+1, right);
}
}
}
}
}

main()

</script>

解决方案

Suggest reading this (very informative) article on quicksort
http://www.angelfire.com/pq/jamesbar...rtIsBroken.htm
Which discusses the stack overflow problems often associated with
quicksorts, and how to mitigate them.

It''s part of this good series on sorting in general.
http://www.angelfire.com/pq/jamesbar...ngOverview.htm

Also, cross-posting I believe is considered bad form.. :-)

HERC777 wrote:

just paste the below into notepad, call it iqsort.html double click it
and your IE browser will run it. (neat! a universal programming
language we can all run!)

it falls out from the sort procedure. I got javascript quicksort
running, it''s quick but it gets stack overflow after about 5000
elements.

Am I passing the array as a parameter alright? I think javascript
default is to pass pointers, that can be global.

Herc


<script language = "javascript">

The language attributes is depreciated, type is required.

<script type="text/javascript">

Ok, you got me. What is the point of this ''Quicksort''? I didn''t work
at all, I could not be bothered to debug it. Below is a script that
uses 20 lines of code to generate an array of any length, with any
range, then sort it either ascending or descending. Tested it with
up to 100,000 terms.

The script is adapted from here:

<URL:http://www.coedu.usf.edu/wwwprog/sort_demo.html>

Incidentally, using the above link, a ''quicksort'' requires over 5,000
compares and took nearly 20 seconds on my old laptop to sort 100
numbers. The ''jsSort'' algorithm took 0.05 seconds to do 1,000
numbers in Firefox and 0.15 seconds in IE.

So the question remains: what is the point of a ''quicksort'' except to
show how slow the algorithm is?

--
Fred

<script type="text/javascript">
function genArray(n,r) {
var a = [];
while(n--) {a[n] = Math.floor(Math.random() * r)}
return a;
}
function doSort(n,d,r) {
var z = genArray(n,r);
var start = new Date().getTime();
(''a'' == d)? z.sort(compA): z.sort(compD);
var end = new Date().getTime();
document.getElementById(''result'').innerHTML =
''That took '' + (end-start) + '' milliseconds<br>''
+ z.join('', '');
}
function compD(a,b) {
return ((a < b) ? 1 : ((a > b) ? -1 : 0));
}
function compA(a,b) {
return ((a < b) ? -1 : ((a > b) ? 1 : 0));
}
</script>
<form action="">
<input type="text" size="10" name="num">Number of terms<br>
<input type="text" size="10" name="range">Range of numbers<br>
<input type="button" value="Sort ascending" onclick="
doSort(this.form.num.value,''a'',this.form.range.val ue);
">
<input type="button" value="Sort descending" onclick="
doSort(this.form.num.value,''d'',this.form.range.val ue);
">
</form><br>
<span id="result">result goes here</span>

> Suggest reading this (very informative) article on quicksort

http://www.angelfire.com/pq/ja mesbarbetti/articles/sorting/0

01_Quicks...

The author of this article seems unaware of Bentley-McIlroy
3-way quicksort. Given that this is the modern quicksort
implementation in Java (for primitive types) and C (qsort),
this seems like a pretty serious omission. Like many sorting
algorithms, quicksort has some positive and some negative
features. If you want to learn about sorting, read Sedgewick''s
Algorithms in X or Knuth.

这篇关于OT有谁知道迭代快速排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！