JavaScript实现插入排序算法

古城微笑少年丶 2022-03-02 15:22 262阅读 0赞

## 一、插入排序算法原理 ##

插入排序是先将数组中的一部分数进行排序，再将数组中的还未排序的数与已排序的数逐一进行比较，每一次比较都判断二者的大小关系，大的数右移，为小的数腾出位置，直到遇到比这个数小的数为止，该数即“插入”到此处左移，接着将下一个未排序的数与左边已排好序的数逐一比较，重复这一过程。

## 二、JS实现 ##

**1、创建一个待排序的数组**

var arr = [6,3,5,2,7,1];

**2、创建中间变量**

var tem,inner;	//分别为值和索引的中间变量

**3、双重for循环**

for(var outer = 1;outer <= arr.length-1;outer++){ 
    			tem = arr[outer];
    			inner = outer;
    
    			while(inner >0 && arr[inner-1]>arr[inner]){ 
    				arr[inner] = arr[inner-1];
    				inner--;
    				arr[inner] = tem;
    			}
    			console.log(arr);
    		}

首先看下此时的效果：  
![在这里插入图片描述][20190320194209566.png]  
发现排序已成功。

现在对双重for循环的代码进行解释：  
（1）外层循环将遍历数组，每次循环决定要“插入”的数。  
（2）内层循环从第二个元素（第一个进行排序的元素）开始，每次与前一个数进行比较，决定是否左移。

完整代码及注释如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTI1MDMx_size_16_color_FFFFFF_t_70]  
这样我们就用JS实现了插入排序算法。

[20190320194209566.png]: /images/20220302/e38d4df5796f467f85ff6a20748d07ab.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTI1MDMx_size_16_color_FFFFFF_t_70]: /images/20220302/b455a4bc8d924ec085df2126669cf372.png