#ifndef SORT_H
#define SORT_H
#include <iostream>
#include <queue>
using namespace std;
// 1.直接插入排序
template<class ElemType>
void InsertSort(ElemType data[], int n);
// 2.折半插入排序
template<class ElemType>
void BInsertSort(ElemType data[], int n);
// 3.Shell排序
// 對(duì)data數(shù)組中的元素進(jìn)行希爾排序，n為該數(shù)組大小
// increments為增量序列，incrementsLength為增量序列的大小
template<class ElemType>
void ShellSort(ElemType data[],int increments[], int n, int incrementsLength);
// 1.Bubble Sort
template<class ElemType>
void BubbleSort(ElemType data[], int n);
// 2.快速排序
template<class ElemType>
void QuickSort(ElemType data[], int n);
////////////////// 
// Merge Sort
////////////////// 
// 歸并排序
template<class ElemType>
void MergeSort(ElemType data[],int n);
template<class ElemType>
void MergeSortNonRecursion(ElemType data[], int n);
////////////////// 
// Selection sort
////////////////// 
// 簡(jiǎn)單選擇排序
template<class ElemType>
void SelectionSort(ElemType data[], int n);
// 堆排序
template<class ElemType>
void HeapSort(ElemType data[],int n);
///////////////
// Radix Sort
///////////////
// 靜態(tài)鏈表結(jié)點(diǎn)
const int DIGITS = 10;
const int RADIX = 10;
class SLList;
ostream& operator<<(ostream& os, SLList &s);// 由于VC++6.0使用using namespace std對(duì)于友元不支持
      // 故在類SLList之前做前向聲明
      // 若使用其他C++編譯器，這兩句可刪去
// 靜態(tài)鏈表static linked list
// [0]：頭結(jié)點(diǎn)
class SLList
{
 struct Node
 {
 int  key[DIGITS];
 int    info;
 int    next;
 }; 
  
 friend ostream& operator<<(ostream& os, SLList &s);
public:
 SLList():data(NULL),length(0){};
  ~SLList();
 void Arrange();       
  void Init(int arr[],int n);
  void RadixSort();
private:
  void Distribute( int[], int[], int);
 void Collection( int[], int[], int);
  Node *data;
  int length;
};
// 基數(shù)排序
void RadixSort(int data[], int n);
//void RadixSort(SLList&);
///////////////
// util
///////////////
template<class ElemType>
void Swap( ElemType& a, ElemType& b)
{
  ElemType c = a;
  a = b;
  b = c;
}
int init(int** data);
template<class ElemType>
void print(ElemType data[],int begin,int end);
// 直接插入排序,數(shù)組data用于存放待排序元素，n為待排序元素個(gè)數(shù)
template<class ElemType>
void InsertSort(ElemType data[], int n)
{ 
  ElemType tmp;
 int i, j;
  for (i = 1; i < n; i++){
    if ( data[i] > data[i - 1])
      continue;
    tmp = data[i];                // 保存待插入的元素
 data[i] = data[i - 1];
    for ( j = i - 1; j > 0 && data[j - 1] > tmp;j--)
      data[j] = data[j - 1];          // 元素后移
    data[j] = tmp;                // 插入到正確位置    
  }
}
// 折半插入排序
template<class ElemType>
void BInsertSort(ElemType data[], int n)
{ 
  ElemType tmp;
 int i, j, mid, low, high;
  for (i = 1; i < n; i++){
    tmp = data[i];           // 保存待插入的元素
    low = 0;
    high = i-1;
    while (low <= high){        // 在data[low..high]中折半查找有序插入的位置
      mid = (low + high) / 2;      // 折半
      if( tmp < data[mid])
        high = --mid;         // 插入點(diǎn)在低半?yún)^(qū)
      else
        low = ++mid;         // 插入點(diǎn)在高半?yún)^(qū)
    }
    for(j = i - 1; j >= low; j--)
      data[j + 1] = data[j];     // 元素后移
    data[low] = tmp;          // 插入到正確位置
  }
}
// 對(duì)data數(shù)組中的元素進(jìn)行希爾排序，n為該數(shù)組大小
// increments為增量序列，incrementsLength為增量序列的大小
template<class ElemType>
void ShellSort(ElemType data[], int increments[], int n, int incrementsLength)
{
  int i, j, k;
  ElemType tmp;
 for ( k = 0; k < incrementsLength; k++){    // 進(jìn)行以increments[k]為增量的排序
    for ( i = increments[k]; i < n; i++){
      tmp = data[i];
      for ( j = i; j >= increments[k]; j -= increments[k]){
        if ( tmp >= data[j - increments[k]])
          break; 
        data[j] = data[j - increments[k]]; 
      }
      data[j] = tmp;
    }
  }
}
// 冒泡排序
template<class ElemType>
void BubbleSort(ElemType data[], int n)
{
 int lastSwapIndex = n - 1; // 用于記錄最后一次交換的元素下標(biāo)
 int i, j;
  for (i = lastSwapIndex; i > 0;i = lastSwapIndex)
 {
 lastSwapIndex = 0;
 for (j = 0; j < i; j++)
  if (data[j] > data[j + 1]){
        Swap( data[j],data[j + 1]);
  lastSwapIndex = j;
  }
 }
}
//快速排序
template<class ElemType>
int Partition(ElemType data[] , int low , int high)  
{  
  ElemType pivot = data[low];  
  while (low < high){  
    while (low < high && data[high] >= pivot) 
  high--;  
    data[low] = data[high]; 
    while (low < high && pivot >= data[low]) 
  low++;  
    data[high] = data[low];  
  }  
  data[low] = pivot;  
  return low;  
}  
template<class ElemType>
void QuickSort(ElemType data[], int begin, int end)
{ 
  if (begin >= end) 
 return;
  int pivot = Partition(data , begin , end);  
  QuickSort(data , begin , pivot - 1);  
  QuickSort(data , pivot + 1, end);     
}
template<class ElemType>
void QuickSort(ElemType data[], int n)
{
  if (n < 2)
    return;
  QuickSort(data, 0, n-1);
}
// 將數(shù)組data中，[lptr...rptr-1][rptr...rightEnd]兩部分的元素進(jìn)行合并
// tmpArr為合并時(shí)的輔存空間
template<class ElemType>
void Merge(ElemType data[], ElemType tmpArr[], int lptr, int rptr, int rightEnd)
{
  int leftEnd = rptr - 1;
  int ptr,i;
  ptr = i = lptr;
  while (lptr <= leftEnd && rptr <= rightEnd)
    if (data[lptr] <= data[rptr])
      tmpArr[ptr++] = data[lptr++];
    else
      tmpArr[ptr++] = data[rptr++];
  while (lptr <= leftEnd)
    tmpArr[ptr++] = data[lptr++];
  while (rptr <= rightEnd)
    tmpArr[ptr++] = data[rptr++];
  for (;i <= rightEnd; i++)
    data[i] = tmpArr[i];
}
// 遞歸實(shí)現(xiàn)
// 將數(shù)組data中，[begin...end]的元素進(jìn)行歸并排序
template<class ElemType>
void MSort(ElemType data[], ElemType tmpArr[], int begin, int end)
{
  int middle;
  if ( begin >= end)
    return;
  middle = (begin + end)/2;   // 將data平分為[begin..middle]和[middle..end]
  MSort( data, tmpArr, begin, middle);  // 遞歸前半部分
  MSort( data, tmpArr, middle + 1, end);  // 遞歸后半部分
  Merge( data, tmpArr, begin, middle + 1, end); // 將data[begin..middle]，data[middle..end]進(jìn)行歸并
}
template<class ElemType>
void MergeSort(ElemType data[], int n)
{
  ElemType* pArr = NULL;
  pArr = new ElemType[n];
  MSort( data,pArr,0,n-1);
  delete[] pArr;
}
// 非遞歸實(shí)現(xiàn)
template<class ElemType>
void MPass(ElemType data[], ElemType tmpArr[], int n, int mergeLength)
{
 int i = 0;
 while (i <= n - 2 * mergeLength){
 Merge(data, tmpArr, i, i + mergeLength, i + 2 * mergeLength - 1);
 i = i + 2 * mergeLength;
 }
 if (i + mergeLength < n)
 Merge(data, tmpArr, i, i + mergeLength, n - 1);
}
template<class ElemType>
void MergeSortNonRecursion(ElemType data[], int n)
{
 int mergeLength = 1;
 ElemType* pArr = NULL;
 pArr = new ElemType[n];
 while (mergeLength < n){
 MPass(data, pArr, n, mergeLength);
 mergeLength *= 2;
 }
 delete[] pArr;
}
// 簡(jiǎn)單選擇排序
template<class ElemType>
void SelectionSort(ElemType data[], int n)
{
 int i, j, min;
  for (i = 0; i < n; i++){
    min = i;
    for (j = i + 1; j < n; j++){
      if ( data[j] < data[min])
        min = j;
    }
    Swap(data[i],data[min]);
  }
}
// 堆排序
// i為指定元素在數(shù)組中的下標(biāo)
// 返回指定結(jié)點(diǎn)的左孩子在數(shù)組中的下標(biāo)
inline int LeftChild(int i)
{
  return 2 * i + 1;
}
template<class ElemType>
void HeapAdjust(ElemType data[], int i, int n)
{
  ElemType tmp;
  int child;
  for ( tmp = data[i]; LeftChild(i) < n; i = child){
    child = LeftChild(i);
    if (child != n - 1 && data[child + 1] > data[child])  // 取較大的孩子結(jié)點(diǎn)
      child++;
    if (tmp < data[child])                
      data[i] = data[child];
    else
      break;
  }
  data[i] = tmp;
}
template<class ElemType>
void HeapSort(ElemType data[], int n)
{
  int i;
  for (i = n/2; i >= 0; i--)  // 建堆
    HeapAdjust(data, i, n);
  for (i = n - 1;i > 0; i--){  // 將堆的根結(jié)點(diǎn)與最后的一個(gè)葉結(jié)點(diǎn)交換,并進(jìn)行調(diào)整
    Swap(data[0],data[i]);
    HeapAdjust(data, 0, i);
  }
}
// 用數(shù)組實(shí)現(xiàn)的基數(shù)排序
void RadixSort(int data[], int n)
{
  const int radix = 10;
  const int digits = 10;
  int i,j,k,factor;
 queue<int> queues[radix];
  for ( i = 0,factor = 1; i < digits;i++,factor *= radix){
    for ( j = 0;j < n; j++)
      queues[(data[j]/factor)%radix].push(data[j]);    // 分配
    for ( k = j = 0; j < radix; j++,k++)          // 收集
      while (!queues[j].empty()){
        data[k] = queues[j].front();
        queues[j].pop();
      }
  }
}
// 分配
void SLList::Distribute(int front[], int rear[], int digit)
{
 int i, index;
 for (i = 0; i < RADIX; i++)
 front[i] = 0;
 for (i = data[0].next; i > 0; i = data[i].next){
 index = data[i].key[digit];
 if (front[index] == 0)
  front[index] = i;
 else
  data[rear[index]].next = i;
 rear[index] = i;
 }
}
// 收集
void SLList::Collection(int front[], int rear[], int digit)
{
 int i, current;
 for (i = 0; front[i] == 0; i++); // 找到第一個(gè)非空子表
 data[0].next = front[i];  // 頭結(jié)點(diǎn)指向第一個(gè)非空子表中第一個(gè)結(jié)點(diǎn)
 current = rear[i++];
 for (; i < RADIX; i++){
 if (front[i] == 0)
  continue;
 data[current].next = front[i]; // 鏈接兩個(gè)非空子表
 current = rear[i];
 }
 data[current].next = 0;
}
// 用SLList實(shí)現(xiàn)的基數(shù)排序
void SLList::RadixSort()
{
  int i;
  int front[RADIX],rear[RADIX];
  // 從最低位優(yōu)先依次對(duì)各關(guān)鍵字進(jìn)行分配收集
  for ( i = 0; i < DIGITS; i++){
    Distribute(front, rear, i);
    Collection(front, rear, i);    
  }
}
SLList::~SLList()
{
  delete[] data;
  length = 0;
}
void SLList::Init(int arr[], int n)
{
  length = n + 1;
  if (data != NULL)
    delete[] data;
  data = new Node[n + 1];
  data[0].next = 1;
  for ( int i = 1; i <= n; i++){
    int value = data[i].info = arr[i - 1];
    for (int j = 0;j < 10; j++){
      data[i].key[j] = value % 10;// + '0';
      value /= 10;
    }
    data[i].next = i + 1;
  }
  data[n].next = 0;
}
// 根據(jù)鏈表中各結(jié)點(diǎn)的指針值調(diào)整元素位置，使得SLList中元素按關(guān)鍵字正序排列
void SLList::Arrange()
{
 int i, tmp;
 int current = data[0].next;   // current存放第一個(gè)元素的當(dāng)前位置
 for (i = 1; i < length; i++){
 while (current < i)   // 找到第i個(gè)元素，并用current存放其在靜態(tài)鏈表中當(dāng)前位置
  current = data[current].next;
 tmp = data[current].next;
 if (current != i){
  Swap(data[current], data[i]); // 第i個(gè)元素調(diào)整到位
  data[i].next = current;  // 指向被移走的元素
 }
 current = tmp;    // 為找第i + 1個(gè)元素做準(zhǔn)備
 }
}
ostream& operator<<(ostream& os,SLList &s)
{
 for (int i = 1; i < s.length; i++)
 cout << s.data[i].info << " ";
 os << endl;
 return os;
}
#endif