首页 > 代码库 > 数据结构之插入排序--折半插入排序
数据结构之插入排序--折半插入排序
排序思路:通过折半查找的方式找到合适的插入位置再插入。
算法实现:
public class BiInsertSort { public static void biInsertSort(int arr[]){ for(int i = 1; i < arr.length; i ++){ int temp = arr[i]; int left = 0; int right = i-1; while(left <= right){//通过拆装查找找到插入位置 int mid = (left+right)/2; if(temp < arr[mid]){//插入点在[left,mid-1] right = mid-1; }else //插入点在[mid+1,right] left = mid+1; }//直到找到合适的位置(left或right+1),接下来就将left/right+1后的元素后移 for(int j = i-1;j >= right+1; j --){ arr[j+1] = arr[j]; } arr[right+1] = temp; } } public static void main(String[] args) { int array[] = {2,5,3,1,5,2,8}; System.out.println("排序之前:"); for(int element : array){ System.out.print(element+" "); } biInsertSort(array); System.out.println("\n排序之后:"); for(int element : array){ System.out.print(element+" "); } } }
算法分析:不管元素的初始序列为正序还是反序,其时间复杂度都和直接插入排序的一样为O(n2)。不同的是折半插入排序中查找的平均比较次数为log2(i+1)-1,
所以就平均性能而言,折半插入排序优于直接插入排序。
同样,折半插排序的空间复杂度也是O(1),且也是一种稳定的排序。
数据结构之插入排序--折半插入排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。