首页 > 代码库 > 插入排序——2折半插入排序实现
插入排序——2折半插入排序实现
折半插入与直接插入的不同在于,搜索要插入的位置的时候,使用的是折半搜索(二分搜索)。这种查找方式理论上比顺序查找的效率要高。
其代码实现如下:
public IList<int> InsertionSort(int[] ary) { for (int i = 1; i < ary.Length; i++) { int low = 0; int high = i - 1; var key = ary[i]; //不断的折半 while (low <= high)//注意包含等号 { //找出中间值 int mid = (low + high) / 2; //如果大于中间值 if (key > ary[mid]) { //在大于中间值的那部分查找 low = mid + 1; } else { //在小于中间值的那部分查找 high = mid - 1; } } //使用low来进行移动,此时low是要插入的位置 for (int j = i; j > low; j--) { ary[j] = ary[j - 1]; } ary[low] = key; ////使用high进行移动,此时high是要插入的位置之前的一个位置 //for (int j = i; j > high + 1; j--) //{ // ary[j] = ary[j - 1]; //} ////插入到指定的位置 //ary[high + 1] = key; } return ary.ToList(); }
在内层的while循环,使用的是折半查找,找到在low>high的时候,low的值就是要插入的位置。后面的移动元素和将当前元素插入的操作与直接插入排序是一样的。
最后我们实现一个单独的折半查找的方法,可以进行对比。
public int BinarySearch(int[] ary, int key) { int low = 0; int high = ary.Length - 1; int mid = 0; while (low < high) { mid = (low + high) / 2; if (ary[mid] == key) { return mid; } else if (ary[mid] > key) { high = mid - 1; } else { low = mid + 1; } } return -1; }
这个方法返回的是key在ary中的下标,如果ary中不包含key这个元素,则返回-1。在折半查找在用作插入排序时,需要进行一些修改。
记住代码的写法,以后用的时候,直接按照固定格式来写就行了。
插入排序——2折半插入排序实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。