[C/C++ 演算法]-資料結構與演算法(文魁)：謝爾排序

[C/C++ 演算法]-資料結構與演算法(文魁)：謝爾排序

 

線上執行結果：http://www.tutorialspoint.com/compile_c_online.php 

 

/* =============== Program Description =============== */
/* 程式名稱 : 6_6.cpp				       */				
/* 程式目的 : 謝爾排序				       */
/* 輸    入 : 排序前的整數陣列資料		       */
/* 輸    出 : 排序後的整數陣列資料		       */
/* =================================================== */
#define n 20

// 宣告標頭檔
#include "stdio.h"


// 宣告函式原型

// 利用傳址的方式把Array A傳進shell_sort函式中
void shell_sort(int *A);


void main(void)
{
	int i;
	int A[n]={1,21,0,47,60,
		   15,84,65,77,88,
		   100,93,8,17,36,
		   5,24,63,72,20};

	// 排序前的資料
	printf(" Data before sorting \n");
	for(i=0;i<n;i++)
		printf("%d",A[i]);
	printf("\n");
	
	shell_sort(A);
	
	// 排序後的資料
	printf(" Data after sorting \n");

	for(i=0;i<n;i++)
		printf("%d",A[i]);
	printf("\n");

	getchar();

}

void shell_sort(int *A)
{  	
	int i,j,x,hcount,hgroup;
	// hcount:每個群組的間隔
	for (hcount = 2 ; hcount < (n/2) ; hcount=hcount*2)	
	{			
		// 對個別的群組作插入排序
		for (hgroup = 1 ; hgroup <= hcount-1 ; hgroup++)	
		{			
			// 插入排序
			for (i = hgroup ; i <= n-1 ; i+=hcount)
			{					
				x=A[i];
				j=i-hcount;
		
				while (j>=0 && A[j]>x)
				{		
					A[j+hcount] = A[j];
					j-=hcount;			
				}
		
				A[j+hcount]=x;
			}	
		}
	}

	// 最後再作一次插入排序
	for (i = 1 ; i <= n-1 ; i++)
	{					
		x=A[i];
		j=i-1;

		while (j>=0 && A[j]>x)
		{		
			A[j+1] = A[j];
			j--;			
		}

		A[j+1]=x;
	}	

}