用C++程序实现shell排序

Shell排序是插入排序的一般化，其中与插入排序不同，借助元素'gap'可以交换far元素，并使列表进行缺口排序，我们将不断减少缺口，直到缺口变为1，这意味着最后一步将是正常的插入排序。

算法：

步骤1：初始化gap的值。

步骤2：将列表分为等间隔的较小子列表。

步骤3：使用插入排序对每个子列表进行排序。

步骤4：重复操作，直到列表排序完毕。

考虑给定的程序：

#include<iostream>
using namespace std;

/*Method to sort the list/array*/
void shellSort(int sort[],int size)      
{
	for(int gap=size/2;gap>0;gap/=2)
	{
		for(int i=gap;i<size;i++)
		{
			int temp=sort[i];
			int j;
			for(j=i; j>=gap && sort[j-gap]>temp; j-=gap)
			{
				sort[j]=sort[j-gap];
			}
			sort[j]=temp;
		}
	}	
}

//主程序
int main(){
	int size;               

	cout<<"Enter the size of the array :";
	cin>>size;

	int sort[size];
	for(int i=0;i<size;i++)
	{
		cin>>sort[i];
	}

	shellSort(sort,size);

	cout<<"Array after sorting is :";
	for(int i=0;i<size;i++)
	{
		cout<<sort[i]<<" ";
	}

	cout<<endl;
	
	return 0;
}

输出结果

FIRST INPUT:
Enter the size of the array :6
87 15 34 99 56 44
Array after sorting is :15 34 44 56 87 99

SECOND INPUT :
Enter the size of the array :10
13 54 36 87 36 42 11 68 91 9
Array after sorting is :9 11 13 36 36 42 54 68 87 91