首页 > 代码库 > 插入排序算法---插入排序与希尔排序
插入排序算法---插入排序与希尔排序
本文主要说明插入排序、shell排序两种排序方法。
一、插入排序
算法思想：
假定这个数组的序是排好的，然后从头往后，如果有数比当前外层元素的值大，则将这个数的位置往后挪，直到当前外层元素的值大于或等于它前面的位置为止.这具算法在排完前k个数之后，可以保证a[1…k]是局部有序的，保证了插入过程的正确性.
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
⒈ 从第一个元素开始，该元素可以认为已经被排序
⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫描
⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置
⒋ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
⒌ 将新元素插入到下一位置中
⒍ 重复步骤2~5
如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。
插入排序过程示例：
下面是对无序表[12,15,9,20,6,31,24]的排序过程：
伪代码：
INSERTION-SORT(A)1 for j ← 2 to length[A]2 do key ← A[j]3 ? Insert A[j] into the sorted sequence A[1 ‥ j - 1].4 i ← j - 15 while i > 0 and A[i] > key6 do A[i + 1] ← A[i]7 i ← i - 18 A[i + 1] ← key
代码实现：
static int count = 0; /*** * 把n个待排序的元素看成一个有序表和一个无序表， 开始有序表只包含一个元素，无序表中包含n-1个元素， * 排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较， 将它插入到有序表中的适当位置，使之成为新的有序表。 */ public static void runInsertSort(int[] a) { for (int i = 1; i < a.length; i++) { int insertVal = a[i]; // insertValue准备和前一个数比较 int index = i - 1; while (index >= 0 && insertVal < a[index]) { // 将把a[index]向后移动 a[index + 1] = a[index]; // 让index向前移动一位 index--; } // 将insertValue插入到适当位置 a[index + 1] = insertVal; System.out.println("indexPos>>>"+(index+1)); System.out.print("第" + (i) + "次排序结果："); for (int k = 0; k < a.length; k++) { System.out.print(a[k] + "\t"); } System.out.println(""); count++; } System.out.print("最终排序结果："); for (int l = 0; l < a.length; l++) { System.out.print(a[l] + "\t"); } }public static void main(String[] args) { int[] array = new int[6]; for (int k = 0; k < array.length; k++) { array[k] = (int) (Math.random() * 100); } System.out.print("排序之前结果为:"); for (int i = 0; i < array.length; i++) { System.out.print(array[i] + "\t"); } System.out.println(""); runInsertSort(array); System.out.println("交换次数："+count); }
打印结果如下：
排序之前结果为:66 12 90 75 43 85 indexPos>>>0第1次排序结果：12 66 90 75 43 85 indexPos>>>2第2次排序结果：12 66 90 75 43 85 indexPos>>>2第3次排序结果：12 66 75 90 43 85 indexPos>>>1第4次排序结果：12 43 66 75 90 85 indexPos>>>4第5次排序结果：12 43 66 75 85 90 最终排序结果：12 43 66 75 85 90 排序次数：5
算法复杂度:
如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需（n-1）次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1）次。平均来说插入排序算法的时间复杂度为O(n^2）。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。
稳定性:
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
二分插入排序
插入排序中，总是先寻找插入位置，然后在实行挪动和插入过程；寻找插入位置采用顺序查找的方式（从前向后或者从后向前），既然需要插入的数组已经是有序的，那么可以采用二分查找方法来寻找插入位置，提高算法效率，但算法的时间复杂度仍为O(n2)。
public class SortSolution { static int count = 0; /*** * 向有序序列中插入元素，那么插入位置可以不断地平分有序序列， 并把待插入的元素的关键字与平分有序序列的关键字比较，以确定下一步要平分的子序列， * 直到找到合适的插入位置位置。 */ public static void runBinaryInsertSort(int[] a) { for (int i = 1; i < a.length; i++) { int insertVal = a[i];// 待插入的值 int low = 0; int high = i - 1; while (low <= high) { // 找出low,high的中间索引 int mid = (low + high) / 2; // 如果要插入的值大于mid的值 if (insertVal > a[mid]) { low = mid + 1; }// 限制在索引大于mid的那一半中搜索 else { high = mid - 1; }// 限制在索引小于mid的那一半中搜索 } // 将low到i处的所有元素向后整体移动一位 for (int j = i; j > low; j--) { a[j] = a[j - 1]; } // 将insertValue插入到适当位置 a[low] = insertVal; System.out.println("indexPos>>>"+(low)); //System.out.print("\n"); System.out.print("第" + (i) + "次排序结果："); for (int k = 0; k < a.length; k++) { System.out.print(a[k] + "\t"); } System.out.println(""); count++; } } public static void main(String[] args) { int[] array = new int[1500]; for (int k = 0; k < array.length; k++) { array[k] = (int) (Math.random() * 100); } SimpleDateFormat df = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); Date begintime = new Date(); System.out.println("开始时间: " + df.format(begintime)); System.gc(); System.out.print("排序之前结果为:"); for (int i = 0; i < array.length; i++) { System.out.print(array[i] + "\t"); } System.out.println(""); runBinaryInsertSort(array); System.out.println("交换次数："+count); Date endtime = new Date(); System.out.println("结束时间：" + df.format(endtime)); Date time = new Date(endtime.getTime() - begintime.getTime()); System.out.println("总用时间：" + time.getMinutes() + "分" + time.getSeconds() + "秒"); } }
插入排序算法---插入排序与希尔排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。