/*******************************
		???shell排序
Author:蘭亭風(fēng)雨?Date:2014-02-25
Email:zyb_maodun@163.com
********************************/
#include
#include

/*
第一種形式的代碼
對長為len的數(shù)組進(jìn)行一趟增量為ader的插入排序
本算法在插入排序算法的第一種實(shí)現(xiàn)形式上進(jìn)行修改得到
*/
void?Shell_Insert1（int?*arrint?lenint?ader）
{
	int?ik;
	//循環(huán)對ader個(gè)子序列進(jìn)行插入排序操作
	for（k=0;k		for（i=ader+k;i		{	//將第i個(gè)元素分別與前面的每隔ader個(gè)位置的元素比較，插入適當(dāng)?shù)奈恢?br/>			if（arr[i]			{	//一直向左進(jìn)行比較，直到插入到適當(dāng)?shù)奈恢?br/>				int?key?=?arr[i];
				int?count?=?0;	//用來記錄key在與前面元素比較時(shí)向左移動(dòng)了幾個(gè)ader長度
				while（i>k?&&?key				{
					arr[i]?=?arr[i-ader];
					arr[i-ader]?=?key;
					i?-=?ader;
					count++;
				}
				//將待插入的數(shù)定位到下一個(gè)元素，執(zhí)行下一次插入排序
				//因?yàn)楹竺孢€要執(zhí)行i+=ader，所以這里回到原位置即可
				i?+=?count*ader;??
			}?
		}
}

/*
第二種形式的代碼
對長為len的數(shù)組進(jìn)行一趟增量為ader的插入排序
本算法在插入排序算法的第二種實(shí)現(xiàn)形式上進(jìn)行修改得到
*/
void?Shell_Insert2（int?*arrint?lenint?ader）
{
	int?ijk;
	//循環(huán)對ader個(gè)子序列各自進(jìn)行插入排序
	for（k=0;k		for（i=ader+k;i			if（arr[i]?			{
				int?key?=?arr[i];
				for（j=i-ader;j>=k?&&?arr[j]>key;j-=ader）
					arr[j+ader]?=?arr[j];
				arr[j+ader]?=?key;
			}
}

/*
在第二種代碼的形式上繼續(xù)精簡代碼
交叉進(jìn)行各個(gè)子序列的插入排序
*/
void?Shell_Insert2_1（int?*arrint?lenint?ader）
{
	int?ij;
	//對ader子序列交叉進(jìn)行插入排序
	for（i=ader;i		if（arr[i]?		{
			int?key?=?arr[i];
			for（j=i-ader;j>=0?&&?arr[j]>key;j-=ader）
				arr[j+ader]?=?arr[j];
			arr[j+ader]?=?key;
		}
}

/*
第三種形式的代碼
對長為len的數(shù)組進(jìn)行一趟增量為ader的插入排序
本算法在插入排序算法的第三種實(shí)現(xiàn)形式上進(jìn)行修改得到
*/
void?Shell_Insert3（int?*arrint?lenint?ader）
{
	int?ijk;
	//循環(huán)對ader個(gè)子序列各自進(jìn)行插入排序
	for（k=0;k		for（i=ader+k;i			for（j=i-ader;j>=k?&&?arr[j]>arr[j+ader];j-=ader）
			{
				//交換元素?cái)?shù)值
				arr[j]^=arr[j+ader];
				arr[j+ader]^=arr[j];
				arr[j]^=arr[j+ader];
			}
}

/*
在第三種代碼的形式上繼續(xù)精簡代碼
交叉進(jìn)行各個(gè)子序列的插入排序
*/
void?Shell_Insert3_1（int?*arrint?lenint?ader）
{
	int?ij;
	//交叉對ader個(gè)子序列進(jìn)行插入排序
		for（i=ader;i			for（j=i-ader;j>=0?&&?arr[j]>arr[j+ader];j-=ader）
			{
				//交換元素?cái)?shù)值
				//由于arr[j]不等于arr[j+1]，
				//因此可以安全地用該交換方法
				arr[j]^=arr[j+ader];
				arr[j+ader]^=arr[j];
				arr[j]^=arr[j+ader];
			}
}

/*
shell排序后的順序?yàn)閺男〉酱?br/>arr為要排序的數(shù)組，長為len，
add為增量數(shù)組，長為num
*/
void?Shell_Sort（int?*arrint?lenint?*addint?num）
{
	int?i;
	//共進(jìn)行nun趟不同增量的插入排序
	for（i=0;i		Shell_Insert2_1（arr?lenadd[i]）;	//一趟增量為add[i]的插入排序
}
?
int?main（）
{
	int?len;
	printf（“請輸入排序的元素的個(gè)數(shù)：“）;
	scanf（“%d“&len）;

	int?i;
	int?add[]?=?{321};??//增量數(shù)組
	int?*arr?=?（int?*）malloc（len*sizeof（int））;
	printf（“請依次輸入這%d個(gè)元素（必須為整數(shù)）：“l(fā)en）;
	for（i=0;i		scanf（“%d“arr+i）;

	printf（“shell排序后的順序：“）;
	Shell_Sort（arrlenadd3）;
	for（i=0;i		printf（“%d?“arr[i]）;
	printf（“\n“）;

	free（arr）;
	arr?=?0;
	return?0;
}

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----

?????文件?????184387??2014-02-27?12:05??各種排序\shell排序\Debug\shell排序.exe

?????文件?????206764??2014-02-27?12:05??各種排序\shell排序\Debug\shell排序.ilk

?????文件???????8370??2014-02-27?12:05??各種排序\shell排序\Debug\shell排序.obj

?????文件?????220140??2014-02-27?10:32??各種排序\shell排序\Debug\shell排序.pch

?????文件?????443392??2014-02-27?12:05??各種排序\shell排序\Debug\shell排序.pdb

?????文件??????41984??2014-02-27?12:05??各種排序\shell排序\Debug\vc60.idb

?????文件??????45056??2014-02-27?12:05??各種排序\shell排序\Debug\vc60.pdb

?????文件???????3415??2014-02-27?12:06??各種排序\shell排序\shell排序.cpp

?????文件???????3439??2014-02-25?15:53??各種排序\shell排序\shell排序.dsp

?????文件????????526??2014-02-25?16:17??各種排序\shell排序\shell排序.dsw

?????文件??????41984??2014-02-27?12:06??各種排序\shell排序\shell排序.ncb

?????文件??????48640??2014-02-27?12:06??各種排序\shell排序\shell排序.opt

?????文件???????1156??2014-02-27?12:05??各種排序\shell排序\shell排序.plg

?????文件????????816??2014-02-26?12:35??各種排序\冒泡排序\原始冒泡排序\BubbleSort.cpp

?????文件???????3449??2014-02-26?12:35??各種排序\冒泡排序\原始冒泡排序\BubbleSort.dsp

?????文件????????528??2014-02-26?12:35??各種排序\冒泡排序\原始冒泡排序\BubbleSort.dsw

?????文件??????33792??2014-02-26?12:35??各種排序\冒泡排序\原始冒泡排序\BubbleSort.ncb

?????文件??????48640??2014-02-26?12:35??各種排序\冒泡排序\原始冒泡排序\BubbleSort.opt

?????文件????????766??2014-02-26?12:35??各種排序\冒泡排序\原始冒泡排序\BubbleSort.plg

?????文件?????184400??2014-02-26?12:35??各種排序\冒泡排序\原始冒泡排序\Debug\BubbleSort.exe

?????文件?????181776??2014-02-26?12:35??各種排序\冒泡排序\原始冒泡排序\Debug\BubbleSort.ilk

?????文件???????4203??2014-02-26?12:35??各種排序\冒泡排序\原始冒泡排序\Debug\BubbleSort.obj

?????文件?????220140??2014-02-26?12:35??各種排序\冒泡排序\原始冒泡排序\Debug\BubbleSort.pch

?????文件?????361472??2014-02-26?12:35??各種排序\冒泡排序\原始冒泡排序\Debug\BubbleSort.pdb

?????文件??????33792??2014-02-26?12:35??各種排序\冒泡排序\原始冒泡排序\Debug\vc60.idb

?????文件??????45056??2014-02-26?12:35??各種排序\冒泡排序\原始冒泡排序\Debug\vc60.pdb

?????文件?????184407??2014-02-26?12:47??各種排序\冒泡排序\改進(jìn)冒泡排序\Debug\UpdatedBubbleSort.exe

?????文件?????182996??2014-02-26?12:47??各種排序\冒泡排序\改進(jìn)冒泡排序\Debug\UpdatedBubbleSort.ilk

?????文件???????4306??2014-02-26?12:47??各種排序\冒泡排序\改進(jìn)冒泡排序\Debug\UpdatedBubbleSort.obj

?????文件?????220140??2014-02-26?12:40??各種排序\冒泡排序\改進(jìn)冒泡排序\Debug\UpdatedBubbleSort.pch

............此處省略128個(gè)文件信息