算法：排序算法总结（JavaScript描述）

dkzwm 发布于2019-08-23 11:45 / 2344人阅读

摘要：二代码简单选择排序一分析循环次，每一次的当前项与其之后的项作比较，找出其中最小的那个，与当前项交换。二代码希尔排序是一种改进版的插入排序，缩小增量排序。这样做的目的是因为，直接插入排序在序列基本有序时效率最高。

排序算法	平均情况	最好情况	最坏情况	辅助空间	稳定性
冒泡排序	O(n^2)	O(n)	O(n^2)	O(1)	稳定
简单选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	稳定
直接插入排序	O(n^2)	O(n)	O(n^2)	O(1)	稳定
希尔排序	O(nlogn)~O(n^2)	O(n^1.3)	O(n^2)	O(1)	不稳定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定
快速排序	O(nlogn)	O(nlogn)	O(n^2)	O(nlogn)~O(n)	不稳定

简单算法：冒泡、简单选择、直接插入
改进算法：希尔、堆、归并、快速

后三种改进算法比希尔算法效率高，但最好的情况下，冒泡和直接插入最有效，因此如果数组基本有序，则需要考虑简单算法

1. 冒泡排序

一、分析

冒泡arr.length-1趟；

第i趟，比较arr.length-i-1次，两两比较，反序则交换位置。

改进：为了避免已经有序的情况下进行无意义的两两比较，用flag标志上一趟是否有交换，没有交换则已经是有序数组，退出循环。

二、代码

    function bubbleSort(arr){
        var flag=true;
        for(let i=0;iarr[j+1]){
                    [arr[j],arr[j+1]]=[arr[j+1],arr[j]];
                    flag=true;
                }
            }
        }
        return arr;
    }

2. 简单选择排序

一、分析

循环arr.length-1次，每一次的当前项与其之后的项作比较，找出其中最小的那个，与当前项交换。

二、代码

    function selectSort(arr){
        var min=0;
        for(let i=0;i
3. 直接插入排序
一、分析

从数组的第二项开始，循环arr.length-1次；
将当前项的值赋值给临时变量：（留出一个“坑”）为了前面大于当前项的项能够后移；
当前项与其前面的项比较，如果大于当前项后移，直到找到小于当前项的那个，将当前项插入其后；
如果前面没有小于当前项的，前面项全部后移以为，当前项就插入位置0处。

二、代码
    function insertSort(arr){
        for(let i=1;i=0&&arr[j]>temp){
                arr[j+1]=arr[j];
                j--;
            }
            arr[j+1]=temp;
        }
        return arr;
    }
4. 希尔排序
  是一种改进版的插入排序，“缩小增量排序”。
一、分析

通过增量将待排序列分割成若干个子序列，每个子序列进行插入排序；
缩小增量，重复步骤1，直到增量不大于0；
ps：增量等于1时，进行了一次全排的直接插入排序。这样做的目的是因为，直接插入排序在序列基本有序时效率最高。

二、代码
    function shellSort(arr){
        for(let increment=Math.floor(arr.length/2);increment>0;increment=Math.floor(increment/2)){
            for(let i=increment;i=0&&arr[j]>temp){
                    arr[j+increment]=arr[j];
                    j-=increment;
                }
                arr[j+increment]=temp;
            }
        }
        return arr;
    }
5. 堆排序
一、分析

将待排序列构造成一个大顶堆（位置0处，也就是堆顶，为最大数）；
将arr[0]与arr[arr.length-1]进行交换，此时数组尾为最大值；
调整0~arr.length-2成一个大顶堆，继续2，直到全部排完。

二、代码
    function heapSort(arr){
        //1. 构造大顶堆
        //2. 顶值最大，交换到最末尾
        //3. 调整大顶堆
        var len=arr.length;
        for(let i=Math.floor(len/2)-1;i>=0;i--){
            heapAdjust(arr,i,len);
        }
        for(let i=arr.length-1;i>0;i--){
            [arr[0],arr[i]]=[arr[i],arr[0]];
            heapAdjust(arr,0,i);
        }
        return arr;
    }
    function heapAdjust(arr,pos,len){
        var root=pos;
        for(let i=2*pos+1;i
6. 归并排序
一、分析

将两个有序数组合成一个有序数组：归并。
将一个数组分割成长度为1的数组，就可以当做它是一个有序数组，两两合并，就成了一个长度为2的有序数组，再两两合并，直到排序完成。

二、代码
    function mergeSort(arr){
        if(arr.length<=1){return arr};

        let mid=Math.floor(arr.length/2);
        let left=arr.slice(0,mid);
        let right=arr.slice(mid);
        // console.log(left+"+"+right);
        return merge(mergeSort(left),mergeSort(right));
    }
    function merge(left,right){
        var result=[];
        while(left.length>0&&right.length>0){
            if(left[0]
7. 快速排序
一、分析

找基准
小于基准的放左边，大于基准的放右边；
递归基准左、右无序序列找基准；
直到输入数组长度为1，跳出递归。

二、代码
    function qSort1(arr){
        if(arr.length<=1){return arr;}

        let pivot=arr[0];
        let left=[];let right=[];
        for(let i=1;i=arr[low]){
                low++
            }
            [arr[low],arr[high]]=[arr[high],arr[low]];
        }

        return low;
    }

云服务器 GPU云服务器排序算法总结算法c语言描述自然语言算法描述最大流算法总结

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

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

十大经典排序算法总结(Javascript描述)

摘要：算法描述冒泡排序是一种简单的排序算法。算法描述和实现一般来说，插入排序都采用在数组上实现。平均情况希尔排序年发明第一个突破的排序算法是简单插入排序的改进版它与插入排序的不同之处在于，它会优先比较距离较远的元素。前言读者自行尝试可以想看源码戳这，博主在github建了个库，读者可以Clone下来本地尝试。此博文配合源码体验更棒哦~~~ 个人博客：Damonare的个人博客原文地址：...

Binguner 2019-08-20 11:05 评论0 收藏0
常用排序算法之JavaScript实现

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

jerry 2019-08-21 12:27 评论0 收藏0
用JavaScript实现插入排序

摘要：实现插入排序插入排序是一种非常简单的算法，最适合大部分已经被排好序的数据。由此才有了这个名字插入排序。插入排序的最坏情况是输入的数组是按逆序排序的。总结当输入的数组已经大部分被排好序时，插入排序的效果最佳。翻译：疯狂的技术宅https://medium.com/@jimrottin... 本文首发微信公众号：前端先锋欢迎关注，每天都给你推送新鲜的前端技术文章插入排序的工作原理...

LittleLiByte 2019-08-26 13:44 评论0 收藏0
JavaScript 数据结构与算法之美 - 归并排序、快速排序、希尔排序、堆排序

摘要：之所以把归并排序快速排序希尔排序堆排序放在一起比较，是因为它们的平均时间复杂度都为。归并排序是一种稳定的排序方法。因此，快速排序并不稳定。希尔排序思想先将整个待排序的记录序列分割成为若干子序列。 showImg(https://segmentfault.com/img/bVbvpYZ?w=900&h=250); 1. 前言算法为王。想学好前端，先练好内功，只有内功深厚者，前端之路才...

haitiancoder 2019-08-26 10:20 评论0 收藏0