/* * 實現了八個常用的排序算法：插入排序、冒泡排序、選擇排序、希爾排序 * 以及快速排序、歸并排序、堆排序和LST基數排序 * @author gkh178 */ #include <iostream>  template<class T> void swap_value(T &a, T &b) {   T temp = a;   a = b;   b = temp; }  //插入排序：時間復雜度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;   } }  //冒泡排序：時間復雜度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]);       }     }   } }  //選擇排序：時間復雜度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;   } }  //希爾排序：時間復雜度介于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;     }   } }  //快速排序：時間復雜度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; }  //歸并排序：時間復雜度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; }  //堆排序：時間復雜度o(nlgn)  template<class T> void heap_sort(T a[], int n) {   built_max_heap(a, n);//建立初始大根堆    //交換首尾元素，并對交換后排除尾元素的數組進行一次上調整    for (int i = n - 1; i >= 1; --i)   {     swap_value(a[0], a[i]);     up_adjust(a, i);   } } //建立一個長度為n的大根堆  template<class T> void built_max_heap(T a[], int n) {   up_adjust(a, n); } //對長度為n的數組進行一次上調整  template<class T> void up_adjust(T a[], int n) {   //對每個帶有子女節點的元素遍歷處理，從后到根節點位置    for (int i = n / 2; i >= 1; --i)   {     adjust_node(a, n, i);   } } //調整序號為i的節點的值  template<class T> void adjust_node(T a[], int n, int i) {   //節點有左右孩子    if (2 * i + 1 <= n)   {     //右孩子的值大于節點的值，交換它們      if (a[2 * i] > a[i - 1])     {       swap_value(a[2 * i], a[i - 1]);     }     //左孩子的值大于節點的值，交換它們      if (a[2 * i - 1] > a[i - 1])     {       swap_value(a[2 * i - 1], a[i - 1]);     }     //對節點的左右孩子的根節點進行調整      adjust_node(a, n, 2 * i);     adjust_node(a, n, 2 * i + 1);   }   //節點只有左孩子，為最后一個有左右孩子的節點    else if (2 * i == n)   {     //左孩子的值大于節點的值，交換它們      if (a[2 * i - 1] > a[i - 1])     {       swap_value(a[2 * i - 1], a[i - 1]);     }   } }  //基數排序的時間復雜度為o(distance(n+radix)),distance為位數，n為數組個數，radix為基數  //本方法是用LST方法進行基數排序，MST方法不包含在內  //其中參數radix為基數，一般為10；distance表示待排序的數組的數字最長的位數；n為數組的長度  template<class T> void lst_radix_sort(T a[], int n, int radix, int distance) {   T* newA = new T[n];//用于暫存數組    int* count = new int[radix];//用于計數排序，保存的是當前位的值為0 到 radix-1的元素出現的的個數    int divide = 1;   //從倒數第一位處理到第一位    for (int i = 0; i < distance; ++i)   {     //待排數組拷貝到newA數組中     for (int j = 0; j < n; ++j)     {       *(newA + j) = a[j];     }     //將計數數組置0      for (int j = 0; j < radix; ++j)     {       *(count + j) = 0;     }     for (int j = 0; j < n; ++j)     {       int radixKey = (*(newA + j) / divide) % radix; //得到數組元素的當前處理位的值        (*(count + radixKey))++;     }     //此時count[]中每個元素保存的是radixKey位出現的次數      //計算每個radixKey在數組中的結束位置，位置序號范圍為1-n      for (int j = 1; j < radix; ++j)     {       *(count + j) = *(count + j) + *(count + j - 1);     }     //運用計數排序的原理實現一次排序，排序后的數組輸出到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; }