JS数组排序

JavaScript021

JS数组排序,第1张

JS数组排序方法有两个: reverse() 和 sort() ,其中 reverse() 可将数组进行倒序,而 sort() 则可将数组项灵活地进行升序或降序排列。

可以看出, reverse() 会直接改变原数组,并且返回值也是倒序后的数组。

记得当年学C语言时,要学各种各样的排序算法,比如经典的冒泡排序法、二分排序法等,现在抛开这些算法不说,JS就自带原生的排序函数,用起来非常方便,它就是 sort() 。

可以看出, sort() 不传参数时会按升序方式对数组项进行排序,并且与 reverse() 一样既改变原数组,同时返回的也是排序后的数组。

我们再来看下一个例子:

这时你可能会说,不对呀,最终排序返回的不应该是 [8, 9, 16, 90] 吗?然鹅事实返回的却是 [16, 8, 9, 90] ,这到底是哪门子逻辑?

事实上, sort() 并不是按照数值进行排序,而是按字符串字母的ASCII码值进行比较排序的,所以当数组项为数字时, sort() 也会自动先将数字转换成字符串,然后再按字母比较的规则进行排序处理。

现在我们再回头看看前面两个例子。当 arr 为 [8,4,9,1] 时,数组每一项转换成字符串后进行排序的结果正好与数字排序结果相同;而当 arr 为 [8,90,9,16] 时,数组每一项转换成字符串后就得按顺序一位一位进行比较,比如升序排序时,“16”应该排在最前面,因为“16”的第一位是“1”,比“8”和“9”的ASCII码值都要小。

啰嗦了这么多,其实我们实际很少会使用这种排序方式,而更多的应该就是纯数字的排序。那么我们该如何正确地使用 sort() 来达到预期的排序效果呢?

接下来就来看看传参后的 sort() 能给我们怎样的精彩表现。

这个函数参数功能其实很简单,实际上就是告诉 sort() 排序方式到底是升序还是降序,我们还是来看具体实例吧~

这种用法的规则是,当 sort() 传入函数中的第一个参数a位于第二个参数b之前,则返回一个负数,相等则返回0,a位于b之后则返回正数。

比如,当要做升序排序时,我们需要想到前面的数肯定是要比后面的数小,所以传入的这个函数参数返回值应该要是个负数,因此函数参数返回 a - b 。

如果实在不好理解,我们可以干脆记下来, a - b 升序, b - a 降序,但是需要注意的是,如果按照这种记忆方式的话,函数括号内的两个参数 a 和 b 的书写顺序可不能颠倒哦~

js常用排序实现,参考代码如下

<script> 

Array.prototype.swap = function(i, j) 

var temp = this[i] 

this[i] = this[j] 

this[j] = temp 

Array.prototype.bubbleSort = function() 

for (var i = this.length - 1 i > 0 --i) 

for (var j = 0 j < i ++j) 

if (this[j] > this[j + 1]) this.swap(j, j + 1) 

Array.prototype.selectionSort = function() 

for (var i = 0 i < this.length ++i) 

var index = i 

for (var j = i + 1 j < this.length ++j) 

if (this[j] < this[index]) index = j 

this.swap(i, index) 

Array.prototype.insertionSort = function() 

for (var i = 1 i < this.length ++i) 

var j = i, value = this[i] 

while (j > 0 && this[j - 1] > value) 

this[j] = this[j - 1] 

--j 

this[j] = value 

Array.prototype.shellSort = function() 

for (var step = this.length >> 1 step > 0 step >>= 1) 

for (var i = 0 i < step ++i) 

for (var j = i + step j < this.length j += step) 

var k = j, value = this[j] 

while (k >= step && this[k - step] > value) 

this[k] = this[k - step] 

k -= step 

this[k] = value 

Array.prototype.quickSort = function(s, e) 

if (s == null) s = 0 

if (e == null) e = this.length - 1 

if (s >= e) return 

this.swap((s + e) >> 1, e) 

var index = s - 1 

for (var i = s i <= e ++i) 

if (this[i] <= this[e]) this.swap(i, ++index) 

this.quickSort(s, index - 1) 

this.quickSort(index + 1, e) 

Array.prototype.stackQuickSort = function() 

var stack = [0, this.length - 1] 

while (stack.length > 0) 

var e = stack.pop(), s = stack.pop() 

if (s >= e) continue 

this.swap((s + e) >> 1, e) 

var index = s - 1 

for (var i = s i <= e ++i) 

if (this[i] <= this[e]) this.swap(i, ++index) 

stack.push(s, index - 1, index + 1, e) 

Array.prototype.mergeSort = function(s, e, b) 

if (s == null) s = 0 

if (e == null) e = this.length - 1 

if (b == null) b = new Array(this.length) 

if (s >= e) return 

var m = (s + e) >> 1 

this.mergeSort(s, m, b) 

this.mergeSort(m + 1, e, b) 

for (var i = s, j = s, k = m + 1 i <= e ++i) 

b[i] = this[(k > e || j <= m && this[j] < this[k]) ? j++ : k++] 

for (var i = s i <= e ++i) this[i] = b[i] 

Array.prototype.heapSort = function() 

for (var i = 1 i < this.length ++i) 

for (var j = i, k = (j - 1) >> 1 k >= 0 j = k, k = (k - 1) >> 1) 

if (this[k] >= this[j]) break 

this.swap(j, k) 

for (var i = this.length - 1 i > 0 --i) 

this.swap(0, i) 

for (var j = 0, k = (j + 1) << 1 k <= i j = k, k = (k + 1) << 1) 

if (k == i || this[k] < this[k - 1]) --k 

if (this[k] <= this[j]) break 

this.swap(j, k) 

function generate() 

var max = parseInt(txtMax.value), count = parseInt(txtCount.value) 

if (isNaN(max) || isNaN(count)) 

alert("个数和最大值必须是一个整数") 

return 

var array = [] 

for (var i = 0 i < count ++i) array.push(Math.round(Math.random() * max)) 

txtInput.value = array.join("\n") 

txtOutput.value = "" 

function demo(type) 

var array = txtInput.value == "" ? [] : txtInput.value.replace().split("\n") 

for (var i = 0 i < array.length ++i) array[i] = parseInt(array[i]) 

var t1 = new Date() 

eval("array." + type + "Sort()") 

var t2 = new Date() 

lblTime.innerText = t2.valueOf() - t1.valueOf() 

txtOutput.value = array.join("\n") 

</script> 

<body onload=generate()> 

<table style="width:100%height:100%font-size:12pxfont-family:宋体"> 

<tr> 

<td align=right> 

<textarea id=txtInput readonly style="width:100pxheight:100%"></textarea> 

</td> 

<td width=150 align=center> 

随机数个数<input id=txtCount value=500 style="width:50px"><br><br> 

最大随机数<input id=txtMax value=1000 style="width:50px"><br><br> 

<button onclick=generate()>重新生成</button><br><br><br><br> 

耗时(毫秒):<label id=lblTime></label><br><br><br><br> 

<button onclick=demo("bubble")>冒泡排序</button><br><br> 

<button onclick=demo("selection")>选择排序</button><br><br> 

<button onclick=demo("insertion")>插入排序</button><br><br> 

<button onclick=demo("shell")>谢尔排序</button><br><br> 

<button onclick=demo("quick")>快速排序(递归)</button><br><br> 

<button onclick=demo("stackQuick")>快速排序(堆栈)</button><br><br> 

<button onclick=demo("merge")>归并排序</button><br><br> 

<button onclick=demo("heap")>堆排序</button><br><br> 

</td> 

<td align=left> 

<textarea id=txtOutput readonly style="width:100pxheight:100%"></textarea> 

</td> 

</tr> 

</table> 

</body>