JS实现随机化快速排序的实例代码

JavaScript011

JS实现随机化快速排序的实例代码,第1张

算法的平均时间复杂度为O(nlogn)。但是当输入是已经排序的数组或几乎排好序的输入，时间复杂度却为O(n^2)。为解决这一问题并保证平均时间复杂度为O(nlogn)的方法是引入预处理步骤，它惟一的目的是改变元素的顺序使之随机排序。这种预处理步骤可在O(n)时间内运行。能够起到同样作用的另一种简单方法是在算法中引入一个随机元素，这可以通过随机地选择拆分元素的主元来实现。随机选择主元的结果放宽了关于输入元素的所有排列的可能性相同的步骤。引入这一步来修正原先的快速排序，可得到下面所示的随机化快速排序。新算法只是在区间[low…high]中一致随机地选择一个索引v，并将A[v]和A[low]交换，然后按照原来的快速排序算法继续。这里，parseInt(Math.random()*(high-low+1)

+

low)返回一个在low和high之间的数。

复制代码

代码如下:

/****************************************

算法：split

输入：数组A[low...high]

输出：

1.若有必要，输出按上述描述的重新排列的数组A

2.划分元素A[low]的新位置w

****************************************/

function

split(array,

low,

high)

{

var

i

=

low

var

x

=

array[low]

for(var

j

=

low

+

1

j

<=

high

j++)

{

if(array[j]

<=

x)

{

i

++

if(i

!=

j)

{

var

temp

=

array[i]

array[i]

=

array[j]

array[j]

=

temp

}

}

}

temp

=

array[low]

array[low]

=

array[i]

array[i]

=

temp

return

i

}

/****************************************

算法：rquicksort

输入：A[0...n-1]

输出：按非降序排列数组A[0...n-1]

rquicksort(A,

0,

n-1)

****************************************/

function

rquicksort(array,

low,

high)

{

if(low

<

high)

{

/******随机化拆分元素的主元*******/

var

v

=

parseInt(Math.random()*(high-low+1)

+

low)

var

tmp

=

array[low]

array[low]

=

array[v]

array[v]

=

tmp

/******随机化拆分元素的主元*******/

var

w

=

split(array,

low,

high)

rquicksort(array,

low,

w

-1)

rquicksort(array,

w

+1,

high)

return

array

}

}

var

array

=

[33,

22,

11,

88,

23,

32]

array

=

rquicksort(array,

0,

array.length-1)

console.log(array)

本文实例为大家分享了js抽奖程序的编写代码，以及编写注意事项，感兴趣的小伙伴们可以参考一下

代码：

<!DOCTYPE

html>

<html

lang="en">

<head>

<meta

charset="UTF-8">

<title>简单抽奖（可用键盘）</title>

<style>

*{margin:0padding:0}

.box{width:

400pxheight:

300pxmargin:50px

autobackground:

red}

.title{color:

#ffffont-size:

30pxfont-weight:700pxpadding:

50px

0text-align:

centerheight:40px}

.btm{text-align:

centerpadding:20px

0}

.btm

a{display:

inline-blockwidth:

120pxheight:60pxline-height:

60pxbackground:

#FEF097margin:0

10pxtext-decoration:

none}

</style>

<script>

var

data=['Iphone','Ipad','笔记本','相机','谢谢参与','充值卡','购物券'],

timer=null,//定时器

flag=0//阻止多次回车

window.onload=function(){

var

play=document.getElementById('play'),

stop=document.getElementById('stop')

//

开始抽奖

play.onclick=playFun

stop.onclick=stopFun

//

键盘事件

document.onkeyup=function(event){

event

=

event

||

window.event

//

回车键的code值：13

if(event.keyCode==13){

if(flag==0){

playFun()

flag=1

}else{

stopFun()

flag=0

}

}

}

function

playFun(){

var

title=document.getElementById('title')

var

play=document.getElementById('play')

clearInterval(timer)

timer=setInterval(function(){

var

random=Math.floor(Math.random()*data.length)

title.innerHTML=data[random]

},60)

play.style.background='#999'

}

function

stopFun(){

clearInterval(timer)

var

play=document.getElementById('play')

play.style.background='#FEF097'

}

}

</script>

</head>

<body>

<div

class="box">

<div

class="title"

id="title">淘家趣抽奖</div>

<div

class="btm">

<a

href="javascript:"

id="play">开始</a>

<a

href="javascript:"

id="stop">停止</a>

</div>

</div>

</body>

</html>

注意点：

1.随机数，取数组的其中一个；取0-n之间：Math.random()*(n+1)

2.定时器，开始抽奖时要停止前面的一次抽奖，不然会定时器重叠

3.按键操作，要判断是抽奖进行中，还是未开始，所有设置了变量

flag

想要学习更多关于javascript抽奖功能，请参考此专题：javascript实现抽奖功能

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持脚本之家。