javascript实现排序算法

xiangzhihong 发布于2019-08-22 10:39 / 2749人阅读

摘要：高级排序算法有希尔排序归并排序快速排序。冒泡排序首先声明，这是最慢的排序算法之一，但是也是最容易实现的排序算法。稳定性冒泡排序为一种稳定排序。快速排序快速排序是出力大数据集最快的排序算法之一。

简介

对计算机中存储的数据执行的两种最常见的操作是排序和检索，也是面试经常会被问到的一个知识点，本文将整理数据排序的基本算法和高级算法。其中基本排序算法有：冒泡排序、选择排序、插入排序。高级排序算法有：希尔排序、归并排序、快速排序。
通常排序问题都可以分隔为相同的小规模问题来解决，即问题的解决都是递归的思路。

冒泡排序

首先声明，这是最慢的排序算法之一，但是也是最容易实现的排序算法。
算法描述：对于一个数列，从第一个元素开始，依次对相邻元素进行两两比较，如果第一个元素大于第二个元素就交换他们的位置。
稳定性：冒泡排序为一种稳定排序。
步骤：
1.从第一个元素开始，比较相邻的元素，如果第一个比第二个大，就交换他们的位置，一次排序可以将大元素沉底。
2.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

function bubble(list){
    for (var i=1; ilist[j+1]){//如果第一个元素大于第二个，交换二者的位置
                list[j] = list[j] + list[j+1];
                list[j+1] = list[j] - list[j+1]; //list[j]
                list[j] = list[j] - list[j+1]; //list[j+1]
            }
        }
    }
    return list;
}

选择排序

算法描述：从数组的开头开始，将第一个元素和其他元素进行比较。检查完所有元素后最小的元素将会被放到数组的第一个位置，然后对第二个元素执行相同的操作，最后直到所有的元素排序完毕。
稳定性：选择排序是一种不稳定的排序。

function selection(list){
    for(var i=0; ilist[j]){ //交换二者的位置
                list[i] = list[i]+list[j];
                list[j] = list[i]-list[j];
                list[i] = list[i]-list[j];
            }
        }
    }
    return list;
}

插入排序

算法描述：对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，直到所有的数据排序完毕。
步骤：
1.第一个元素，认为已经被排序。
2.下一个元素，从已排序的的序列中从前向后扫描，一直找到大于或等于它的元素，将此元素插入到那个元素之前。
3.重复步骤2.
稳定性：插入排序是一个稳定排序。

function insert(list){
    for(var i =1; i=j; k--){//从j到i－1的元素向后移动一位
                   list[k] = list[k-1];
               }
               list[j] = a;
           }
       }
    }
    return list;
}

希尔排序

希尔排序是在插入排序的基础上改进的。希尔排序是基于插入排序的以下两点性质而提出改进方法的：
1、插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
2、但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
步骤：
1.先取一个小于n的整数d1作为第一个增量，把所有距离为d1的元素放在同一个分组中，先在各组内进行直接插入排序；
2.然后取第二个增量d2一般的初次取序列的一半为增量，以后每次减半，直到增量为1。
稳定性：希尔排序是不稳定排序

归并排序

实现原理是把一系列排好序的字序列合并成一个大的完整有序序列。

快速排序

快速排序是出力大数据集最快的排序算法之一。它是一种分而治之的算法，通过递归的方式将数据一次分解为包含小元素和包含大元素的不同子序列。然后不断重复这个步骤直到所有数据都是有序的。快速排序非常适合大型数据集合的排序，对于小数据集时性能反而会有下降。
步骤：
1.选择一个基准元素，将列表分隔成两个子序列；
2.对序列重新排序，将所有小于基准值的元素放在基准值前面，所有大于基准值的元素放在基准值后面；
3.分别对较小元素的子序列和较大元素的子序列重复步骤1、2。
稳定性：快速排序是不稳定排序

function quickSort(list){
    if(list.length == 0){
        return [];
    }
    else{
        var lesser = []; //小于基准值的序列
        var greater = []; //大于基准值的序列
        var pivot  = list[0];
        for(var i=1; i

云服务器 GPU云服务器排序算法图解排序算法总结桶排序算法学习排序算法

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

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

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

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

itvincent 2019-08-21 11:55 评论0 收藏0
常用排序算法之JavaScript实现

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

jerry 2019-08-21 12:27 评论0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,C#算法系列之插入排序

摘要：常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。插入排序在实现上，通常采用排序即只需用到的额外空间的排序，因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： showImg(https://segm...

GeekQiaQia 2019-08-21 11:41 评论0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,C#算法系列之插入排序

摘要：常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。插入排序在实现上，通常采用排序即只需用到的额外空间的排序，因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： showImg(https://segm...

cgspine 2019-08-16 10:33 评论0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,C#算法系列之插入排序

摘要：常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。插入排序在实现上，通常采用排序即只需用到的额外空间的排序，因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： showImg(https://segm...

lufficc 2019-07-31 10:56 评论0 收藏0
优秀程序员都应该学习的 GitHub 上开源的数据结构与算法项目

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

cheukyin 2019-08-26 10:17 评论0 收藏0