vlambda博客
学习文章列表

//逐步推倒//希尔排序第一轮//第一轮是将10个数分为了10/2=5组，每组两个，增量5，即每两个数之间相差5-1个//遍历每个分组，i的初始值为当前增量for (int i=5;i < arr.length ;i++ ) { //这一层相当于进行了两数大小比较交换 //j从i-5地方开始减，可以认为从i的位置向前走5步，切换到同组的前一个数 for(int j=i-5;j >=0;j-=5){ //采用交换法比较 if(arr[j] > arr[j+5]){ int temp=arr[j]; arr[j]=arr[j+5]; arr[j+5]=temp; } }}

//希尔排序第二轮//第二轮排序，是将10个数据分为5/2组，每组5个，增量为2，即每两个数之间相差2-1个for(int i=2;i<arr.length;i++){ for(int j=i-2;j>=0;j-=2){ //采用交换法比较 if(arr[j] > arr[j+2]){ int temp=arr[j]; arr[j]=arr[j+2]; arr[j+2]=temp; } }}
 //希尔排序的第3轮//第3轮排序，是将10个数据分成2/2=1组个,步长1for (int i = 1; i < arr.length; i++) { for (int j = i - 1; j >= 0; j -= 1) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } }}

//希尔排序的第n轮//第n轮排序，是将m个数分为m/2组，每组m/gap个，增量gapint gap=0; //增量int count=0 //用于记录轮数

//这层循环控制不同时候的分组for (gap=arr.length;gap>=0 ;gap/=2 ) { //用于控制分组的遍历 for (int i=gap;i<arr.length ;i++ ) { //控制分组内的遍历 for (int j=i-gap;j>=0 ;j-=gap ) { //我采用了位运算，相比较temp的交换效率会高点 if (arr[j] > arr[j + gap]) { // a:arr[j] b: arr[j+gap]// int temp = arr[j+gap];// arr[j+gap]=arr[j];// arr[j]=temp; arr[j] = arr[j] ^ arr[j + gap]; arr[j + gap] = arr[j] ^ arr[j + gap]; arr[j] = arr[j] ^ arr[j + gap]; } } }}

//移位法也是三层，两层for一层while，//因为移位不确定移位次数，因此采用while更合适，而且就是插入的改进int gap=0; //增量//这一层还是控制分组for (gap=arr.length;gap >=0 ; gap /=2) { //还是控制遍历各个分组 for (int i=gap;i <arr.length ;i++ ) { //这个地方就和插入排序很相似 //定义一个记录待插入数的变量 int insertIndex=i; //记录待插入的数 int insertNum=arr[insertIndex]; //如果发现同一份组的该数比前一个数小，那么进行移位 if(arr[insertIndex] < arr[insertIndex-gap]){ //一个分组内，前面元素比后面元素大，则进行移位 while (insertIndex-gap>=0&&insertNum < arr[insertIndex-gap]) { //覆盖操作 arr[insertIndex]=arr[insertIndex-gap]; insertIndex-=gap;  } //循环结束，相当于已经腾出位置,将该数放入 arr[insertIndex]=insertNum; } }}