| 盈彩体育注册(中国)有限公司 |  您所在的位置：网站首页 ›
盈彩体育注册(中国)有限公司 › 优化的直接插入排序（二分查找插入排序，希尔排序） |
优化的直接插入排序（二分查找插入排序，希尔排序）
|
本博文向大家介绍了插入排序的三种实现：直接插入排序，二分查找插入排序，希尔排序。详细分析的其实现过程、时间复杂度和空间复杂度、稳定性以及优化改进策略。最后简单的做了下性能测试。
直接插入排序 (一)概念及实现 直接插入排序的原理：先将原序列分为有序区和无序区，然后再经过比较和后移操作将无序区元素插入到有序区中。
具体如下（实现为升序）： 设数组为a[0…n]。 1. 将原序列分成有序区和无序区。a[0…i-1]为有序区，a[i…n] 为无序区。（i从1开始） 2. 从无序区中取出第一个元素，即a[i]，在有序区序列中从后向前扫描。 3. 如果有序元素大于a[i]，将有序元素后移到下一位置。 4. 重复步骤3，直到找到小于或者等于a[i]的有序元素，将a[i]插入到该有序元素的下一位置中。 5. 重复步骤2~4，直到无序区元素为0。
实现代码： public static void Sort(IList arr) where T : IComparable { if (arr == null) throw new ArgumentNullException("arr"); int length = arr.Count(); if (length > 1) { int i, j, k; // 将arr分成有序区和无序区，初始有序区有一个元素 // 0-(i-1) 为有序区；i-(length-1)为无序区 （i从1开始） for (i = 1; i < length; i++) { T temp = arr[i]; // 边找位置边后移元素 for (j = i - 1; j >=&& arr[j].CompareTo(temp) > 0; j--) arr[j + 1] = arr[j]; // 如果已排序的元素大于新元素，将该元素移到下一位置 // 将 arr[i] 放到正确位置上 arr[j + 1] = temp; } } }
示例： 89,-7,999,-89,7,0,-888,7,-7 排序的过程： [89] [-7 999 -89 7-888 7 -7] [-7 89] [999 -89 7-888 7 -7] [-7 89 999] [-89 7-888 7 -7] …… …… [-888 -89 -7 -77 7 89 999] []
(二)算法复杂度 1. 时间复杂度：O(n^2) 直接插入排序耗时的操作有：比较+后移赋值。时间复杂度如下： 1) 最好情况：序列是升序排列，在这种情况下，需要进行的比较操作需（n-1）次。后移赋值操作为0次。即O(n) 2) 最坏情况：序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。后移赋值操作是比较操作的次数加上 (n-1）次。即O(n^2) 3) 渐进时间复杂度（平均时间复杂度）：O(n^2) 2. 空间复杂度：O(1) 从实现原理可知，直接插入排序是在原输入数组上进行后移赋值操作的（称“就地排序”），所需开辟的辅助空间跟输入数组规模无关，所以空间复杂度为：O(1)
(三)稳定性 直接插入排序是稳定的，不会改变相同元素的相对顺序。
(四)优化改进 1. 二分查找插入排序：因为在一个有序区中查找一个插入位置，所以可使用二分查找，减少元素比较次数提高效率。 2. 希尔排序：如果序列本来就是升序或部分元素升序，那么比较+后移赋值操作次数就会减少。希尔排序正是通过分组的办法让部分元素升序再进行整个序列排序。（原因是，当增量值很大时数据项每一趟排序需要的个数很少，但数据项的距离很长。当增量值减小时每一趟需要和动的数据增多，此时已经接近于它们排序后的最终位置。）
下面来分别介绍：二分查找插入排序和希尔排序
二分查找插入排序 (一)概念及实现 二分查找插入排序的原理：是直接插入排序的一个变种，区别是：在有序区中查找新元素插入位置时，为了减少元素比较次数提高效率，采用二分查找算法进行插入位置的确定。
具体如下（实现为升序）： 设数组为a[0…n]。 1. 将原序列分成有序区和无序区。a[0…i-1]为有序区，a[i…n] 为无序区。（i从1开始） 2. 从无序区中取出第一个元素，即a[i]，使用二分查找算法在有序区中查找要插入的位置索引j。 3. 将a[j]到a[i-1]的元素后移，并将a[i]赋值给a[j]。 4. 重复步骤2~3，直到无序区元素为0。
实现代码： /// /// 二分查找插入排序 /// public static void BinarySort(IList arr) where T : IComparable { if (arr == null) throw new ArgumentNullException("arr"); int length = arr.Count(); if (length > 1) { int i, j, k; // 将arr分成有序区和无序区，初始有序区有一个元素 // 0-(i-1) 为有序区；i-(length-1)为无序区 for (i = 1; i < length; i++) { // 二分查找在有序区寻找插入的位置 int index = BinarySearchIndex(arr, i - 1, arr[i]); if (i != index) { T temp = arr[i]; // 后移元素，腾出arr[index]位置 for (j = i - 1; j >= index; j--) arr[j + 1] = arr[j]; // 将 arr[i] 放到正确位置上 arr[index] = temp; } } } } /// /// 二分查找要插入的位置得Index /// /// 数组 /// 有序区最大索引 /// 待插入值 /// 插入的位置的Index private static int BinarySearchIndex(IList arr, int maxIndex, T data) where T : IComparable { int iBegin = 0; int iEnd = maxIndex; int middle = -1; int insertIndex = -1; while (iBegin 0) { iEnd = middle - 1; } else { // 如果是相同元素，也是插入在后面的位置 iBegin = middle + 1; } } return iBegin; }
示例： 89,-7,999,-89,7,0,-888,7,-7 排序的过程： [89] [-7 999 -89 7-888 7 -7] [-7 89] [999 -89 7-888 7 -7] [-7 89 999] [-89 7-888 7 -7] …… …… [-888 -89 -7 -77 7 89 999] []
(二)算法复杂度 1. 时间复杂度：O(n^2) 二分查找插入位置，因为不是查找相等值，而是基于比较查插入合适的位置，所以必须查到最后一个元素才知道插入位置。 二分查找最坏时间复杂度：当2^X>=n时，查询结束，所以查询的次数就为x，而x等于log2n（以2为底，n的对数）。即O(log2n) 所以，二分查找排序比较次数为：x=log2n 二分查找插入排序耗时的操作有：比较 + 后移赋值。时间复杂度如下： 1) 最好情况：查找的位置是有序区的最后一位后面一位，则无须进行后移赋值操作，其比较次数为：log2n 。即O(log2n) 2) 最坏情况：查找的位置是有序区的第一个位置，则需要的比较次数为：log2n，需要的赋值操作次数为n(n-1)/2加上 (n-1) 次。即O(n^2) 3) 渐进时间复杂度（平均时间复杂度）：O(n^2) 2. 空间复杂度：O(1) 从实现原理可知，二分查找插入排序是在原输入数组上进行后移赋值操作的（称“就地排序”），所需开辟的辅助空间跟输入数组规模无关，所以空间复杂度为：O(1)
(三)稳定性 二分查找排序是稳定的，不会改变相同元素的相对顺序。
希尔排序 (一)概念及实现 思想：分治策略 希尔排序是一种分组直接插入排序方法，其原理是：先将整个序列分割成若干小的子序列，再分别对子序列进行直接插入排序，使得原来序列成为基本有序。这样通过对较小的序列进行插入排序，然后对基本有序的数列进行插入排序，能够提高插入排序算法的效率。
具体如下（实现为升序）： 1. 先取一个小于n的整数d1作为第一个增量，将所有距离为d1的倍数的记录放在同一个组中，把无序数组分割为若干个子序列。 2. 在各子序列内进行直接插入排序。 3. 然后取第二个增量d2 |
【本文地址】 转载请注明
