c语言希尔排序

尽快掌握独自把算法化为代码的能力

希尔排序

两个半小时

#include
#include
using namespace std;
void shellsort(int arr[],int len){
	for(int interval=len/2;interval>0;interval/=2){
		for(int i=interval;itarget&&j>-1){
				arr[j+interval]=arr[j];
				j-=interval;
			}
			arr[j+interval]=target;
		}
	}
	}
void myshell(int arr,int len){
	for(int interval=len/2;len>0;len/=2){
		for(int i=interval;itarget&&j>-1){
				arr[j+interval]=arr[j];
				j-=interval/;
			}
				arr[j+inteval]=target;	
		}
		
	}
}



int main(){
	
	int arr[]={1,5,7,4,6,15,2};
	int len=sizeof(arr)/sizeof(arr[0]);
	shellsort(arr,len);
	for(int i=0;i 
写了两遍第一次对照别人的代码写的，第二次独立完成。
 
#include
#include
using namespace std;
void shellsort(int arr[],int len){
	for(int interval=len/2;interval>0;interval/=2){
		for(int i=interval;itarget&&j>-1){
				arr[j+interval]=arr[j];
				j-=interval;
			}
			arr[j+interval]=target;
		}
	}
	}

 
第一层循环控制增量，第一个最大的增量组是数组长度len/2，每次循环/2，循环条件是>0,最后一次的增量是1
 
第二层循环实现增量分组，例如9个数，第一次进入嵌套循环增量是4，那么，从增量处开始排序，I=interval(这里一个interval代表一个增量）,先把增量处的值存放在target中，int j=i-interval,j是同一组中的另一个数组下标，
 
进入while循环，条件为，同组中左边的数大于右边的数，并且j>-1,把左边的数覆盖到右边的位置上，（增量处的值已经保存在target中），让下标J-interval，第一次进入while时这里就循环一次，但是，第一层循环增量为4时，第二层循环下标j++到8时，这里进入while就可以比两次，相当于0-4-8连接到一起去比，一开始把8的值存起来，如果前两个数都比target大的话，第一次把4的值会覆盖到8上，j再减掉一个Interval后<0跳出循环，把存起来的target给到 j+interval 即可。感觉这里其实不会出现0比8大的情况，因为第一次进入循环的时候就已经比过了，如果0比4大就已经调换过位置了。但是感觉如果interval！=4的时候就要多次调换了
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5711973.html