前言

本文主要记录了JavaScript 实现 -- 插入排序，以及原理、时间复杂度、空间复杂度和算法稳定性。

插入排序

插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个高效的算法 。

插入排序原理

从数组中第二个元素开始比较前面的元素，如果前的元素大，就把它向后排，以此类推完成排序。

arr = [6,3,2,5,4,1] 是待排序数组；

首先取出数组中第二个元素 3 ，去比较前一个元素 6 ，6 比 3大，所有把6移动到3的位置上，6前面没有元素所以将把 3 插入到 6 位置上；

然后取出数组中第三个元素 2 ，6 比 2 大，将 6 移动到 2 的位置上，比较 3 比 2 大，将 3 移动到 6 的位置上，3前面没有元素所以将2插入到3的位置上；

依次类推，完成整个数组的排序。

示例代码

	Array.prototype.insertionSort = function() {
	    for(let i =1;i<this.length;i++){
	        let tmp = this[i];
	        let j = i;
	        while(j>0){
	            if(this[j-1] > tmp){
	                this[j] = this [j-1];
	            }else{
	                break;
	            }
	            j--;
	        }
	        this[j] = tmp;
	    }
	}

时间复杂度

最坏的情况：外层循环n-1次，内层循环1+2+3+…+(n-2)=(n-2)(n-1)/2次，所以最坏情况是O(n^2)；

最好的情况（已经有序）：O(n)；

平均情况为：(n^2 + n)/2，**时间复杂度为O(n^2)**；

空间复杂度

插入排序过程中，需要一个临时变量存储待排序元素，所以**空间复杂度为O(1)**。

算法稳定性

插入排序是稳定的排序算法；

本文到此结束

如果大家还有什么其他想法，欢迎在评论区交流！