#ifndef SORT_H
#define SORT_H
#include 
#include 
using namespace std;
// 1.直接插入排序
template
void InsertSort(ElemType data[], int n);
// 2.折半插入排序
template
void BInsertSort(ElemType data[], int n);
// 3.Shell排序
// 对data数组中的元素进行希尔排序，n为该数组大小
// increments为增量序列，incrementsLength为增量序列的大小
template
void ShellSort(ElemType data[],int increments[], int n, int incrementsLength);
// 1.Bubble Sort
template
void BubbleSort(ElemType data[], int n);
// 2.快速排序
template
void QuickSort(ElemType data[], int n);
////////////////// 
// Merge Sort
////////////////// 
// 归并排序
template
void MergeSort(ElemType data[],int n);
template
void MergeSortNonRecursion(ElemType data[], int n);
////////////////// 
// Selection sort
////////////////// 
// 简单选择排序
template
void SelectionSort(ElemType data[], int n);
// 堆排序
template
void HeapSort(ElemType data[],int n);
///////////////
// Radix Sort
///////////////
// 静态链表结点
const int DIGITS = 10;
const int RADIX = 10;
class SLList;
ostream& operator= increments[k]; j -= increments[k]){
        if ( tmp >= data[j - increments[k]])
          break; 
        data[j] = data[j - increments[k]]; 
      }
      data[j] = tmp;
    }
  }
}
// 冒泡排序
template
void BubbleSort(ElemType data[], int n)
{
 int lastSwapIndex = n - 1; // 用于记录最后一次交换的元素下标
 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
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
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
void QuickSort(ElemType data[], int n)
{
  if (n < 2)
    return;
  QuickSort(data, 0, n-1);
}
// 将数组data中，[lptr...rptr-1][rptr...rightEnd]两部分的元素进行合并
// tmpArr为合并时的辅存空间
template
void Merge(ElemType data[], ElemType tmpArr[], int lptr, int rptr, int rightEnd)
{
  int leftEnd = rptr - 1;
  int ptr,i;
  ptr = i = lptr;
  while (lptr