希尔排序(ShellSort 改进后的插入排序) -- C++实现


实现代码

// ShellSort.h
#ifndef SHELLSORT_H
#define SHELLSORT_H

#include<iostream>
using namespace std;

#include "Component.h"

namespace jay{

	template< typename T >
	void ShellSort(T *input,int input_len )
	{
		// 当前分组间隔
		int nInterval(1);
		while (nInterval < input_len/3) 
		{
			nInterval = 3*nInterval + 1;
		}
		// nComponentCount此时指向第一个分组的最后一个元素,然后向前比较

		// 当nComponentCount=1的时候就是普通的插入排序
		while (nInterval >= 1)
		{
			for (int i=nInterval;i<input_len;i++)
			{
				for (int j=i;j>=nInterval && input[j] < input[j-nInterval];j -= nInterval)
				{
					ExchangeArrayElements<T>(input,j,j-nInterval);
				}
			}

            // 分组元素间距缩小为原来的1/3
			nInterval /= 3;
		}

	}

};

#endif

测试代码

//main.cpp

#include <time.h>
#include<windows.h>

#include <iostream>
using namespace std;

#include "Component.h"
#include "SelectSort.h"
#include "InsertionSort.h"
#include "ShellSort.h"
using namespace jay;


int main(int argc, char* argv[])
{
	TimeCalculator timec;

	int iElentmentsCunt(0) ;
	cin>>iElentmentsCunt;
	int *testarray = new int[iElentmentsCunt];

	int iCount = 0;
	int p;
	while(cin>>p)
	{
		testarray[iCount] = p;
		iCount++;
	}

	PrintArray<int>(testarray,iCount,"排序前:");
	ShellSort<int>(testarray,iCount);
	PrintArray<int>(testarray,iCount,"排序后:");

	delete []testarray;

	// 打印操作耗时
	timec.PrintTimeInfo();

}

 

暂无评论

注册用户登录后才能发表或者回复评论,请先登录 注册。