于是今天用C++11的模版实现了几个整数和浮点数的排序算法模版，分别是
- 冒泡排序
- 鸡尾酒排序
- 插入排序
- 选择排序
- 壳排序
- 快速排序
都是教科书一般的算法，std::sort不知道比这个高到哪里去了（逃
使用的示例如下，
#include <iostream> #include <iterator> #include "Sort.hpp" using namespace std; int main(int argc, const char * argv[]) { int array[11]; auto restore = [&](int * x){ x[0]=12; x[1] = 2; x[2]=16; x[3]=30; x[4] = 8; x[5]=28; x[6]= 4; x[7] =10; x[8]=20; x[9]= 6; x[10]=18; }; restore(array); sort<int>(BUBBLE_SORT, array, 11); copy(array, array+11, ostream_iterator<int>(cout, " ")); cout<<'\n'; restore(array); sort<int>(COCKTAIL_SORT, array, 11); copy(array, array+11, ostream_iterator<int>(cout, " ")); cout<<'\n'; restore(array); sort<int>(INSERTION_SORT, array, 11); copy(array, array+11, ostream_iterator<int>(cout, " ")); cout<<'\n'; restore(array); sort<int>(SELECTION_SORT, array, 11); copy(array, array+11, ostream_iterator<int>(cout, " ")); cout<<'\n'; restore(array); sort<int>(SHELL_SORT, array, 11); copy(array, array+11, ostream_iterator<int>(cout, " ")); cout<<'\n'; restore(array); sort<int>(QUICK_SORT, array, 11); copy(array, array+11, ostream_iterator<int>(cout, " ")); cout<<'\n'; return 0; }
运行的结果如下
代码如下，最新的版本在我的Github上，sort-template
其实本来考虑过写得再通用一些，但是C++标准库的版本已经很好了，所以这里就只写了整数和浮点数的版本。（通过std::enable_if<std::is_arithmetic<T>::value, T>实现）
#ifndef SORT_HPP #define SORT_HPP #include <cstdint> #include <sys/types.h> #include <type_traits> typedef enum : uint32_t { BUBBLE_SORT, COCKTAIL_SORT, INSERTION_SORT, SELECTION_SORT, SHELL_SORT, QUICK_SORT, } method_t; template <typename Condition, typename T = void> using EnableIf = typename std::enable_if<Condition::value, T>::type; /** * @brief Universal sort function * * @param method Sorting method * @param data Array with integer or floating point * @param len Array length */ template<typename T, typename = EnableIf<std::is_arithmetic<T>>> void sort(method_t method, T* && data, ssize_t len); /** * @brief Bubble sort * * @param data Array with integer or floating point * @param len Array length */ template<typename T, typename = EnableIf<std::is_arithmetic<T>>> void __bubble_sort(T* && data, ssize_t len) __attribute__ ((visibility ("hidden"))); /** * @brief Cocktail sort * * @param data Array with integer or floating point * @param len Array length */ template<typename T, typename = EnableIf<std::is_arithmetic<T>>> void __cocktail_sort(T* && data, ssize_t len) __attribute__ ((visibility ("hidden"))); /** * @brief Insertion sort * * @param data Array with integer or floating point * @param len Array length */ template<typename T, typename = EnableIf<std::is_arithmetic<T>>> void __insertion_sort(T* && data, ssize_t len) __attribute__ ((visibility ("hidden"))); /** * @brief Selection sort * * @param data Array with integer or floating point * @param len Array length */ template<typename T, typename = EnableIf<std::is_arithmetic<T>>> void __selection_sort(T* && data, ssize_t len) __attribute__ ((visibility ("hidden"))); /** * @brief Shell sort * * @param data Array with integer or floating point * @param len Array length */ template<typename T, typename = EnableIf<std::is_arithmetic<T>>> void __shell_sort(T* && data, ssize_t len) __attribute__ ((visibility ("hidden"))); /** * @brief Quick sort * * @param data Array with integer or floating point * @param low Lower bound index of this array * @param high Upper bound index of this array */ template<typename T, typename = EnableIf<std::is_arithmetic<T>>> void __quick_sort(T* && data, ssize_t low, ssize_t high) __attribute__ ((visibility ("hidden"))); template<typename T, typename> void sort(method_t method, T* && data, ssize_t len) { switch (len) { case 0: case 1: return; case 2: if (data[0] > data[1]) { T tmp = data[0]; data[0] = data[1]; data[1] = tmp; } default: break; } switch (method) { caseBUBBLE_SORT: __bubble_sort(std::forward<T* &&>(data), len); break; caseCOCKTAIL_SORT: __cocktail_sort(std::forward<T* &&>(data), len); break; caseINSERTION_SORT: __insertion_sort(std::forward<T* &&>(data), len); break; caseSELECTION_SORT: __selection_sort(std::forward<T* &&>(data), len); break; case SHELL_SORT: __shell_sort(std::forward<T* &&>(data), len); break; case QUICK_SORT: __quick_sort(std::forward<T* &&>(data), 0, len - 1); break; default: break; } } template<typename T, typename> void __bubble_sort(T* && data, ssize_t len) { for (size_t i = 0; i < len; i++) { for (size_t j = i; j < len; j++) { if (data[i] > data[j]) { T temp = data[i]; data[i] = data[j]; data[j] = temp; } } } } template<typename T, typename> void __cocktail_sort(T* && data, ssize_t len) { bool swapped; do { swapped = false; for (ssize_t i = 0; i < len - 2; i++) { if (data[i] > data[i + 1]) { T temp = data[i]; data[i] = data[i + 1]; data[i + 1] = temp; swapped = true; } } if (!swapped) { break; } swapped = false; for (ssize_t j = len - 2; j >= 0; j--) { if (data[j] > data[j + 1]) { T temp = data[j]; data[j] = data[j + 1]; data[j + 1] = temp; swapped = true; } } } while (swapped); } template<typename T, typename> void __insertion_sort(T* && data, ssize_t len) { for (size_t i = 1; i < len; i++) { if (data[i - 1] > data[i]) { T temp = data[i]; int64_t j = i; while (j > 0 && data[j - 1] > temp) { data[j] = data[j - 1]; j--; } data[j] = temp; } } } template<typename T, typename> void __selection_sort(T* && data, ssize_t len) { for (size_t i = 0; i < len; i++) { T min = data[i]; size_t min_index = i; for (size_t j = i; j < len; j++) { if (data[j] < min) { min = data[j]; min_index = j; } } if (min_index != i) { T temp = data[i]; data[i] = data[min_index]; data[min_index] = temp; } } } template<typename T, typename> void __shell_sort(T* && data, ssize_t len) { ssize_t group, i, j; for (group = len / 2; group > 0; group /= 2) { for (i = group; i < len; i++) { for (j = i - group; j >= 0; j -= group) { if (data[j] > data[j + group]) { T temp = data[j]; data[j] = data[j + group]; data[j + group] = temp; } } } } } template<typename T, typename> void __quick_sort(T* && data, ssize_t low, ssize_t high) { auto partition = [&](int64_t low_p, int64_t high_p) -> int64_t { T pivot = data[low_p]; while (low_p < high_p) { while (low_p < high_p && data[high_p] > pivot) high_p--; data[low_p] = data[high_p]; while (low_p < high_p && data[low_p] <= pivot) low_p++; data[high_p] = data[low_p]; } data[low_p] = pivot; return low_p; }; size_t loc = 0; if (low < high) { loc = partition(low, high); __quick_sort(std::forward<T* &&>(data), low, loc - 1); __quick_sort(std::forward<T* &&>(data), loc + 1, high); } } #endif /* SORT_HPP */