数据结构中的各种排序方法-JS实现

标签： 数据结构 排序 方法 | 发表时间：2011-10-28 15:02 | 作者：CareySon zhai
出处：http://www.cnblogs.com/

     新技术一直在不断变化，掌握一些基础是未来学习不断更新的技术的坚实基础。近来闲来无事,为了温习一下从前学的数据结构，将数据结构中的排序算法用JS实现了一遍，并在本文末尾处嵌入了DEMO。

 

简单排序

冒泡排序

     冒泡排序是最简单排序算法,时间复杂度为n的平方,代码如下:

        function bubbleSort(array) {
            for (var i = 0; i < array.length; i++) {
                for (var j = array.length; j > 0; j--) {
                    if (array[j] < array[j - 1]) {
                        var temp = array[j - 1];
                        array[j - 1] = array[j];
                        array[j] = temp;
                    }

                }
                /* 输出结果 */
                document.write("这是第 + (i + 1) + "次循环·，结果为:");
                for (var k = 0; k < array.length; k++) {
                    document.write(array[k] + ",");
                }
                document.write("<br />");
                /* 输出结果结束 */
            }
        }

 

直接插入排序

    直接插入排序也属于简单排序算法,时间复杂度也为n的平方，但性能略好于冒泡排序，代码如下:

        function insertSort(array) {
            var temp;
            for (var i = 1; i < array.length; i++) {
                var temp = array[i];
                for (var j = i; j > 0 && temp < array[j - 1]; j--) {
                    array[j] = array[j - 1];
                }
                array[j] = temp
                /* 输出结果 */
                document.write("第? + i + "遍排序的结果是:")
                for (var n = 0; n < array.length; n++) {
                    document.write(array[n] + ",");
                }

                document.write("<br />")
                /* 输出结果结束 */

            }
        }

 

选择排序

    选择排序也属于简单排序算法，时间复杂度也为n的平方，性能同样略微好于冒泡排序，代码如下:

        function selectSort(array) {
            var min, temp; ;
            for (var i = 0; i < array.length; i++) {
                min = i;
                for (var j = i + 1; j < array.length; j++) {
                    if (array[min] > array[j])
                        min = j;
                }
                if (min != i) {
                    temp = array[i];
                    array[i] = array[min];
                    array[min] = temp;
                }
                /* 输出结果 */
                document.write("第 + i + "遍排序的结果是:")
                for (var n = 0; n < array.length; n++) {
                    document.write(array[n] + ",");
                }

                document.write("<br />")
                /* 输出结果结束 */

            }
        }

 

复杂排序

 

希尔排序

     希尔排序是插入排序的升级，1959年希尔通过将简单排序中两两比较改为设置步长跳跃式比较而突破了n的平方的时间复杂度,希尔排序根据步长的不同时间复杂度由最好的nlogn到最坏的n的平方。代码如下:

       function shallSort(array) {
           var increment = array.length;
           var i
           var temp; //暂存
           var count = 0;
           do {
               increment = Math.floor(increment / 3) + 1;
               for (i = increment; i < array.length; i++) {
                   if (array[i] < array[i - increment]) {
                       temp = array[i];
                       for (var j = i - increment; j > 0 && temp < array[j]; j -= increment) {

                           array[j + increment] = array[j];

                       }
                       array[j + increment] = temp;
                       /* 输出结果 */
                       count++;
                       document.write("<br />第 + count + "遍排序的结果是:")
                       for (var n = 0; n < array.length; n++) {
                           document.write(array[n] + ",");
                       }
                       /* 输出结果结束 */
                   }
               }
           }
           while (increment > 1)

       }

 

堆排序

      堆排序是选择排序的升级，通过不断构建大顶堆或者小顶堆来选择最大或者最小的值放入队列前端进行排序，堆排序任何情况下的时间复杂度都为n的平方，代码如下:

        function heapSort(array) {
            var temp;
            var i;
            for (i = Math.floor(array.length / 2); i >= 0; i--) {
                heapAdjust(array, i, array.length - 1); //将数组array构建成一个大顶堆
            }
            for (i = array.length - 1; i >= 0; i--) {
                /*把根节点交换出去*/
                temp = array[i];
                array[i] = array[0];
                array[0] = temp;

                /*余下的数组继续构建成大顶堆*/
                heapAdjust(array, 0, i - 1);
                /* 输出结果 */
                document.write("<br />第 + (array.length - i).toString() + "遍排序的结果是:")
                for (var n = 0; n < array.length; n++) {
                    document.write(array[n] + ",");
                }
                /* 输出结果结束 */
            }
        }
        //要调整的子树
        //start为数组开始下标
        //max是数组结束下标
        function heapAdjust(array, start, max) {
            var temp, j;
            temp = array[start];//temp是根节点的值
            for (j = 2 * start; j < max; j *= 2) {
                if (j < max && array[j] < array[j + 1]) {  //取得较大孩子的下标
                    ++j;

                }
                if (temp >= array[j])
                    break;
                array[start] = array[j];
                start = j;
            }
            array[start] = temp;

        }

 

归并排序

     归并排序是复杂排序中唯一一个稳定排序，通过将待排序数组进行分拆再合并来进行排序，归并排序时间复杂度为n的平方，代码如下:

        //source源数组
        //dest目标数组
        //s起始下标
        //t目标下标
        function mSort(source, dest, s, t) {
            var m; //取中间值
            var dest2 = new Array();
            if (s == t) {
                dest[s] = source[s];
             
            }
            else {
                m = Math.floor((s + t) / 2);
                mSort(source, dest2, s, m);
                mSort(source, dest2, m+1 , t);
                merge(dest2, dest, s, m, t);
                /* 输出结果 */
                document.write("<br />第 + ++count + "遍排序的结果是:")
                for (var n = 0; n < dest.length; n++) {
                    document.write(array[n] + ",");
                }
                /* 输出结果结束 */
            }

        }
        
        //将两个数组按照从小到大的顺序融合
        //source原数组
        //dest排序后的数组
        //s第一个下标
        //m第二个数组下标
        //总长度
        function merge(source, dest, s, m, n) {
            for (var j = m+1, k = s; j <= n && s <= m; k++) {
                if (source[s] < source[j]) {
                    dest[k] = source[s++];
                }
                else {
                    dest[k] = source[j++];
                }
            }
           
                //将剩余排不完的有序数组加入到dest的末端
                if (s <= m) {
                    for (var l = 0; l <= m - s; l++) {
                        dest[k + l] = source[s+l];
                    }
                }
                if (j <= n) {
                    for (var l = 0; l <= n - j; l++) {
                        dest[k + l] = source[j+l];
                    }
                
            }
        }

 

快速排序

     快速排序是目前已知的速度最快的排序，时间复杂度为nlogn,代码如下:

        var count = 0;
        function quickSort(array, low, high) {
            var temp;
            
            if (low < high) {

                var keypoint = QuickSortHelp(array, low, high);
                count++;
                document.write("<br />第台? + count + "遍括?排?序ò的?结á果?是?:")
                for (var l = 0; l < array.length; l++) {
                    document.write(array[l] + ",");
                }
                quickSort(array, low, keypoint - 1);
                quickSort(array, keypoint + 1, high);
                

                }
        }
        function QuickSortHelp(array, low, high) {
            while (low < high) {

                while (low < high && array[low] <= array[high]) {
                    high--;
                }
                temp = array[low];
                array[low] = array[high];
                array[high] = temp;
                while (low < high && array[low] <= array[high]) {
                    low++
                }
                temp = array[low];
                array[low] = array[high];
                array[high] = temp;

            }
            return low;
        }

 

DEMO

    下面嵌入了demo:

    再次排序需要点清除数组重新添加:

数组内容为:
清为数组添加数字:

        

作者: CareySon 发表于 2011-10-28 15:02 原文链接

评论: 4　查看评论　发表评论

最新新闻：
· Sterling收购Mosaid交易涉及诺基亚微软专利(2011-10-28 21:42)
· 谷歌Android翻译应用支持14种语言(2011-10-28 21:29)
· Netflix占用美国近三分之一带宽(2011-10-28 21:17)
· 三星计划明年推出柔性屏幕手机(2011-10-28 21:16)
· 消息称Sprint即将与Clearwire达成网络共享协议(2011-10-28 20:56)

编辑推荐：乔布斯：初心与终点

网站导航：博客园首页  我的园子  新闻  闪存  小组  博问  知识库

相关 [数据结构 排序 方法] 推荐：

数据结构中的各种排序方法-JS实现

- zhai - 博客园-首页原创精华区
     新技术一直在不断变化，掌握一些基础是未来学习不断更新的技术的坚实基础. 近来闲来无事,为了温习一下从前学的数据结构，将数据结构中的排序算法用JS实现了一遍，并在本文末尾处嵌入了DEMO.      冒泡排序是最简单排序算法,时间复杂度为n的平方,代码如下:. document.write("这是第 + (i + 1) + "次循环·，结果为:");.

数据结构之BloomFilter

- - 编程语言 - ITeye博客
BloomFilter是什么.        BloomFilter主要提供两种操作: add()和contains()，作用分别是将元素加入其中以及判断一个元素是否在其中，类似于Java中的Set接口，它内部采用的byte数组来节 省空间. 其独特之处在于contains()方法，当我们需要查询某个元素是否包含在BloomFilter中时，如果返回true，结果可能是不正确 的，也就是元素也有可能不在其中；但是如果返回的是false，那么元素一定不在其中.

hadoop复合键排序使用方法

- - CSDN博客云计算推荐文章
在hadoop中处理复杂业务时，需要用到复合键，复合不同于单纯的继承Writable接口，而是继承了WritableComparable接口，而实际上，WritableComparable接口继承了Writable和Comparable接口，如果只需要使用某一个类作为传值对象而不是作为key，继承Writable接口即可.

使用graphviz画数据结构

- 王者自由 - Emacs中文网
今天下午用了些时间写了个小的函数，该函数配合 autoinsert + graphviz-dot-mode ，可以很方便的将 C 语言中指定的 struct 结构画出来. 这样，画了多个数据结构之后，再手动添加几条线， 数据结构之间的关系就一目了然了. 1.2 Graphviz 的安装. 1.3 Graphviz 的使用.

数据结构之红黑树

- Shengbin - 董的博客
红黑树是一种自平衡二叉查找树. 它的统计性能要好于平衡二叉树（AVL树），因此，红黑树在很多地方都有应用. 在C++ STL中，很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化，这些修改提供了更好的性能，以及对set操作的支持).

数据结构-二分法查找

- - 操作系统 - ITeye博客
1、二分查找(Binary Search).     　二分查找又称折半查找，它是一种效率较高的查找方法.     　二分查找要求：线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构. 2、二分查找的基本思想.     　二分查找的基本思想是：（设R[low..high]是当前的查找区间）.

redis数据结构缓存运用

- - 企业架构 - ITeye博客
之前redis已经描述了redis 的基本作用与用处， 这一篇主要讲述redis运用场景以及分片,和spring整合. redis 存储数据结构大致5种，String 普通键值对，用的比较多. HASH针对 key 唯一标识 hashmap 键值对运用也比较多 list set 当然是集合运用 sortedSet 排序集合使用.

可视化的数据结构和算法

- greenar - 酷壳 - CoolShell.cn
还记得之前发布过的那个关于可视化排序的文章吗. 在网上又看到了一个旧金山大学David Galles做的各种可视化的数据结构和基本算法的主页，网址在这里，大家可以看看. 我把这个页面的目录列在下面并翻译了一下，大家可以直接点击了. 不知道国内的教育有没有相关的教学课件，至少在我大学的时候是没有的. Queues队列: 数组实现.

为什么要学习算法和数据结构

- snowflip - TopLanguage Google Group