// 一些排序函數(shù)模板

#include <iostream>
using namespace System;

// 排序算法 函數(shù)模板

// 直接插入排序函數(shù)模板
template <class T>
void InsertionSort(T A[], int n)
{  int i, j;
   T   temp;
   for (i = 1; i < n; i++)
   {  j = i;
      temp = A[i];
      while (j > 0 && temp < A[j-1])
      {  A[j] = A[j-1];   
         j--;
      }
     A[j] = temp;
   }
}

// 交換位置函數(shù)模板
template <class T>
void Swap (T &x, T &y)
{
 T temp;
 temp = x;
 x = y;
 y = temp;
}

// 直接選擇排序函數(shù)模板
template <class T>
void SelectionSort(T A[], int n)
{  int smallIndex;   
   int i, j;
   for (i = 0; i < n-1; i++)
   {  smallIndex = i;   
      for (j = i+1; j < n; j++)
         if (A[j] < A[smallIndex])
            smallIndex = j;
      Swap(A[i], A[smallIndex]);
   }
}

// 交換排序方法——起泡排序
template <class T>
void BubbleSort(T A[], int n)
{ 
 int i,j;            
 int lastExchangeIndex;
 i = n-1;     
 while (i > 0)
 { 
  lastExchangeIndex = 0; 
  for (j = 0; j < i; j++)
  {
   if (A[j+1] < A[j])
   {
    Swap(A[j],A[j+1]);
    lastExchangeIndex = j;    
   }
  }
  i = lastExchangeIndex;
 }
}

// 比較函數(shù)指針
// 返回值
//     負值: 第一個參數(shù)小于第二個參數(shù)
//    0   : 相等
//    正值: 第一個參數(shù)大于第二個參數(shù)
typedef int (*CFT)(const void*, const void*);

// **************************************
// 對向量base的n個元素按照遞增順序排序
// 用由cmp所指的函數(shù)做比較
// 元素的大小是sz
// Shell排序
// **************************************
void ssort(void* base, size_t n, size_t sz, CFT cmp)
{
 for (int gap=n/2; 0<gap; gap/=2)
 {
  for (int i=gap; i<n; i++)
  {
   for (int j=i-gap; 0<=j; j-=gap)
   {
    char* b = static_cast<char*>(base);  // 必須強制
    char* pj = b+j*sz;      // &base[j]
    char* pjg = b+(j+gap)*sz;    // &base[j+gap]
    if (cmp(pjg, pj) < 0)
    {
     // 交換base[j]與base[j+gap]
     for (int k=0; k<sz; k++)
     {
      char temp = pj[k];
      pj[k] = pjg[k];
      pjg[k] = temp;
     }
    }
   }
  }
 }
}

// 比較函數(shù)
int compare_int(const void* arg1, const void* arg2)
{
 if (*(int*)arg1 < *(int*)arg2) return -1;
 if (*(int*)arg1 == *(int*)arg2) return 0;
 if (*(int*)arg1 > *(int*)arg2) return 1;
}

void main()
{
 const int MAXSIZE = 20;
 int* iA = new int[MAXSIZE];
 Random* random = new Random;
 for (int i=0; i<MAXSIZE; i++)
 {
  iA[i] = random->Next(100);
 }
 //InsertionSort(iA, 8);
 ssort(iA, MAXSIZE, sizeof(int), compare_int);
 for (int i=0; i<MAXSIZE; i++)
 {
  std::cout<< iA[i] << " ";
 }

 int x;
 std::cin>>x;

}