#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排序// 對data數組中的元素進行希爾排序，n為該數組大小// increments為增量序列，incrementsLength為增量序列的大小template<class ElemType>void ShellSort(ElemType data[],int increments[], int n, int incrementsLength);// 1.Bubble Sorttemplate<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////////////////// // 簡單選擇排序template<class ElemType>void SelectionSort(ElemType data[], int n);// 堆排序template<class ElemType>void HeapSort(ElemType data[],int n);///////////////// Radix Sort///////////////// 靜態鏈表結點const int DIGITS = 10;const int RADIX = 10;class SLList;ostream& operator<<(ostream& os, SLList &s);// 由于VC++6.0使用using namespace std對于友元不支持      // 故在類SLList之前做前向聲明      // 若使用其他C++編譯器，這兩句可刪去// 靜態鏈表static linked list// [0]：頭結點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;};// 基數排序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);// 直接插入排序,數組data用于存放待排序元素，n為待排序元素個數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;         // 插入點在低半區      else        low = ++mid;         // 插入點在高半區    }    for(j = i - 1; j >= low; j--)      data[j + 1] = data[j];     // 元素后移    data[low] = tmp;          // 插入到正確位置  }}// 對data數組中的元素進行希爾排序，n為該數組大小// 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++){    // 進行以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; // 用于記錄最后一次交換的元素下標 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);}// 將數組data中，[lptr...rptr-1][rptr...rightEnd]兩部分的元素進行合并// tmpArr為合并時的輔存空間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];}// 遞歸實現// 將數組data中，[begin...end]的元素進行歸并排序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]進行歸并}template<class ElemType>void MergeSort(ElemType data[], int n){  ElemType* pArr = NULL;  pArr = new ElemType[n];  MSort( data,pArr,0,n-1);  delete[] pArr;}// 非遞歸實現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;}// 簡單選擇排序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為指定元素在數組中的下標// 返回指定結點的左孩子在數組中的下標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])  // 取較大的孩子結點      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--){  // 將堆的根結點與最后的一個葉結點交換,并進行調整    Swap(data[0],data[i]);    HeapAdjust(data, 0, i);  }}// 用數組實現的基數排序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++); // 找到第一個非空子表 data[0].next = front[i];  // 頭結點指向第一個非空子表中第一個結點 current = rear[i++]; for (; i < RADIX; i++){ if (front[i] == 0)  continue; data[current].next = front[i]; // 鏈接兩個非空子表 current = rear[i]; } data[current].next = 0;}// 用SLList實現的基數排序void SLList::RadixSort(){  int i;  int front[RADIX],rear[RADIX];  // 從最低位優先依次對各關鍵字進行分配收集  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;}// 根據鏈表中各結點的指針值調整元素位置，使得SLList中元素按關鍵字正序排列void SLList::Arrange(){ int i, tmp; int current = data[0].next;   // current存放第一個元素的當前位置 for (i = 1; i < length; i++){ while (current < i)   // 找到第i個元素，并用current存放其在靜態鏈表中當前位置  current = data[current].next; tmp = data[current].next; if (current != i){  Swap(data[current], data[i]); // 第i個元素調整到位  data[i].next = current;  // 指向被移走的元素 } current = tmp;    // 為找第i + 1個元素做準備 }}ostream& operator<<(ostream& os,SLList &s){ for (int i = 1; i < s.length; i++) cout << s.data[i].info << " "; os << endl; return os;}#endif