排序算法——插入排序系列及性能测试

素颜马尾好姑娘i 2022-12-13 14:17 142阅读 0赞

### 文章目录 ###

*   *   *  初识插入排序
         *  优化思路
         *   *  思路一
             *  思路二
             *  思路3（希尔排序）
         *  性能测试

### 初识插入排序 ###

插入排序也是较为简单的一种排序算法。它的思想是，先将数组第一个元素，作为一个已经排好序的序列，然后将数组中剩下的元素，从左到右，每次取一个元素，插入到左侧的有序序列中的合适位置，不断扩大左侧有序序列的长度，直到整个数组有序。

图解如下

假设准备对如下数组进行插入排序

![7fbb4372407d1cf624917e26ec1522a4.png][]

首先将第一个元素加入到有序序列中

![dcbd600d4695639ca7241d16a0f7927b.png][]

然后取**未排序部分**的第一个元素，将该元素插入到左侧有序序列中合适的位置

![9c4f03f39cb886bf0633c74ffefd3a55.png][]

**未排序部分**的第一个元素是3，发现3应该插入到9的前面

那么第一轮插入的结果如下

![5b6aa59bbada6b72b8ec651fe802e897.png][]

继续下一轮，取**未排序部分**的第一个元素，6

![b6635f0aa77a6e622fd59317a8597964.png][]

将6插入到左侧有序序列中的合适位置，即3和9之间

![a8fe30c56362d9db05251c1310c4571d.png][]

继续下一轮，取数组未排序部分第一个元素1，发现1应该插入到3的左侧

![e8712626eb402aa4b88149d1c3aed622.png][]

继续下一轮，4被插入到3和6之间

![7828921f612dce32bd5ff8522236c3b1.png][]

下一轮，2被插入到1和3之间

![9392636cdaad916d519d6301331abfb7.png][]

… 最终，整个数组有序

![5d16f2b06ef8b4c4d818754b965a0a8e.png][]

注意：将一个数，插入到有序序列中的合适位置，这个过程可以有多种实现。最简单的一种是采用类似冒泡的过程，不断地比较和交换相邻2个数，一直把待插入元素交换到合适的位置。根据这个思路，插入排序的代码如下

public void insertSort(int[] array) { 
    		/*不断地将数字插入到合适的位置，扩大有序序列的边界 */
    		for (int sortedSize = 1; sortedSize < array.length; sortedSize++) { 
    			for (int i = sortedSize - 1; i >= 0 ; i--) { 
    				if (array[i + 1] < array[i]) { 
    					swap(array, i + 1, i);
    				} else { 
    					break;
    				}
    			}
    		}
    	}

### 优化思路 ###

#### 思路一 ####

**将比较和交换，改为单向赋值**

上述的插入排序，实际还有可优化的空间。因为每一轮排序，实际只要找到一个合适的位置即可。而上面的实现，**找到合适的插入位置**，这个过程，是通过不断地进行元素交换来完成的。**而每次发生2个数的交换，需要3次赋值的操作**。换一种思路，我们其实可以把待插入的元素先暂存起来，然后将**待插入元素**和**有序序列中的元素**从右到左依次做比较，只要有序序列中的元素比待插入元素大的，就将其在有序序列中的位置右移一位，这样，原先每次需要交换的地方，改为了**单向赋值**，就只需要一次赋值操作。最后找到合适位置后，将暂存的待插入元素直接赋值即可。图解如下

假设插入排序过程中某个时刻的数组状态如下

![229cb88b07c8b336ab1e7394776503bc.png][]

下一个待插入的元素为5，将其暂存起来，然后从有序序列最右侧的元素开始，依次和5做比较，发现9比5大，则将9单向往右赋值，覆盖掉了5，逻辑上讲，原先9的位置其实就没用了，因为9已经被右移了一位，而由于我们暂存了5，所以不用担心丢失。没用的元素，下图用紫色做了标记

![932a112bcf4dc6a75682767f3384d261.png][]

然后往左，看有序序列中的下一个元素，8

![be06cb98bef40892276f9570f97b07db.png][]

比较8和5，发现8比5大，则8也向右赋值，覆盖掉紫色的9

![3738dcd598b2bf5126f939fce75b327b.png][]

继续往左，

![2a39fe364970503bf2da7ecd19995a32.png][]

比较2和5，发现2小于5，说明找到了合适的插入位置，将之前暂存的5，单向赋值给紫色元素的位置

![d463a6615329c008f8d874ea97446db9.png][]

就完成了这一轮的插入排序

逻辑上讲，相当于将有序序列中较大的元素，依次往右挪一个位置，留出一个空位给待插入元素，由于是单向赋值，所以和前面的比较交换的方式相比，少了很多次的赋值操作，所以性能会提高一些。但是需要一个额外的空间，来暂存待插入元素。根据这个思路，写成代码如下

public void insertSortV1(int[] array) { 
    		for (int sortedSize = 1; sortedSize < array.length; sortedSize++) { 
    			int temp = array[sortedSize];
    			int i = sortedSize;
    			while (i > 0 && array[i - 1] > temp) { 
    				array[i] = array[i - 1];
    				i--;
    			}
    			array[i] = temp;
    		}
    	}

#### 思路二 ####

**将线性查找，改为二分查找**

由于每一轮插入排序，关键的地方在于**找到合适的插入位置**，这其实是一个查找的过程。上面的实现，使用的都是线性查找，即从有序序列的最右端，依次往左比较，直到找到合适位置。这种查找的时间复杂度是线性的，即O(n)。我们可以针对这个查找的过程进行优化，将线性查找替换为**二分查找**，二分查找是跳跃式的查找，每次取待查找序列的中间位置，与目标值做比较，若小于目标值，则继续在右半边部分进行查找，若大于目标值，则继续在左半边部分进行查找。二分查找每次能缩小一半的查找空间，其时间复杂度为O(log(n))

使用二分查找优化后的代码如下

/** * 二分查找 * @param left 左边界(inclusive) * @param right 有边界(inclusive) * */
    	private int binarySearch(int[] array, int left, int right, int target) { 
    		while (left <= right) { 
                /* 取中间位置 */
    			int mid = (left + right) >> 1;
    			/* * 临界情况有2种 * 1. 待查找区间还剩2个数 -> 此时 right = left + 1 , mid = left * 1.1 若判断 arr[mid] > target, 则该查找左半部分，此时应该插入的位置是mid，也就是left * 1.2 若判断 arr[mid] < target, 则该查找右半部分，此时应该插入的位置是mid + 1，也就是更新后的left * 2. 待查找区间还剩3个数 -> 此时 right = left + 2 , mid = left + 1 * 2.1 若判断 arr[mid] > target, 则查找左半部分，回到情况1 * 2.2 若判断 arr[mid] < target，则查找右半部分，更新完后下一轮循环 left = right = mid， * 若arr[mid] > target，则应插入的位置是left，若arr[mid] < target，则更新完后的left是应插入的位置 * */
    			if (array[mid] > target) { 
    				/* 往左半边查找 */
    				right = mid - 1;
    			} else if (array[mid] < target) { 
    				/* 往右半边查找 */
    				left = mid + 1;
    			} else { 
    				/* 相等了，返回待插入位置为 mid + 1 */
    				return mid + 1;
    			}
    		}
    		return left;
    	}
    
    	@Override
    	public void insertSortBinarySearch(int[] array) { 
    		for (int sortedSize = 1; sortedSize < array.length; sortedSize++) { 
    			int temp = array[sortedSize];
    			/* 获得待插入的位置 */
    			int insertPos = binarySearch(array, 0, sortedSize - 1, temp);
    			/* 将待插入位置之后的有序序列，全部往后移一位 */
    			for (int i = sortedSize; i > insertPos ; i--) { 
    				array[i] = array[i - 1];
    			}
    			array[insertPos] = temp;
    		}
    	}

#### 思路3（希尔排序） ####

**希尔排序**

希尔排序是插入排序的变种，其核心思想是引入了一个**步长**的概念，希尔排序使用**步长**将数组切分成很多个小数组，在每个小数组中利用插入排序，然后逐渐缩小**步长**，最后**步长**缩小到一，步长为一的希尔排序，就是上面的简单插入排序。相比简单插入排序，希尔排序的好处在于可以跨越多个位置来移动元素，而原先的简单插入排序，必须挨个挨个的比较以便找到合适的插入位置。

希尔排序的图解如下，初始步长一般设为数组长度的一半

![c6cd8534b5b79a9576c88d0fd6775e9a.png][]

上述数组就按照gap=4被划分成了4组元素。位置间隔等于gap的元素被分为了同一个组。第一组是\[1,5,9\]，（5和1间隔了4个位置，9和5又间隔了4个位置…）被标注为了浅蓝色，第二组是\[4,7\]，被标注为了淡黄色，第三组是\[2,6\]，被标注为了浅紫色，第四组为\[8,3\]，被标注为了橘色。对每组元素，分别进行简单插入排序，随后缩小gap的值，继续对每组进行插入排序，直到gap被缩小为1，最后一轮相当于进行了一次简单插入排序。由于插入排序在数组基本有序的情况下，能够取得很高的效率，而希尔排序，引入了步长的概念，能够让元素跨越多个位置进行插入排序，而不必挨个挨个的进行操作。每一轮希尔排序后，整个数组都变得更加整体有序（可以理解为，一轮希尔排序后，排在整个数组前面位置的元素，都是每个分组中最小的元素，而排到后面的元素，都是每个分组中较大的元素）

第一轮希尔排序后，数组状态如下（只交换了3和8的位置）

![4e7d8e86b416e749e52467aebf2390bc.png][]

第二轮希尔排序，gap缩小一半，变为2

![2ff1a81a15f4e4f8c213775297e2e9fe.png][]

分别对2组元素进行插入排序，结果如下（第1组，浅蓝色标注，没有任何变化；第2组，橙色标注，只交换了3和4的位置）

![3a72af332b0b60592d5b492c0a2cd62b.png][]

最后，gap=1，进行最后一轮希尔排序（此时相当于进行一次简单插入排序）

肉眼观察可知，最后这轮只需要交换2和3，6和7。两次交换，即完成排序

![4895ce35781ee90a867e5a327fab76c0.png][]

上述数组经过希尔排序，共执行了4次交换操作即完成排序，非常高效，而若采用简单插入排序，交换操作的次数是要大于4的。由此可见希尔排序的强大。根据上述内容，也可更好地理解希尔排序又被称为**缩小增量排序**的含义。步长，增量，gap都是同一个东西。**增量序列**的选择也会影响到希尔排序的效率，通常选择初始增量为数组长度一半，然后每次减半的增量序列即可。

希尔排序的代码实现如下

public void shellSort(int[] array) { 
    		for (int gap = array.length / 2; gap > 0; gap /= 2) { 
    			for (int i = gap; i < array.length; i++) { 
    				int j = i;
    				int temp = array[i];
                    /* 这里没有采用二分查找，直接使用的线性查找 */
    				while (j - gap >= 0 && array[j - gap] > temp) { 
    					array[j] = array[j - gap];
    					j -= gap;
    				}
    				array[j] = temp;
    			}
    		}
    	}

注意代码实现中，是直接从gap之后的位置，遍历到数组最后一个元素，对每个元素，以gap为增量，向前进行直接插入排序。这与图解中分别对每组元素进行插入排序的描述，有一些差别。这样写的好处是，整个希尔排序的代码只需要3层循环，并且比较容易理解。若按照图解的描述，每次以一组元素的插入排序作为一个循环，则写出的代码需要4层循环，不易理解。有兴趣的读者，可以参考下面的代码

public void shellSort(int[] array) { 
    		int gap = array.length / 2;
    		while (gap >= 1) { 
    			for (int i = 0; i < gap; i++) { 
    				/* 这一层循环就是对每一组元素进行插入排序 */
    				for (int j = i; j + gap < array.length; j += gap) { 
    					int pos = j + gap;
    					while (pos - gap >= 0) { 
    						if (array[pos] < array[pos - gap]) { 
    							swap(array, pos, pos - gap);
    							pos -= gap;
    						} else { 
    							break;
    						}
    					}
    				}
    			}
    			gap /= 2;
    		}
    	}

### 性能测试 ###

使用规模从1万到50万的随机数组，对各个插入排序的算法进行了性能测试，绘制成折线图如下

![0e9aec7b7f5af4c07d5b923bb962925f.png][]

可见，希尔排序的性能完爆其他几个版本，使用了二分查找进行优化的次之，使用单向赋值优化的再次之，未优化的性能最差。

[7fbb4372407d1cf624917e26ec1522a4.png]: /images/20221123/2d4e9170570d472082364220ff7ee7e4.png
[dcbd600d4695639ca7241d16a0f7927b.png]: /images/20221123/36cd502b3bc146b7b2d293f8a27651ae.png
[9c4f03f39cb886bf0633c74ffefd3a55.png]: /images/20221123/668141d0a68449a6bf94484cc7eaac01.png
[5b6aa59bbada6b72b8ec651fe802e897.png]: /images/20221123/a66ae146edd74acbbc75b2baa8119287.png
[b6635f0aa77a6e622fd59317a8597964.png]: /images/20221123/afe4c66ef8fe41ab9863cc42849a1fdb.png
[a8fe30c56362d9db05251c1310c4571d.png]: /images/20221123/599fe481799a4d29a2065a4b6c5deaf0.png
[e8712626eb402aa4b88149d1c3aed622.png]: /images/20221123/4b40aa07c84a4ddaa9737b8ae603c785.png
[7828921f612dce32bd5ff8522236c3b1.png]: /images/20221123/d9519e8d68e94c168db665b4f13ac13b.png
[9392636cdaad916d519d6301331abfb7.png]: /images/20221123/2dbf60b0c24d40fd97b669bea06c99a0.png
[5d16f2b06ef8b4c4d818754b965a0a8e.png]: /images/20221123/6bedc493e31d415f9394a38797dcbefd.png
[229cb88b07c8b336ab1e7394776503bc.png]: /images/20221123/66d6d2387ace4a6d80cdb1c19c95351f.png
[932a112bcf4dc6a75682767f3384d261.png]: /images/20221123/7afc4c6e01ee4e3282484a0cd89bf229.png
[be06cb98bef40892276f9570f97b07db.png]: /images/20221123/36f0a90ef98d434cb3dfe7781d466a24.png
[3738dcd598b2bf5126f939fce75b327b.png]: /images/20221123/cf26f3ee0e8b4d50a9e914cc70b8b5dc.png
[2a39fe364970503bf2da7ecd19995a32.png]: /images/20221123/77e0164650004544a49d1a8fe096c790.png
[d463a6615329c008f8d874ea97446db9.png]: /images/20221123/c6181d27f2af474083fc32d2d06a9bef.png
[c6cd8534b5b79a9576c88d0fd6775e9a.png]: /images/20221123/b53c71fe99034eb0b4c41241ae5c0ca1.png
[4e7d8e86b416e749e52467aebf2390bc.png]: /images/20221123/c12764d89ab54e24b6abea6d29a4d82b.png
[2ff1a81a15f4e4f8c213775297e2e9fe.png]: /images/20221123/b95ff3dd1a734180a4ef765c00988e2d.png
[3a72af332b0b60592d5b492c0a2cd62b.png]: /images/20221123/8008dca74b5744b2b5baec71e56081a7.png
[4895ce35781ee90a867e5a327fab76c0.png]: /images/20221123/80c89375179543c1ab8fbc1856ba51e0.png
[0e9aec7b7f5af4c07d5b923bb962925f.png]: /images/20221123/6f594ec74fb44a7b8316b9acf7e13d4a.png