如何将JavaScript的插入排序算法改写为长尾词的？

本文共计751个文字，预计阅读时间需要4分钟。

想法：将关键字temp通过比较大小插入到已排序序列中，直到全部元素插入完成。

实现步骤：

1.判断是否为数组。

2.判断数组是否为空。

3.默认序列下标为0的值为有序序列。

4.从下一位开始遍历数组，将temp与当前元素比较大小。

5.如果temp小于当前元素，将temp插入到当前位置，并将后续元素依次后移。

6.如果temp大于当前元素，继续比较下一位元素。

7.当遍历完所有元素后，temp已插入到正确的位置。

思想：

就是在把关键字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));