注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

梦幻雪冰

技在手,能在身,思在脑,从容过生活——陈能堡

 
 
 

日志

 
 

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

2014-11-07 13:13:39|  分类: JavaScript |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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

     新技术一直在不断变化,掌握一些基础是未来学习不断更新的技术的坚实基础。近来闲来无事,为了温习一下从前学的数据结构,将数据结构中的排序算法用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)

       }

 

欢迎学习交流---梦幻雪冰

堆排序

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

        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;
        }
        

欢迎学习交流---梦幻雪冰

  评论这张
 
阅读(19)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017