這兩天用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
梅雪香 閱讀(1336)
評論(0) 編輯 收藏