1 /*  2 * Copyright 2016 E-Tool, Inc.  3 */  4   5 #ifndef sort_h  6 #define sort_h  7   8 #include <vector>  9 #include <math.h> 10 using std::vector; 11 template <typename T> 12  13 class Sort { 14 public: 15     /* 16     *  Selection Sort 17     */ 18     static void selection_sort(vector<T> &arr) { 19         int i, j; 20         for (i = 0;i < arr.size() - 1;i++) { 21             int min = i; 22             for (j = i + 1;j < arr.size();j++) { 23                 if (arr[j] < arr[min]) 24                     min = j; 25             } 26             if (min != i) { 27                 arr[min] = arr[min] + arr[i]; 28                 arr[i] = arr[min] - arr[i]; 29                 arr[min] = arr[min] - arr[i]; 30             } 31         } 32     } 33     /* 34     *  Swap Sort 35     */ 36     static void swap_sort(vector<T> &arr) { 37         int i, j; 38         for (i = 0;i < arr.size();i++) { 39             for (j = 0;j < arr.size() - i - 1;j++) { 40                 if (arr[j + 1] < arr[j]) { 41                     arr[j + 1] = arr[j + 1] + arr[j]; 42                     arr[j] = arr[j + 1] - arr[j]; 43                     arr[j + 1] = arr[j + 1] - arr[j]; 44                 } 45             } 46         } 47     } 48     /* 49     *  Insert Sort 50     */ 51     static void insert_sort(vector<T> &arr) { 52         int i, j; 53         for (i = 0;i < arr.size();i++) { 54             T tmp = arr[i]; 55             j = i - 1; 56             while (j >= 0 && arr[j] > tmp) { 57                 arr[j + 1] = arr[j]; 58                 j--; 59             } 60             arr[j + 1] = tmp; 61         } 62     } 63     /* 64     *  Quick Sort 65     */ 66     static void once_quick_sort(vector<T> &arr, int low, int high) { 67         if (low >= high) return; 68         T tmp = arr[low]; 69         int first = low, last = high; 70         while (first != last) { 71             while (first < last&&arr[last] >= tmp) { 72                 last--; 73             } 74             arr[first] = arr[last]; 75             while (first < last&&arr[first] <= tmp) { 76                 first++; 77             } 78             arr[last] = arr[first]; 79         } 80         arr[first] = tmp; 81         once_quick_sort(arr, low, first - 1); 82         once_quick_sort(arr, first + 1, high); 83     } 84     static void quick_sort(vector<T> &arr) { 85         once_quick_sort(arr, 0, arr.size() - 1); 86     } 87  88     /* 89     *  Heap Sort 90     */ 91     static void heap_adjust(vector<T> &arr, int i, int nLength) {//MAX Heap 92         int nChild; 93         for (;2 * i + 1 < nLength;i = nChild) { 94             nChild = 2 * i + 1; 95             if (nChild<nLength - 1 && arr[nChild + 1]>arr[nChild]) 96                 ++nChild; 97             if (arr[i] < arr[nChild]) { 98                 arr[i] = arr[nChild] ^ arr[i]; 99                 arr[nChild] = arr[nChild] ^ arr[i];100                 arr[i] = arr[nChild] ^ arr[i];101             }102             else break;103         }104     }105     static void heap_sort(vector<T> &arr) {106         int i;107         for (i = arr.size() / 2 - 1;i >= 0;--i) //Construction of the heap108             heap_adjust(arr, i, arr.size());109         for (i = arr.size() - 1;i > 0;--i) { //Adjust the heap110             arr[i] = arr[0] ^ arr[i];111             arr[0] = arr[0] ^ arr[i];112             arr[i] = arr[0] ^ arr[i];113             heap_adjust(arr, 0, i);114         }115     }116     /*117     *  Shell Sort118     */119     static void shell_sort(vector<T> &arr) {120         int i, j, k;121         int t = int(log(arr.size() + 1) / log(2));122         for (i = 1;i <=t;i++) {123             int dk = int(pow(2, t - i + 1)-1);124             for (j = dk;j < arr.size();j++) {125                 int temp=arr[j];126                 for (k = j - dk;(k >= j%dk) && arr[k] > temp;k-=dk) {127                     arr[k + dk] = arr[k];128                 }129                 if (k != j - dk) {130                     arr[k + dk] = temp;131                 }132             }133         }134     }135     /*136     *  Binary Insert Sort137     */138     static void binary_insert_sort(vector<T> &arr) {139         int i, j;140         for (i = 1;i < arr.size();i++) {141             T tmp = arr[i];142             int low=0, high=i-1;143             while (low <= high) {144                 int mid = (low + high) / 2;145                 if (arr[i] <= arr[mid])146                     high = mid-1;147                 else low = mid+1;148             }149             j = i - 1;150             while (j >= low) {151                 arr[j + 1] = arr[j];152                 j--;153             }154             arr[low] = tmp;155         }156     }157     /*158     *  Radix Sort159     */160     static void radix_sort(vector<T> &arr) {161         int d;162         vector<T> tmp(arr.size());163         vector<int> count(10);164         int i, j, k;165         int radix = 1;166         bool state ;167         for (i = 1;;i++) {168             state = false;169             for (j = 0;j < 10;j++) {170                 count[j] = 0;171             }172             for (j = 0;j < arr.size();j++) {173                 k = (arr[j] / radix) % 10;174                 if (k != 0) state = true;175                 count[k]++;176             }177             if (!state) {178                 return;179             }180             for (j = 1;j < 10;j++) {181                 count[j] = count[j - 1] + count[j];182             }183             for (j = arr.size() - 1;j >= 0;j--) {184                 k = (arr[j] / radix) % 10;185                 tmp[count[k] - 1] = arr[j];186                 count[k]--;187             }188             for (j = 0;j < arr.size();j++) {189                 arr[j] = tmp[j];190             }191             radix *= 10;192         }193     }194     /*195     * Merge Sort196     */197     static void merge(vector<T> &arr,int low,int high) {198         if (low >= high) {199             return;200         }201         int mid = (low + high) / 2;202         merge(arr,low,mid);203         merge(arr,mid+1,high);204         int i = low, j = mid + 1;205         vector<T> tmp;206         while (i <= mid&&j <= high) {207             if (arr[i] < arr[j]) {208                 tmp.push_back(arr[i++]);209             }210             else tmp.push_back(arr[j++]);211         }212         while (i <= mid) {213             tmp.push_back(arr[i++]);214         }215         while (j <= high) {216             tmp.push_back(arr[j++]);217         }218         for (i = low;i < low + tmp.size();i++) {219             arr[i] = tmp[i-low];220         }221     }222     static void merge_sort(vector<T> &arr) {223         merge(arr,0,arr.size()-1);224     }225     /*226     *  bitmap_sort227     */228     static void bitmap_sort(vector<int> &arr) {229         static unsigned int BitsSetTable32[32] =230         {231             0x80000000,0x40000000,0x20000000,0x10000000,232             0x08000000,0x04000000,0x02000000,0x01000000,233             0x00800000,0x00400000,0x00200000,0x00100000,234             0x00080000,0x00040000,0x00020000,0x00010000,235             0x00008000,0x00004000,0x00002000,0x00001000,236             0x00000800,0x00000400,0x00000200,0x00000100,237             0x00000080,0x00000040,0x00000020,0x00000010,238             0x00000008,0x00000004,0x00000002,0x00000001,239         };240         const int INT_BIT = 32;241         int i,j;242         int maxV = -1;243         for (i = 0;i < arr.size();i++) {244             if (arr[i] > maxV) maxV = arr[i];245         }246         vector<int> map((maxV+1)/INT_BIT+1);247         for (i = 0;i < arr.size();i++) {248             map[arr[i] / INT_BIT] = map[arr[i] / INT_BIT] | BitsSetTable32[arr[i] % INT_BIT];249         }250         arr.clear();251         for (i = 0;i < map.size();i++) {252             int t = map[i];253             for (j = 0;j < 32;j++) {254                 if (t&BitsSetTable32[j]) {255                     arr.push_back(32*i+j);256                 }257             }258         }259     }260 };261 262 #endif