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

JavaScript010

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调用CS里的方法有很多 我用一种简单的方法 如下 有需要的朋友可以参考一下  

CS里

复制代码 代码如下: public string test()   {      return "Hello World"   } 

aspx 页面

复制代码 代码如下: <xmlns=" <head runat="server">      <title>无标题页</title>      <mce:script type=text/javascript ><!        var demo=function(){         var b= "<%=test() %>"         alert(b)         }  // ></mce:script>   </head>  <body>      <form id="form " runat="server">      <div>          <input type=button id="id " onclick="demo()" value="JS调用CS" />      </div>      </form>  </body>  </> 

上面的是不带参数的 要是后台CS里方法带参数就要注意了 CS:

复制代码 代码如下: public string test(string a)   {      return a   } 

aspx:

复制代码 代码如下: <xmlns=" <head runat="server">      <title>无标题页</title>      <mce:script type=text/javascript ><!        var demo=function(){         var a="Hello World"         var b= <%=test(" +a+ ") %>//这里一定注意单引号和双引号的使用!!!!!          alert(b)         }  // ></mce:script>   </head>  <body>      <form id="form " runat="server">      <div>          <input type=button id="id " onclick="demo()" value="JS调用CS" />      </div>      </form>  </body>  </>  lishixinzhi/Article/program/Java/JSP/201311/20337

如下所示:

复制代码

代码如下:

if

(new

Date(strSD.replace(/\-/g,

'\/'))

>

new

Date(strED.replace(/\-/g,

'\/')))

{

//开始时间大于了结束时间

alert("时间选择有误!开始日期必须小于或者等于结束时期!")

return

false

}