`
yiminghe
  • 浏览: 1466600 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

Array.prototype.sort 稳定性问题

prototypeChrome算法IEFirefox 
阅读更多

 

引例

 

首先看一段代码：

 

<html><head><title>sort稳定性</title></head><body>

<h1>Non-stable Sort</h1>

<ol>
<script type="text/javascript">
function Pair(_x, _y)
{
    this.x = _x;
    this.y = _y;
}
function pairSort(a, b)
{
    return a.x - b.x;
}
var check = new Array(new Pair("1", "1"), new Pair("1", "2"),
                      new Pair("1", "3"), new Pair("1", "4"),
                      new Pair("2", "1"), new Pair("2", "2"),
                      new Pair("2", "3"), new Pair("2", "4"));
check.sort(pairSort);
for (var i = 0; i < check.length; ++i)
{
    document.write("<li>" + check[i].x + ", " + check[i].y + "</li>\n");
}
</script>

</ol>


</body></html>
 

会输出什么 ？

 

 

答案

 

 



ie ,firefox3 :


   1. 1, 1
   2. 1, 2
   3. 1, 3
   4. 1, 4
   5. 2, 1
   6. 2, 2
   7. 2, 3
   8. 2, 4

firefox 2:


   1. 1, 1
   2. 1, 2
   3. 1, 4
   4. 1, 3
   5. 2, 2
   6. 2, 1
   7. 2, 3
   8. 2, 4


chrome:

   1. 1, 2
   2. 1, 4
   3. 1, 3
   4. 1, 1
   5. 2, 2
   6. 2, 4
   7. 2, 3
   8. 2, 1

 

解释

 

  这就涉及到了 sort 各个浏览器是如何实现的 ，ecma没有规定 sort的具体实现 ，对稳定性也没有要求 :

 

15.4.4.11 Array.prototype.sort (comparefn)


The elements of this array are sorted. The sort is not necessarily stable
(that is, elements that compare equal do not necessarily remain in their
original order).

 

，而上述结果正是由于各个浏览器选择了不同的排序算法，各个算法的稳定性不同而导致了结果的差异。

 

  firefox2采取了不稳定的堆排序，firefox3采用了稳定的归并排序 ，ie 速度较慢，具体算法不明，可能为冒泡或者插入排序，而chrome则为了最大效率，采用了两种算法：


chrome use quick sort for a large dataset ( >22) ,and for a smaller dataset (<=22) chrome use insert sort but modified to use binary search to find insert point ,so traditionally insert sort is stable ,but chrome make it faster and unstable , in conclusion chrome’s sort is quick and unstable .

 

chrome的具体实现可以直接 document.writeln(Array.prototype.sort) 得到。

 

所以依赖于sort稳定性的应用需要自己写排序算法了，不要贸然使用系统的 Array.prototype.sort 。

 

理论基础：

 

什么是稳定性

 

就是两个元素具有相同的key，依据key排序后，相同key的两个元素的相对位置不变。

 

如 ： 


3 ,7 ,1(1) ,8 ,1(2),6
 

 

得到这样的排序才算是稳定的排序算法 ： 


1(1) , 1(2) ,3 ,6 ,7 ,8
 

 

 

 

各个算法稳定性列举：

 

冒泡排序：

 

基础为两两相邻元素比较，所以相同的两个相邻元素不会交换位置，所以稳定。

 

选择排序：


每次选择一个当前位置以后最小的一个，和当前位置交换，可能不稳定。

 

如： 


10(1)  , 9 , 10(2) ,1
 

 

第一轮过后： 


1  ,9 ,10(2) ,10(1)
 

 


插入排序：


在前面有序的基础上，再将当前元素插入到前面合适的位置，只有当前元素比前面序列中某个位置元素大时才能插入，稳定，

 

例如： 


10 , 1(1) ,1(2) ,2,5

->

1(1) ,10,1(2),2,5

->

1(1),1(2),10,2,5
 

 

 

快速排序：


同选择排序，类似有个长距离选择交换的过程，选择了一个pivot元素，则pivot和他应该在的位置的元素交换，可能破坏稳定性。

 

例如：

 

3        ,1(1) ,1(2) ,4

pivot

->

1(2) ,1(1) ,3,4
 

 

归并排序：

 

是两个相邻序列进行合并，合并时我们保证相同的元素出现时，前一个序列的元素出现在前面。

 

例如： 


1(1) ,10    +   1(2),9   = 1(1) ,1(2),9,10
 

 

 

 

基数排序：


从低位到高位，每一轮都是用稳定排序算法排序，则结果是稳定的。

 

希尔插入排序：

 

由于有gap的存在，可能插入元素中间会破坏稳定性。

 

例如：

 

| 3, 1(1), 1(2) |     |1(3) ,4 ,4|


->


| 1(3) ,1(1) ,1(2) |   | 3 ,4 ,4 |
 

 

堆排序：

 

父节点之间进行选择时，可能会破坏稳定性，

 

例如下面两堆

 

                    1

   10(1)                    9

11     10(2)



 

                      1

      9                       10(1)

11    10(2)
 

 

最终必有一堆最终结果会破坏稳定性，有兴趣可以自己推导。

 

2
顶
0
踩
分享到：
| min-width For ie6 与传统事件阻止
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    总结在前端排序中遇到的问题

    如果项目对排序稳定性有要求，如在某些场景下相同的元素需要保持原有的相对顺序，那么直接使用`Array.prototype.sort()`可能会出现问题。例如，在机动车牌照拍卖系统的例子中，当价格相同的情况下，需要按照提交时间...

    ES10的13个新特性示例(小结)

    7. Array.prototype.sort()方法的稳定性改进：ES10改变了Array.prototype.sort()方法的默认排序算法，以提供稳定的排序结果，这保证了具有相同排序键值的元素在排序前后保持相同的顺序。 8. Function.prototype....

    Vue infinite update loop的问题解决

    在Vue.js开发过程中，有时会出现“Vue infinite update loop”错误，这是由于组件渲染函数中存在一个无限循环导致的。...在日常开发中，我们应该养成良好的编程习惯，避免触发此类错误，以保证应用程序的稳定性和性能。

    深入理解js数组的sort排序.docx

    JavaScript中的`Array.prototype.sort()`方法是用于对数组进行排序的内置函数。这个方法可以在原地对数组进行排序，即不创建新的数组副本，而是直接修改原数组。在深入理解这个方法之前，我们需要知道它的工作原理和...

    JS数组排序方法实例分析

    了解如何使用try...catch语句、throw语句来控制错误的抛出和捕获，以及如何使用console对象、断点调试等技巧，对于提高开发效率和程序稳定性至关重要。 通过理解上述JavaScript数组排序及其他相关算法和技巧，读者...

    Javascript中的常见排序算法

    这种方法确保了稳定性，但需要额外的存储空间。 7. 堆排序（Heap Sort）： 堆排序是一种树形选择排序，利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的...

    DS-Algorithms:JS的数据结构和算法实践

    在JavaScript中，我们可以使用内置函数`Array.prototype.sort`进行排序，但要注意它默认使用的是不稳定排序。对于更高效或自定义的排序需求，可以编写自己的排序算法。二分查找适用于已排序的数组，可以大大提高查找...

    前端大厂最新面试题-sort.docx

    排序算法是计算机科学中基础且重要的概念，尤其在前端开发中，理解并能灵活运用排序算法...在实际工作中，还可以利用JavaScript内置的`Array.prototype.sort()`方法，但在某些特定场景下，自定义排序算法可能会更高效。

    js排序脚本

    `sort.js`可能保证了稳定性。 4. **多级排序**：支持对多个属性或条件进行排序，例如先按年龄排序，再按名字排序。 5. **回调支持**：允许用户传递额外的参数或配置，以适应不同场景。 6. **错误处理**：增加了对非...

    17 - 数组排序.rar

    JavaScript提供了内置的`Array.prototype.sort()`方法来对数组进行排序。这个方法接受一个可选的比较函数作为参数，用于自定义排序顺序。默认情况下，`sort()`会将数组元素转换为字符串并按照字典顺序进行排序，这...

    JS实现给数组对象排序的方法分析

    首先，`Array.prototype.sort()`方法是JavaScript中用于对数组进行原地排序的内置函数。它接受一个可选的比较函数作为参数，该函数定义了元素之间的比较规则。默认情况下，`sort()`方法会将所有元素转换为字符串，...

    JS排序插件

    在JavaScript中，数组的排序可以通过`Array.prototype.sort()`方法实现。这个方法可以接受一个比较函数作为参数，用于定义元素之间的排序规则。默认情况下，`sort()`会将数组元素转换为字符串，然后按照字典顺序进行...

    DSA阵列

    5. **排序与排序稳定性**：DSA阵列有时会需要内置排序功能，JavaScript提供了`Array.prototype.sort()`方法，但默认排序不稳定。为了实现稳定的排序，可以使用插入排序、冒泡排序或选择合适的外部排序算法。 6. **...

    前端开源库-arraysort

    4. **稳定性**：arraysort确保相同元素的相对顺序在排序后保持不变，这是稳定排序算法的一个关键特性。 **三、使用示例** ```javascript // 导入arraysort库 const arraySort = require('arraysort'); // 单个...

    javascript Table排序

    7. **兼容性问题**：考虑到老旧的浏览器，可能需要使用`Array.prototype.slice.call`将非数组的`NodeList`转换为数组，以便使用数组方法。 在实际应用中，还可以结合现代前端框架，如React或Vue，来更高效地管理...

    模拟javascript中的sort排序(简单实例)

    JavaScript中的`Array.prototype.sort()`方法是用于对数组的元素进行排序的一个强大工具。它可以直接对数组进行原地排序，也就是说，排序操作不会创建新的数组，而是直接修改原数组。但需要注意的是，`sort()`方法...

    前端开源库-arraysort.zip

    在JavaScript中，数组的排序可以通过`Array.prototype.sort()`方法来实现。这个方法接受一个可选的比较函数，根据这个函数返回值的正负决定元素的顺序。默认情况下，它会将所有元素转换为字符串并按照字典顺序进行...

    js前端排序

    首先，我们要了解JavaScript中的`Array.prototype.sort()`函数，这是最常用到的排序方法。该函数接受一个可选的比较函数作为参数，用于定义数组元素的排序顺序。默认情况下，`sort()`会按照字典顺序对字符串进行排序...

    table排序

    - `Array.prototype.sort()`函数是JavaScript中进行数组排序的基础，可以用于表格数据的排序。 - 自定义排序函数可以用来处理特定类型的排序逻辑，比如日期、数字或字符串。 3. **jQuery插件**： - 插件如...

Magicbox
Global site tag (gtag.js) - Google Analytics