思想：
就是在把關鍵字temp通過比較大小，插入到前面已經排好序的序列中，直到全部元素插入完成，
實作步驟：
- 是否為陣列->陣列是否為空
- 默認序列下標0的數值為有序序列，而從下標1到末尾的元素
temp構成無序序列 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));
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/499628.html
標籤：其他
上一篇：【Unity Shader學習筆記】Unity高級紋理 - 立方體紋理
下一篇：選擇排序/插入排序/冒泡排序