shellsort.cpp

来自「是各种常用算法的集合」· C++ 代码 · 共 52 行

//shell排序
#include <iostream.h>
#include <stdlib.h>
#include <time.h>

typedef int ELEM;


void swap(ELEM& a ,ELEM& b){
	ELEM c = b; 
	b = a ;
	a = c ;
}

ELEM key(ELEM a){
	return a;
}
  
void inssort2(ELEM*, int, int);

// Shell 排序
void shellsort(ELEM* array, int n) { 
  for (int i=n/2; i>2; i/=2)   
    for (int j=0; j<i; j++)    
      inssort2(&array[j], n-j, i);
  inssort2(array, n, 1);  
}

void inssort2(ELEM* A, int n, int incr) {
  for (int i=incr; i<n; i+=incr)
    for (int j=i; (j>=incr) && (key(A[j])<key(A[j-incr])); j-=incr)
      swap(A[j], A[j-incr]);
}

void sort(ELEM* array, int n) {
  shellsort(array, n);
}

int main()
{
	int n;
	cout<<"输入数组的大小 ：    ";
	cin>>n;
	ELEM * array = new ELEM[n];
	srand((unsigned) time(NULL));
	for( int i = 0 ; i < n ; i++ )
		array[i] = rand();   //随机生成数
	sort( array , n);
	return 0;
}