shsort3.cpp

数据结构中排序的实例分析

#include <iostream.h>
#include "..\include\book.h"

typedef int ELEM;
#include "..\include\swap.h"
  
// Shell sort
// Modified version of Insertion Sort for varying increments
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 shellsort(ELEM* array, int n) {
  for (int firstincr = 1; firstincr<=n; firstincr = firstincr*3 + 1);
  for (int i=firstincr/3; i>2; i/=3)
    for (int j=0; j<i; j++)
      inssort2(&array[j], n-j, i);
  inssort2(array, n, 1);    // Could call regular inssort
}

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