/* 
* 實(shí)現(xiàn)了八個(gè)常用的排序算法：插入排序、冒泡排序、選擇排序、希爾排序 
* 以及快速排序、歸并排序、堆排序和LST基數(shù)排序 
* @author gkh178 
*/ 
#include <iostream> 
 
template<class T> 
void swap_value(T &a, T &b) 
{ 
  T temp = a; 
  a = b; 
  b = temp; 
} 
 
//插入排序：時(shí)間復(fù)雜度o(n^2) 
template<class T> 
void insert_sort(T a[], int n) 
{ 
  for (int i = 1; i < n; ++i) 
  { 
    T temp = a[i]; 
    int j = i - 1; 
    while (j >= 0 && a[j] > temp) 
    { 
      a[j + 1] = a[j]; 
      --j; 
    } 
    a[j + 1] = temp; 
  } 
} 
 
//冒泡排序：時(shí)間復(fù)雜度o(n^2)  
template<class T> 
void bubble_sort(T a[], int n) 
{ 
  for (int i = n - 1; i > 0; --i) 
  { 
    for (int j = 0; j < i; ++j) 
    { 
      if (a[j] > a[j + 1]) 
      { 
        swap_value(a[j], a[j + 1]); 
      } 
    } 
  } 
} 
 
//選擇排序：時(shí)間復(fù)雜度o(n^2) 
template<class T> 
void select_sort(T a[], int n) 
{ 
  for (int i = 0; i < n - 1; ++i) 
  { 
    T min = a[i]; 
    int index = i; 
    for (int j = i + 1; j < n; ++j) 
    { 
      if (a[j] < min) 
      { 
        min = a[j]; 
        index = j; 
      } 
    } 
    a[index] = a[i]; 
    a[i] = min; 
  } 
} 
 
//希爾排序：時(shí)間復(fù)雜度介于o(n^2)和o(nlgn)之間  
template<class T> 
void shell_sort(T a[], int n) 
{ 
  for (int gap = n / 2; gap >= 1; gap /= 2) 
  { 
    for (int i = gap; i < n; ++i) 
    { 
      T temp = a[i]; 
      int j = i - gap; 
      while (j >= 0 && a[j] > temp) 
      { 
        a[j + gap] = a[j]; 
        j -= gap; 
      } 
      a[j + gap] = temp; 
    } 
  } 
} 
 
//快速排序：時(shí)間復(fù)雜度o(nlgn)  
template<class T> 
void quick_sort(T a[], int n) 
{ 
  _quick_sort(a, 0, n - 1); 
} 
template<class T> 
void _quick_sort(T a[], int left, int right) 
{ 
  if (left < right) 
  { 
    int q = _partition(a, left, right); 
    _quick_sort(a, left, q - 1); 
    _quick_sort(a, q + 1, right); 
  } 
} 
template<class T> 
int _partition(T a[], int left, int right) 
{ 
  T pivot = a[left]; 
  while (left < right) 
  { 
    while (left < right && a[right] >= pivot) 
    { 
      --right; 
    } 
    a[left] = a[right]; 
    while (left < right && a[left] <= pivot) 
    { 
      ++left; 
    } 
    a[right] = a[left]; 
  } 
  a[left] = pivot; 
  return left; 
} 
 
//歸并排序：時(shí)間復(fù)雜度o(nlgn)  
template<class T> 
void merge_sort(T a[], int n) 
{ 
  _merge_sort(a, 0, n - 1); 
} 
template<class T> 
void _merge_sort(T a[], int left, int right) 
{ 
  if (left < right) 
  { 
    int mid = left + (right - left) / 2; 
    _merge_sort(a, left, mid); 
    _merge_sort(a, mid + 1, right); 
    _merge(a, left, mid, right); 
  } 
} 
template<class T> 
void _merge(T a[], int left, int mid, int right) 
{ 
  int length = right - left + 1; 
  T *newA = new T[length]; 
  for (int i = 0, j = left; i <= length - 1; ++i, ++j) 
  { 
    *(newA + i) = a[j]; 
  } 
  int i = 0; 
  int j = mid - left + 1; 
  int k = left; 
  for (; i <= mid - left && j <= length - 1; ++k) 
  { 
    if (*(newA + i) < *(newA + j)) 
    { 
      a[k] = *(newA + i); 
      ++i; 
    } 
    else 
    { 
      a[k] = *(newA + j); 
      ++j; 
    } 
  } 
  while (i <= mid - left) 
  { 
    a[k++] = *(newA + i); 
    ++i; 
  } 
  while (j <= right - left) 
  { 
    a[k++] = *(newA + j); 
    ++j; 
  } 
  delete newA; 
} 
 
//堆排序：時(shí)間復(fù)雜度o(nlgn)  
template<class T> 
void heap_sort(T a[], int n) 
{ 
  built_max_heap(a, n);//建立初始大根堆  
  //交換首尾元素，并對(duì)交換后排除尾元素的數(shù)組進(jìn)行一次上調(diào)整  
  for (int i = n - 1; i >= 1; --i) 
  { 
    swap_value(a[0], a[i]); 
    up_adjust(a, i); 
  } 
} 
//建立一個(gè)長(zhǎng)度為n的大根堆  
template<class T> 
void built_max_heap(T a[], int n) 
{ 
  up_adjust(a, n); 
} 
//對(duì)長(zhǎng)度為n的數(shù)組進(jìn)行一次上調(diào)整  
template<class T> 
void up_adjust(T a[], int n) 
{ 
  //對(duì)每個(gè)帶有子女節(jié)點(diǎn)的元素遍歷處理，從后到根節(jié)點(diǎn)位置  
  for (int i = n / 2; i >= 1; --i) 
  { 
    adjust_node(a, n, i); 
  } 
} 
//調(diào)整序號(hào)為i的節(jié)點(diǎn)的值  
template<class T> 
void adjust_node(T a[], int n, int i) 
{ 
  //節(jié)點(diǎn)有左右孩子  
  if (2 * i + 1 <= n) 
  { 
    //右孩子的值大于節(jié)點(diǎn)的值，交換它們  
    if (a[2 * i] > a[i - 1]) 
    { 
      swap_value(a[2 * i], a[i - 1]); 
    } 
    //左孩子的值大于節(jié)點(diǎn)的值，交換它們  
    if (a[2 * i - 1] > a[i - 1]) 
    { 
      swap_value(a[2 * i - 1], a[i - 1]); 
    } 
    //對(duì)節(jié)點(diǎn)的左右孩子的根節(jié)點(diǎn)進(jìn)行調(diào)整  
    adjust_node(a, n, 2 * i); 
    adjust_node(a, n, 2 * i + 1); 
  } 
  //節(jié)點(diǎn)只有左孩子，為最后一個(gè)有左右孩子的節(jié)點(diǎn)  
  else if (2 * i == n) 
  { 
    //左孩子的值大于節(jié)點(diǎn)的值，交換它們  
    if (a[2 * i - 1] > a[i - 1]) 
    { 
      swap_value(a[2 * i - 1], a[i - 1]); 
    } 
  } 
} 
 
//基數(shù)排序的時(shí)間復(fù)雜度為o(distance(n+radix)),distance為位數(shù)，n為數(shù)組個(gè)數(shù)，radix為基數(shù)  
//本方法是用LST方法進(jìn)行基數(shù)排序，MST方法不包含在內(nèi)  
//其中參數(shù)radix為基數(shù)，一般為10；distance表示待排序的數(shù)組的數(shù)字最長(zhǎng)的位數(shù)；n為數(shù)組的長(zhǎng)度  
template<class T> 
void lst_radix_sort(T a[], int n, int radix, int distance) 
{ 
  T* newA = new T[n];//用于暫存數(shù)組  
  int* count = new int[radix];//用于計(jì)數(shù)排序，保存的是當(dāng)前位的值為0 到 radix-1的元素出現(xiàn)的的個(gè)數(shù)  
  int divide = 1; 
  //從倒數(shù)第一位處理到第一位  
  for (int i = 0; i < distance; ++i) 
  { 
    //待排數(shù)組拷貝到newA數(shù)組中 
    for (int j = 0; j < n; ++j) 
    { 
      *(newA + j) = a[j]; 
    } 
    //將計(jì)數(shù)數(shù)組置0  
    for (int j = 0; j < radix; ++j) 
    { 
      *(count + j) = 0; 
    } 
    for (int j = 0; j < n; ++j) 
    { 
      int radixKey = (*(newA + j) / divide) % radix; //得到數(shù)組元素的當(dāng)前處理位的值  
      (*(count + radixKey))++; 
    } 
    //此時(shí)count[]中每個(gè)元素保存的是radixKey位出現(xiàn)的次數(shù)  
    //計(jì)算每個(gè)radixKey在數(shù)組中的結(jié)束位置，位置序號(hào)范圍為1-n  
    for (int j = 1; j < radix; ++j) 
    { 
      *(count + j) = *(count + j) + *(count + j - 1); 
    } 
    //運(yùn)用計(jì)數(shù)排序的原理實(shí)現(xiàn)一次排序，排序后的數(shù)組輸出到a[]  
    for (int j = n - 1; j >= 0; --j) 
    { 
      int radixKey = (*(newA + j) / divide) % radix; 
      a[*(count + radixKey) - 1] = newA[j]; 
      --(*(count + radixKey)); 
    } 
    divide = divide * radix; 
  } 
} 

#include "Sort.h" 
using namespace std; 
 
template<class T> 
void printArray(T a[], int n) 
{ 
  for (int i = 0; i < n; ++i) 
  { 
    cout << a[i] << " "; 
  } 
  cout << endl; 
} 
 
int main() 
{ 
  for (int i = 1; i <= 8; ++i) 
  { 
    int arr[] = { 45, 38, 26, 77, 128, 38, 25, 444, 61, 153, 9999, 1012, 43, 128 }; 
    switch (i) 
    { 
    case 1: 
      insert_sort(arr, sizeof(arr) / sizeof(arr[0])); 
      break; 
    case 2: 
      bubble_sort(arr, sizeof(arr) / sizeof(arr[0])); 
      break; 
    case 3: 
      select_sort(arr, sizeof(arr) / sizeof(arr[0])); 
      break; 
    case 4: 
      shell_sort(arr, sizeof(arr) / sizeof(arr[0])); 
      break; 
    case 5: 
      quick_sort(arr, sizeof(arr) / sizeof(arr[0])); 
      break; 
    case 6: 
      merge_sort(arr, sizeof(arr) / sizeof(arr[0])); 
      break; 
    case 7: 
      heap_sort(arr, sizeof(arr) / sizeof(arr[0])); 
      break; 
    case 8: 
      lst_radix_sort(arr, sizeof(arr) / sizeof(arr[0]), 10, 4); 
      break; 
    default: 
      break; 
    } 
    printArray(arr, sizeof(arr) / sizeof(arr[0])); 
  } 
  return 0; 
}