希尔排序
设置“监视哨”，写希尔排序，给出详细注释说明，求助各位！
/*希尔排序(SHELL SORT),又称缩小增量排序(diminishing-increment sort)
基本思想:设待排序元素序列有N个元素,首先取出一个整数gap<n作为间隔,将全部元素分为gap
个字序列,所有距离为gap的元素放在同一个子序列中,在每一个子序列中分别施行直接插入排序.
然后缩小间隔gap,直到gap等于 1
*/
/*****************************************************************
** HighlightCodeV3.0 software by yzfy(雨中飞燕) http:// **
*****************************************************************/
#include<iostream>
#include<ctime>
const int MAXSIZE = 30;
int array[MAXSIZE];
void ShellSort(int (&array)[MAXSIZE],const int left,const int right)
{
int gap = right-left+1; //增量的初始值
do
{
gap = gap/3 + 1; // 求下一增量
for (int i=left+gap;i<=right;i++) //各子充列交错处理
if (array[i] < array[i-gap]) //逆序
{
int temp = array[i], j = i-gap;
do
{
array[j+gap] = array[j]; //后移元素
j = j-gap; //现比较前一元素
}while (j>left &&temp < array[j]);
}
}while (gap > 1);
}
int main(void)
{
srand(unsigned(time(NULL)));
for (int i=0;i<MAXSIZE;i++)
array[i] = rand()%10000;
std::cout<<std::endl<<"***希尔排序(SHELL SORT)***"<<std::endl;
ShellSort(array,0,MAXSIZE);
display(array,MAXSIZE);
return 0;
}[/size][/font]
** HighlightCodeV3.0 software by yzfy(雨中飞燕) http:// **
*****************************************************************/
#include<iostream>
#include<ctime>
const int MAXSIZE = 30;
int array[MAXSIZE];
void ShellSort(int (&array)[MAXSIZE],const int left,const int right)
{
int gap = right-left+1; //增量的初始值
do
{
gap = gap/3 + 1; // 求下一增量
for (int i=left+gap;i<=right;i++) //各子充列交错处理
if (array[i] < array[i-gap]) //逆序
{
int temp = array[i], j = i-gap;
do
{
array[j+gap] = array[j]; //后移元素
j = j-gap; //现比较前一元素
}while (j>left &&temp < array[j]);
}
}while (gap > 1);
}
int main(void)
{
srand(unsigned(time(NULL)));
for (int i=0;i<MAXSIZE;i++)
array[i] = rand()%10000;
std::cout<<std::endl<<"***希尔排序(SHELL SORT)***"<<std::endl;
ShellSort(array,0,MAXSIZE);
display(array,MAXSIZE);
return 0;
}[/size][/font]
[[it] 本帖最后由 很远的那颗星 于 2008-8-1 11:33 编辑 [/it]]
