草庐IT

JavaScript插入排序

PaturNax 2023-03-28 原文

思想：

就是在把关键字temp通过比较大小，插入到前面已经排好序的序列中，直到全部元素插入完成。

实现步骤：

  1. 是否为数组->数组是否为空
  2. 默认序列下标0的数值为有序序列，而从下标1到末尾的元素temp构成无序序列
  3. temp和前面的有序序列进行依次比较，比较的同时也让有序序列往后移动，直到找到比temp大的元素，就找到要插入的位置。
function insertSort(arr){
    //是否是数组
    if(Object.prototype.toString.call(arr).slice(8,-1)==='Array'){
        //数组是否为空
        var len=arr.length;
        if(len === 0){
            return arr;
        }
        //认为第1个数是有序的，从第2个数开始遍历,下标从1开始
        for(var i=1;i<len;i++){
            //取出第i个数，和前i-1个数比较后，插入合适的位置
            temp=arr[i];
            //因为前i-1个数都是升序序列
            //则当比较的数arr[j]比temp大，就要后移
            var j = i - 1;
            while(j>=0 && arr[j]>temp){
                arr[j+1]=arr[j];
                j--;
            }
            //插入的位置,j+1则是因为while循环往回退多了一位
            arr[j+1]=temp;
        }
        return arr;
    }else{
        return 'not an Array!'
    }
}

var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(insertSort(arr));
  • 时间复杂度为\(O(N^2)\)
  • 空间复杂度为\(O(1)\)

插入排序是稳定算法

优化

通过二分查找搜索插入的位置

/* 
二分查找函数
array:输入的完整数组
n:有序序列的长度
value:待插入的元素
*/
function BinarySearch(array,n,value){
    //有序序列的左右双指针
    let left=0,right=n-1,mid;
    //采用闭区间的写法
    while(left<=right){
        //取中间下标，做二分查找判断
        mid = left + ((right-left)>>1);
        if(array[mid]>value){
            right=mid-1;
        }else{
            left=mid+1;
        }
    }
    //防止出现单个元素的情况出现
    return (left<n) ? left : -1;
}

//二分插入排序
function BinaryInsertSort(arr){
    //判断是否是数组
    if(Object.prototype.toString.call(arr).slice(8,-1)==='Array'){
        if(arr.length === 0){
            return arr;
        }
        for(var i=1;i<arr.length;i++){
            var insert_index=BinarySearch(arr,i,arr[i]);
            //经过判断插入元素的位置没有问题后
            if(insert_index !== -1){
                var temp = arr[i];
                var j = i-1;
                //往后移动
                while(j >= insert_index){
                    arr[j+1]=arr[j];
                    j--;
                }
                //插入的位置 arr[insert_index]也行
                arr[j+1]=temp;
            }
        }
        return arr;
    }else{
        return 'not an Array!'
    }
}

var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(BinaryInsertSort(arr));
JavaScript插入排序arrcode有序算法与数据结构

有关JavaScript插入排序的更多相关文章

  1. ruby-on-rails - 需要帮助最大化多个相似对象中的 3 个因素并适当排序 - 2

    我需要用任何语言编写一个算法，根据3个因素对数组进行排序。我以度假村为例(如Hipmunk)。假设我想去度假。我想要最便宜的地方、最好的评论和最多的景点。但是，显然我找不到在所有3个中都排名第一的方法。Example(assumingthereare20importantattractions):ResortA:$150/night...98/100infavorablereviews...18of20attractionsResortB:$99/night...85/100infavorablereviews...12of20attractionsResortC:$120/night

  2. ruby-on-rails - 使用 javascript 更改数据方法不会更改 ajax 调用用户的什么方法？ - 2

    我遇到了一个非常奇怪的问题，我很难解决。在我看来，我有一个与data-remote="true"和data-method="delete"的链接。当我单击该链接时，我可以看到对我的Rails服务器的DELETE请求。返回的JS代码会更改此链接的属性，其中包括href和data-method。再次单击此链接后，我的服务器收到了对新href的请求，但使用的是旧的data-method，即使我已将其从DELETE到POST(它仍然发送一个DELETE请求)。但是，如果我刷新页面，HTML与"new"HTML相同(随返回的JS发生变化)，但它实际上发送了正确的请求类型。这就是这个问题令我困惑的

  3. ruby - 如何在 Ruby 字符串中插入项目符号字符？ - 2

    我正在尝试创建一个带有项目符号字符的Ruby1.9.3字符串。str="•"+"helloworld"但是，当我输入它时，我收到有关非ASCII字符的语法错误。我该怎么做？ 最佳答案 你可以把Unicode字符放在那里。str="\u2022"+"helloworld" 关于ruby-如何在Ruby字符串中插入项目符号字符？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/1195

  4. ruby-on-rails - 在具有 ActiveRecord 条件的相关模型中按字段排序 - 2

    我正在尝试按Rails相关模型中的字段进行排序。我研究的所有解决方案都没有解决如果相关模型被另一个参数过滤？元素模型classItem相关模型:classPriority我正在使用where子句检索项目:@items=Item.where('company_id=?andapproved=?',@company.id,true).all我需要按相关表格中的“位置”列进行排序。问题在于，在优先级模型中，一个项目可能会被多家公司列出。因此，这些职位取决于他们拥有的company_id。当我显示项目时，它是针对一个公司的，按公司内的职位排序。完成此任务的正确方法是什么？感谢您的帮助。PS-我

  5. ruby - 按数字(从大到大)然后按字母(字母顺序)对对象集合进行排序 - 2

    我正在构建一个小部件来显示奥运会的奖牌数。我有一个“国家”对象的集合，其中每个对象都有一个“名称”属性，以及奖牌计数的“金”、“银”、“铜”。列表应该排序:1.首先是奖牌总数2.如果奖牌相同，按类型分割(金>银>铜，即2金>1金+1银)3.如果奖牌和类型相同，则按字母顺序子排序我正在用ruby​​做这件事，但我想语言并不重要。我确实找到了一个解决方案，但如果感觉必须有更优雅的方法来实现它。这是我做的:使用加权奖牌总数创建一个虚拟属性。因此，如果他们有2个金牌和1个银牌，加权总数将为“3.020100”。1金1银1铜为“3.010101”由于我们希望将奖牌数排序为最高的，因此列表按降序排

  6. ruby - 在 ruby​​ 中使用自动创建插入数组 - 2

    我想知道是否可以通过自动创建数组来插入数组，如果数组不存在的话，就像在PHP中一样:$toto[]='titi';如果尚未定义$toto，它将创建数组并将“titi”压入。如果已经存在，它只会推送。在Ruby中我必须这样做:toto||=[]toto.push('titi')可以一行完成吗？因为如果我有一个循环，它会测试“||=”，除了第一次:Person.all.eachdo|person|toto||=[]#with1billionofperson,thislineisuseless999999999times...toto.push(person.name)你有更好的解决方案吗？

  7. ruby-on-rails - 在不重新查询数据库的情况下重新排序 Rails 中的事件记录？ - 2

    例如，假设我有一个名为Products的模型，并且在ProductsController中，我有以下代码用于product_listView以显示已排序的产品。@products=Product.order(params[:order_by])让我们想象一下，在product_listView中，用户可以使用下拉菜单按价格、评级、重量等进行排序。数据库中的产品不会经常更改。我很难理解的是，每次用户选择新的order_by过滤器时，rails是否必须查询，或者rails是否能够以某种方式缓存事件记录以在服务器端重新排序？有没有一种方法可以编写它，以便在用户排序时rails不会重新查询结果

  8. ruby-on-rails - 在方法调用中插入 Ruby？ - 2

    在我的用户模型中，我有一堆属性，例如is_foos_admin和is_bars_admin，它们决定允许用户编辑哪些类型的记录。我想干掉我的编辑链接，目前看起来像这样:'edit'ifcurrent_user.is_foos_admin?%>...'edit'ifcurrent_user.is_bars_admin?%>我想做一个帮助程序，让我传入一个foo或bar并返回一个链接来编辑它，就像这样:助手可能看起来像这样(这不起作用):defedit_link_for(thing)ifcurrent_user.is_things_admin?link_to'Edit',edit_poly

  9. ruby-on-rails - 如何对对象数组进行排序？ - 2

    我有一个对象如下:[{:id=>2,:fname=>"Ron",:lname=>"XXXXX",:photo=>"XXX"},{:id=>3,:fname=>"Dain",:lname=>"XXXX",:photo=>"XXXXXXX"},{:id=>1,:fname=>"Bob",:lname=>"XXXXXX",:photo=>"XXXX"}]我想按fname排序，不区分大小写，所以它会导致编号:1,3,2我该如何排序？我正在尝试:@people.sort!{|x,y|y[:fname]x[:fname]}但这没有任何效果。 最佳答案

  10. ruby - 使用自定义排序首选项对数组进行排序？ - 2

    有人可以告诉我如何根据自定义字符串对嵌套数组进行排序吗？比如有没有办法排序:[['Red','Blue'],['Green','Orange'],['Purple','Yellow']]“橙色”、“黄色”，然后是“蓝色”？最终结果如下所示:[['Green','Orange'],['Purple','Yellow'],['Red','Blue']]它不是按字母顺序排序的。我很想知道我是否可以定义要排序的值以实现上述目标。 最佳答案 sort_by对于这种排序总是非常方便:a=[['Red','Blue'],['Green','Ora

随机推荐