Shell Sort

//header in use


#include <stdio.h>
#include <tchar.h>

#include <stdlib.h>
#include <time.h>
#include <iostream>
using namespace std;

#define MAX 20
int _tmain(int argc, _TCHAR* argv[])
{
	int shellbox[MAX];
	void shellsort(int *, int);
	srand(time(NULL));						//using rand() and time() to build ramdom number vector
	for(int i = 0; i != MAX; i++)
	{
		shellbox[i] = rand() % 1000;
		cout<<shellbox[i]<<' ';
	}
	shellsort(shellbox, MAX);
	cout << endl;
	for(int i = 0; i != MAX; i++)
	{
		cout<<shellbox[i]<<' ';
	}
	
	return 0;
}
void shellsort(int *shell, int max)
{
	int n = (int)max/2;
	int length = 0;											//small vector length in all shell box
	int end = 0;
	int temp;
	while(!(n==0)){											// shell sort start
		length=n*int((max - 1)/n);
///////////////////////////////////////////////////////////////////
		for(int i = 0; i != n; i++){
			end = i +length;
			for(int j = end; j > 0;){
	/////////////////////////////////////////////////////////////////// sort from i to end
				for(int c = i; c < j;){							// c is the change, i is the start, j is the end
					if(shell[c] > shell[c+n]){
						temp = shell[c];
						shell[c] = shell[c+n];
						shell[c+n] = temp;
					}
					c = c +n;
				}
	///////////////////////////////////////////////////////////////////
				j = j - n;
			}
		}
///////////////////////////////////////////////////////////////////
		n=int(n/2);
	}
	return;
}

 

自己实现的shell排序，底层排序用的是冒泡法。

 

the shell sort from Data Srtuctures and Algorithm Analysis in C++

       /**
         * Shellsort, using Shell's (poor) increments.
         */
        template <class Comparable>
        void shellsort( vector<Comparable> & a )
        {
            for( int gap = a.size( ) / 2; gap > 0; gap /= 2 )
                for( int i = gap; i < a.size( ); i++ )
                {
                    Comparable tmp = a[ i ];
                    int j = i;
                    for( ; j >= gap && tmp < a[ j - gap ]; j -= gap )
                        a[ j ] = a[ j - gap ];
                    a[ j ] = tmp;
                }
        }