- #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
- //该片段来自于http://www.codesnippet.cn/detail/0508201410153.html
来源: http://www.codesnippet.cn/detail/0508201410153.html