/*  輸入若干個國家名，按照字典順序將這寫國名排序
    要求：
	     所有國名全用大寫或小寫，要求用Shell排序算法
    測試數據 ：SINGAPORE  SWEDEN KOREA NETHRLANDS CHINA BRITAIN POLAN    */


#include<stdio.h>
#include<string.h>
#include<conio.h>

void main()
{
	printf("----------------用Shell排序對字符串按字典順序排序(2005/03/04)------------------\n\n\n");
	char a[7][20]={  "SINGAPORE",
					 "SWEDEN",
					 "KOREA",
					 "NETHERLANDS",
					 "CHINA",
					 "BRITAIN",
					 "POLAND"      };   //定義一個二維數組，用來保存要比較的幾個單詞

	printf("排序前的幾個單詞是：\n");   //輸出
	for(int i=0; i<7; i++)
		printf("\t%s\n",a[i]);
	printf("\n\n");


/*-------------------Shell排序---------------------------------------*/
	int n=7;      //單詞的個數
	int h=n/2;
	char temp[20];
	while(h >= 1)
	{
		for(int i=h; i<n; i++)
		{
			strcpy(temp,a[i]);
			
			int j=i;
			while(j >= h   &&   strcmp(temp, a[j-h]) < 0 )
			{
				strcpy(a[j],a[j-h]);
				j-=h;
			}
			strcpy(a[j],temp);
		}
		h/=2;
	}
/*-------------------Shell排序---------------------------------------*/


	printf("按字典順序排序以后的幾個單詞是：\n");  //輸出
	for(i=0; i<7; i++)
		printf("\t%s\n",a[i]);

	_getch();
}