首页 > 代码库 > Java实现希尔排序(增量递减排序)
Java实现希尔排序(增量递减排序)
1 package Insert.sort; 2 3 import java.util.Scanner; 4 5 /*又叫缩小增量排序,本质是插入排序,将待排的序列增量分成几个子序列,分别对每个子序列进行直接插入排序 6 * 增量为5时,取1、6、11、16...为一组,2、7、12、17...为一组等,分别对这些组进行直接插入排序,就是一趟希尔排序 7 * 再以增量为3分割,构成组,分别对这些组进行直接插入排序,就是第二趟希尔排序 8 * 增量为1分割,就是将整个序列进行一趟直接插入排序...第三趟 9 * 希尔排序的思想:直接插入排序适合基本有序的情况,希尔的每趟排序都会使整个序列变得更加有序,等整个序列基本有序了,10 * 再来一趟直接插入排序,这样会使排序效率更高11 * 希尔排序是不稳定排序12 * 时间复杂度O(nlog2(n)) ..2是低13 * 空间复杂度O(1)14 * 注:增量序列最后一个值为1,增量序列中的值没有除1之外的公因子*/15 public class shell {16 17 public static void main(String args[]){18 Scanner cin = new Scanner(System.in);19 String str = cin.nextLine();20 String[] st = str.split(" ");21 int[] c = new int[st.length] ;22 for(int i=0;i<st.length;i++){23 c[i]=Integer.parseInt(st[i]);24 }25 shellSort(c);26 for(int i=0;i<c.length;i++){27 System.out.print(c[i]);28 System.out.print(" ");29 }30 cin.close();31 }32 public static void shellSort(int R[]){33 int k = R.length/2;//分组的增量34 int temp =0 ;35 int x = 0;36 while(k>=1){37 for(int i=0;i<k;i++){//每组的起始位置38 for(int j=i+k;j<R.length;j+=k){//前后记录位置的增量是k,而不是139 x=j-k;40 temp=R[j];41 while(x>=i&&temp<R[x]){42 R[x+k]=R[x];//移动的增量是k不是143 x-=k;44 }45 R[x+k]=temp;46 }47 }48 k=k/2;49 }50 }51 }
Java实现希尔排序(增量递减排序)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。