shellsort(希尔排序).cpp

希尔排序 希尔排序是一种不稳定的排序算法

// shellsort(希尔排序).cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<iostream>
#include<fstream>
#include<assert.h>

using namespace std;

typedef struct node
{
	int key;
	int oth;
}node;
void shellsort(node r[],int n);

int _tmain(int argc, _TCHAR* argv[])
{
    	node s[11];
	ifstream infile("D:\\1.txt");
	assert(infile);
	for(int i=1;i<11;i++)
		infile>>s[i].key;
	ofstream outfile("D:\\1.txt",ios_base::app);
	assert(outfile);
	
	shellsort(s,10);
	outfile<<endl;
	for(int i=1;i<11;i++)
		outfile<<s[i].key<<' ';
	outfile<<endl;
	return 0;
}


void shellsort(node r[],int n)///希尔排序是属于插入排序的一种，是不稳定的，因为相同的关键字会在排序前后的前后位置发生变化，所以是不稳定的排序，而直接插入排序和折半插入排序都是稳定的排序
{
	int k=n/2;
	int i,j;
	while(k>=1)
	{
		for(i=k+1;i<=n;i++)
		{
			j=i-k;
			r[0]=r[i];
			while(r[j].key>r[0].key&&j>=0){r[j+k]=r[j];j-=k;}
			r[j+k]=r[0];
		}
		k/=2;
	}
}