首页 > 代码库 > Java实现折半(二分)插入排序
Java实现折半(二分)插入排序
1 /*折半插入查找思想:每趟将一个带排序的元素作为关键字插入到已经排好的部分序列的适当位置上,查找适当位置的方法用折半查找法 2 * 适合记录数较多的场景 3 * 在查找插入位置时节省了时间 4 * 在记录移动次数方面和直接插入查找是一样的,所以时间复杂度还是O(n^2) 5 * 空间复杂度同为O(1)*/ 6 7 import java.util.Scanner; 8 9 public class zhebancharusort {10 11 public static void main(String args[]){12 Scanner cin = new Scanner(System.in);13 String str = cin.nextLine();14 String st[] = str.split(" ");15 int num[] = new int[st.length];16 for(int i=0;i<st.length;i++){17 num[i]=Integer.parseInt(st[i]);18 }19 sort(num);20 for(int j=0;j<st.length;j++){21 System.out.print(num[j]);22 System.out.print(" ");23 }24 cin.close();25 }26 public static void sort(int R[]){27 for(int i=1;i<R.length;i++){28 if(R[i]<R[i-1]){29 int low=0;30 int high=i-1;31 int temp = R[i];32 while(low<=high){33 int mid = (int)((low+high)/2);34 if(R[mid]<temp){35 low=mid+1;36 }else{37 high=mid-1;38 }39 }40 for(int j=i;j>low;j--){41 R[j]=R[j-1];42 }43 R[low]=temp;44 }45 }46 }47 }
Java实现折半(二分)插入排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。