#include <cstdlib> #include <iostream> using namespace std; #define SELECTSORT      1 #define INSERTSORT      1 #define BUBBLESORT      1 #define SHELLSORT       1 #define QUICKSORT       1 #define MERGESORT       1 template<typename T> void print(T array[], int len) {     for (int i=0; i<len; i++) {         cout<<array[i]<<" ";        }     cout<<endl; } template<typename T> void Swap(T& a, T& b) {     T temp = a;     a = b;     b = temp;    } #ifdef SELECTSORT template<typename T> void SelectSort(T array[], int len) {     int i = 0;     int j = 0;     int k = -1;     for (i=0; i<len; i++) {         k = i;         for (j=i+1; j<len; j++) {             if (array[j] < array[k]) {                 k = j;                }            }          if (k != i) {             swap(array[i], array[k]);          }     }    } #endif #ifdef INSERTSORT template<typename T> void InsertSort(T array[], int len) {     int i = 0;     int j = 0;     int k = -1;     int temp = -1;     for (i=1; i<len; i++) {         k = i;         temp = array[k];         for (j=i-1; (j>=0)&&(array[j]>temp); j--) {             array[j+1] = array[j];             k = j;         }            array[k] = temp;     }    } #endif #ifdef BUBBLESORT template<typename T> void BubbleSort(T array[], int len) {     int i = 0;     int j = 0;     int exchange = 1;     for (i=0; i<len && exchange; i++) {         exchange = 0;         for (j=len-1; j>0; j--) {             if (array[j] < array[j-1]) {                 Swap(array[j], array[j-1]);                 exchange = 1;             }            }        }    } #endif #ifdef SHELLSORT template<typename T> void ShellSort(T array[], int len) {     int i = 0;     int j = 0;     int k = 0;     int temp = 0;     int gap = len;     do {         gap = gap / 3 + 1;         for (i=gap; i<len; i+=gap) {             k = i;             temp = array[k];             for (j=i-gap; j>=0&&array[j]>temp; j-=gap) {                 array[j+gap] = array[j];                 k = j;                }             array[k] = temp;            }     } while (gap > 1); } #endif #ifdef QUICKSORT template<typename T> int parition(T array[], int low, int high) {     int pv = array[low];     while (low < high) {         while ((low<high) && (array[high] >= pv)) {             high--;            }            Swap(array[low], array[high]);         while ((low<high) && (array[low] <= pv)) {             low++;            }         Swap(array[low], array[high]);     }     return low; } template<typename T> void QSort(T array[], int low, int high) {     if (low < high) {         int part = parition(array, low, high);         QSort(array, low, part-1);   //可以理解为左边数列         QSort(array, part+1, high);  //可以理解为右边数列       }    } template<typename T> void QuickSort(T array[], int len) {     QSort(array, 0, len-1);        } #endif #ifdef MERGESORT template<typename T> void Merge(T src[], T des[], int low, int mid, int high) {     int i = low;     int j = mid+1;     int k = low;     while (i<=mid && j<=high) {         if (src[i] < src[j]) {             des[k++] = src[i++];            } else {             des[k++] = src[j++];            }     }      while (i<=mid) {         des[k++] = src[i++];        }      while (j<=high) {         des[k++] = src[j++];        } } template<typename T> void MSort(T src[], T des[], int low, int high, int max) {     if (low == high) {         des[low] = src[low];        } else {         int mid = (low + high) / 2;         T *space = (T *)malloc(sizeof(T)*max);         if (space != NULL) {             MSort(src, space, low, mid, max);             MSort(src, space, mid+1, high, max);              Merge(space, des, low, mid, high);         }         free(space);         space = NULL;     }      } template<typename T> void MergeSort(T array[], int len) {     MSort(array, array, 0, len-1, len); } #endif