每天一点数据结构之插入排序

谁践踏了优雅 2022-08-23 00:55 55阅读 0赞

# 每天一点数据结构之插入排序    #

最近没有好好写博客了，接下来又有几门考试就隔几天更新一下吧~

今天学习了插入排序，是排序中很简单的一种，效率不是很高。但比较稳定。主要思想是,遍历一遍数组，将数组集合分为R\[0\]~R\[i\]和R\[i+1\]~R\[n\]两个，前者是排好序的有序集合，后者是乱序的。每次将R\[i+1\]个和前面排好序的关键字依次进行比较，从而找到R\[i+1\]应该插入的位置j，并将R\[j\]之后的值统一后移一位.

实现过程中通过双层循环，首先最好的情况就是已经排好的，那么每趟比较1次，移动0次。最坏的情况下，就是逆序。这时每一趟都需要比较依次并且移动。取两者的平均情况，其时间复杂度为O(n2)。

js代码如下：

<span style="font-size:18px;">function ArraySort(data)
    {
        this.desc_sort = data.concat();
        return this;
    }
    
    //插入排序
    ArraySort.prototype.insert_sort = function()
    {
        //在这里写入代码
        var arr = this.desc_sort;
        var result = [];
        arr.forEach(function (item, index, array) {  //遍历一遍数组
            //将元素按大小插入到result中 r[0]~r[i]之间是有序的，
            //r[i+1]~r[n]之间是无序的，将r[i+1]插入到r[0]~r[i]中
    
            if (result.length == 0)
            {
                result.push(item);
            }
            else   
            {
                var i = result.length-1;
                while (i >= 0)   //与result中的元素进行比较
                {
                 	if (result[parseInt(i/2)] < item)  
                    {
                     	   result.splice(i+1,0,item);
                           break;
                    }
               		if (i == 0)
                    {
                        result.splice(0,0,item);
                        break;
                    }
                   
                    	i--;
                }
            }
        });
     
        this.desc_sort = result.concat();
        return this;
    };</span>