资讯专栏INFORMATION COLUMN

排序算法——javascript

cucumber / 2159人阅读

摘要:笔试面试如果涉及到数据结构和算法之类的题,貌似都比较喜欢问二叉树,排序算法等,所以整理一下用写的排序算法排序算法几个关键点就是时间复杂度空间复杂度稳定性,前两者对于数学渣渣的我来说只能尽可能记下来了,判定稳定性主要是看两个相同的元素在排序后

笔试面试如果涉及到数据结构和算法之类的题,貌似都比较喜欢问二叉树,排序算法等,所以整理一下用js写的排序算法

排序算法几个关键点就是时间复杂度、空间复杂度、稳定性,前两者对于数学渣渣的我来说只能尽可能记下来了,判定稳定性主要是看两个相同的元素在排序后和排序前的顺序是否改变,如果改变了就是不稳定

冒泡排序

比较相邻的元素,如果第一个数比第二个数大,就交换他们两个,从开始第一对到结尾的最后一对,这样每一轮比较结束都将会把最大的数排在最后,再重复从第一对开始比较,直到某一轮比较结束后没有进行交换,则排序结束

时间复杂度:O(n^n)
空间复杂度:O(1)
稳定性:稳定

JavaScript语言实现

    function bubbleSort(arr){
        var len = arr.length,k=0;
        for(var i=0;;i++){
            k=0;
            for(var j=0;j arr[j+1]){
                    var temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    k=1;                    
                }
            }
            if(k == 0) break;
        }
        console.log(arr);
    }
选择排序

从一组数中选出最小的与第一个数据交换,再从剩余数据中继续选出最小的与第二个数据交换

时间复杂度:O(n^n)
空间复杂度:O(1)
稳定性:不稳定

JavaScript语言实现

    function selectSort(arr){
        var len = arr.length;
        for(var i=0;i
插入排序

将数据分为有序和无序,初始有序数据为第一个数,无序数据为剩余的,将无序数据循环插入到有序数据中

时间复杂度:O(n^n)
空间复杂度:O(1)
稳定性:稳定

JavaScript语言实现

    function insertSort(arr){
        var len = arr.length;
        for(var i=1;i=0 && arr[j]>temp){
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = temp;
        }
        console.log(arr);
    }
快速排序

先选取数组中一个数作为基数,将其他数据与该基数比较,如果大于基数就排在基数的右侧,如果小于就排在基数的左侧,再分别对小于基数和大于基数的数组做快速排序

时间复杂度:O(nlogn)
空间复杂度:O(1ogn)
稳定性:不稳定

JavaScript语言实现

    function quickSort(arr,start,end){

        if(start < end){
            var base = arr[start];
            var temp;
            var i=start,j=end;
            do{
                while(arr[i] < base && i < end){
                    i++;
                }
                while(arr[j] > base && j > start){
                    j--;
                } 
                if(i <= j){
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                    i++;
                    j--;
                }
            }while(i <= j);
            if(start < j){
                sort4(arr,start,j);
            }
            if(end > i){
                sort4(arr,i,end);
            }
        }
        console.log(arr);
    }
归并排序

先将所有数据两两分组进行排序,再两两归并,重复进行直到所有数据归并成一个有序表

时间复杂度:O(nlogn)
空间复杂度:O(1)
稳定性:稳定

JavaScript语言实现

    function mergeSort(arr){
        function sort(array,first,last){
            first = (first === undefined) ? 0 : first;
            last = (last === undefined) ? array.length-1 : last;
            if(last - first <1){return;}
            sort(arr,first,middle);
            sort(arr,middle+1,last);

            var f=first,
                m=middle,
                i,
                temp;
            while(f <= m && m + 1 <= last){
                if(arr[f] >= arr[m+1]){
                    temp = arr[m+1];
                    for(i=m;i>=f;i--){
                        arr[i+1]=arr[i];
                    }
                    arr[f] = temp;
                    m++;
                }else {
                    f++;
                }
            }
            return arr;
        }
        return sort(arr);
    }
堆排序

将数据表示成完全二叉树的形式,并且以最大堆的方式排序,再一次交换最后一个最后一个元素和根元素,并且每一次都重新进行最大堆排序

时间复杂度:O(nlogn)
空间复杂度:O(1)
稳定性:不稳定

JavaScript语言实现

    function heapSort(array){
        function swap(array,i,j){
            var temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
        /*最大堆调整*/
        function maxHeapify(array,index,heapSize){
            var iMax,
                iLeft,
                iRight;
            while(true){
                iMax = index;
                iLeft = 2 * index + 1;
                iRight = 2 * (index + 1);

                if(iLeft < heapSize && array[index] < array[iLeft]){
                    iMax = iLeft;
                }
                if(iRight < heapSize && array[iMax] < array[iRight]){
                    iMax = iRight;
                }
                if(iMax != index){
                    swap(array,iMax,index);
                    index = iMax;
                }else{break;}
            }
        }
        /*创建最大堆*/
        function buildMaxHeap(array){
            var i,
                iParent = Math.floor(array.length/2) - 1;

            for(i = iParent; i >= 0; i--){
                maxHeapify(array,i,array.length);
            }
        }
        /*堆排序*/
        function sort(array){
            buildMaxHeap(array);

            for(var i = array.length - 1;i > 0; i--){
                swap(array, 0, i);
                maxHeapify(array, 0, i);
            }
            return array;
        }
        return sort(array);
希尔排序

每次对相隔一定间隔的数进行插入排序

时间复杂度:O(nlogn)
空间复杂度:O(1)
稳定性:不稳定

JavaScript语言实现

    function shellSort(array){

        function swap(array, i, k){
            var temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }

        var length = array.length,
            gap = Math.floor(length / 2);

        while(gap > 0){
            for(var i = gap; i < length; i++){
                for(var j = i; j > 0; j -= gap){
                    if(array[j - gap] > array[j]){
                        swap(array, j - gap, j);
                    }else {
                        break;
                    }
                }
            }

            gap = Math.floor(gap/2);
        }

        return array;
    }

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/80407.html

相关文章

  • 深入浅出 JavaScript 的 Array.prototype.sort 排序算法

    摘要:快速排序是不稳定的排序算法。浏览器的实现不同有什么影响排序算法不稳定有什么影响举个例子某市的机动车牌照拍卖系统,最终中标的规则为按价格进行倒排序相同价格则按照竞标顺位即价格提交时间进行正排序。 本文要解决的问题 1、找出 Array.prototype.sort 使用的什么排序算法 2、用一种直观的方式展示 Array.prototype.sort 的时间复杂度,看看它有多快? 3、...

    itvincent 评论0 收藏0
  • JavaScript算法 ,Python算法,Go算法,java算法,系列之归并排序

    摘要:常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。用一张图概括归并排序英语,或,是创建在归并操作上的一种有效的排序算法,效率为。 常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

    zhou_you 评论0 收藏0
  • JavaScript算法 ,Python算法,Go算法,java算法,系列之归并排序

    摘要:常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。用一张图概括归并排序英语,或,是创建在归并操作上的一种有效的排序算法,效率为。 常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

    caoym 评论0 收藏0
  • JavaScript算法 ,Python算法,Go算法,java算法,系列之归并排序

    摘要:常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。用一张图概括归并排序英语,或,是创建在归并操作上的一种有效的排序算法,效率为。 常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

    microcosm1994 评论0 收藏0
  • 常用排序算法JavaScript实现

    摘要:代码实现六堆排序算法简介堆排序是指利用堆这种数据结构所设计的一种排序算法。九计数排序算法简介计数排序是一种稳定的排序算法。计数排序不是比较排序,排序的速度快于任何比较排序算法。 赞助我以写出更好的文章,give me a cup of coffee? 2017最新最全前端面试题 1、插入排序 1)算法简介 插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它...

    jerry 评论0 收藏0
  • 优秀程序员都应该学习的 GitHub 上开源的数据结构与算法项目

    摘要:强烈推荐上值得前端学习的数据结构与算法项目,包含图的演示过程与视频讲解。该仓库包含了多种基于的算法与数据结构,提供进一步阅读的解释和链接。数据结构和算法必知必会的个代码实现。 showImg(https://segmentfault.com/img/bVbvpYZ); 前言 算法为王。想学好前端,先练好内功,内功不行,就算招式练的再花哨,终究成不了高手;只有内功深厚者,前端之路才会走得...

    cheukyin 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<