// 一些排序函數模板
#include <iostream>
using namespace System;
// 排序算法 函數模板
// 直接插入排序函數模板
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;
}
}
// 交換位置函數模板
template <class T>
void Swap (T &x, T &y)
{
T temp;
temp = x;
x = y;
y = temp;
}
// 直接選擇排序函數模板
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;
}
}
// 比較函數指針
// 返回值
// 負值: 第一個參數小于第二個參數
// 0 : 相等
// 正值: 第一個參數大于第二個參數
typedef int (*CFT)(const void*, const void*);
// **************************************
// 對向量base的n個元素按照遞增順序排序
// 用由cmp所指的函數做比較
// 元素的大小是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;
}
}
}
}
}
}
// 比較函數
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;
}