这两天用js写了一个快速排序的算法,希望以后或者大家会用得着.
<
html
>
<
head
>
<
script language
=
"
JavaScript
"
>
<!--
/**/
/*
名称:快速排序算法
*作者:梅雪香(meixx)
*时间:2006-9-22
*/
//
产生随机数数组
Number.prototype.RandArr
=
function
()
{
if
(
this
<
1
)
return
null
;
var
ar
=
[];
for
(
var
i
=
0
;i
<
this
;i
++
)
ar.push(Math.floor(Math.random()
*
10
*
this
));
return
ar;
}
//
选择拆分数组的种子所在的下标
Array.prototype.selMiddleValIdx
=
function
(bIndex, eIndex)
{
var
mid
=
Math.floor((eIndex
+
bIndex)
/
2
)
var
arr
=
[
this
[bIndex],
this
[mid],
this
[eIndex]];
var
arIndex
=
[bIndex,mid,eIndex];
for
(
var
i
=
0
;i
<
2
;i
++
)
for
(
var
j
=
i
+
1
;j
<
3
;j
++
)
if
(arr[i]
>
arr[j])
{
arr.swap(i,j);
arIndex.swap(i,j);
}
return
arIndex[
1
];
}
//
按index交换数组中的两个元素
Array.prototype.swap
=
function
(a, b)
{
var
tmp
=
this
[a];
this
[a]
=
this
[b];
this
[b]
=
tmp;
return
this
;
}
//
对数组[bIndex:eIndex]进行快速排序
Array.prototype.QsSort
=
function
(bIndex, eIndex)
{
if
(bIndex
==
null
) bIndex
=
0
;
if
(eIndex
==
null
) eIndex
=
this
.length
-
1
;
if
(bIndex
>=
eIndex)
return
this
;
var
pivotIdx
=
this
.selMiddleValIdx(bIndex, eIndex);
var
pivot
=
this
[pivotIdx];
this
.swap(pivotIdx,bIndex);
var
pLeft
=
bIndex
+
1
, pRight
=
eIndex;
while
(
true
)
{
while
(
this
[pLeft]
<=
pivot
&&
pLeft
<=
eIndex)
{
pLeft
++
;
}
while
(
this
[pRight]
>
pivot
&&
pRight
>
bIndex)
{
pRight
--
;
}
if
(pLeft
>=
pRight)
break
;
this
.swap(pLeft,pRight);
}
this
[bIndex]
=
this
[pRight];
this
[pRight]
=
pivot;
this
.QsSort(bIndex,pRight
-
1
);
this
.QsSort(pRight
+
1
,eIndex);
return
this
;
}
//
-->
</
script
>
<
script language
=
"
JavaScript
"
>
<!--
var
dw
=
document.write;
var
ge
=
document.getElementById;
var
arr
=
[];
var
isSort
=
false
;
//
是否排好序的标志
//
产生随机数组
function
makeNum()
{
isSort
=
false
;
var
num
=
parseInt(ge(
"
txtRandSeed
"
).value,
10
);
var
div
=
ge(
"
divRslt
"
);
if
(
!
isNaN(num)
&&
num
>
0
)
{
arr
=
num.RandArr();
div.innerHTML
+=
arr.join(
"
"
)
+
"
<br>
"
;
}
}
//
对随机数组进行排序
function
QuickSort()
{
if
(isSort
||
arr.length
<
1
)
return
;
var
ar
=
arr.QsSort();
var
div
=
ge(
"
divRslt
"
);
div.innerHTML
+=
"
<span style='color:blue'>
"
+
ar.join(
"
"
)
+
"
<a href=# onclick=check(this)>验证</a></span><br>
"
;
isSort
=
true
;
}
//
自动产生随机数组 自动排序
function
autoTest()
{
var
num
=
parseInt(ge(
"
txtTimes
"
).value,
10
);
if
(
!
isNaN(num)
&&
num
>
0
)
{
for
(
var
i
=
0
;i
<
num;i
++
)
{
ge(
"
btnMake
"
).click();
ge(
"
btnSort
"
).click();
}
}
}
function
check(lnkObj)
{
var
arr
=
lnkObj.parentNode.innerText.split(
"
"
);
arr
=
arr.pop();
var
isRight
=
true
;
var
len
=
arr.length;
for
(
var
i
=
0
;i
<
len
-
1
;i
++
)
{
if
(arr[i]
>
arr[i
+
1
])
{
isRight
=
false
;
break
;
}
}
var
str
=
isRight
?
"
排序正确!
"
:
"
排序不正确!\n请将测试用例反馈给:wy_hd@163.com
"
;
alert(str);
}
//
-->
</
script
>
</
head
>
<
body style
=
"
font-size:12px
"
>
请输入产生随机数的个数(正整数):
<
input type
=
"
text
"
id
=
"
txtRandSeed
"
value
=
"
20
"
>
<
input type
=
"
button
"
id
=
"
btnMake
"
value
=
"
产生随机数
"
onclick
=
"
makeNum();
"
>
<
input type
=
"
button
"
id
=
"
btnSort
"
value
=
"
随机数排序
"
onclick
=
"
QuickSort()
"
>
<
br
>
请输入自动测试的次数(正整数):
<
input type
=
"
text
"
id
=
"
txtTimes
"
value
=
"
5
"
>
<
input type
=
"
button
"
value
=
"
自动测试
"
onclick
=
"
autoTest();
"
>
<
div style
=
"
width:100%
"
id
=
"
divRslt
"
></
div
>
</
body
>
</
html
>
posted on 2006-09-24 01:50
梅雪香 阅读(1327)
评论(0) 编辑 收藏