用C++11实现的几个排序算法模版

于是今天用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;
}

运行的结果如下

screenshot-sort

代码如下,最新的版本在我的Github上,BlueCocoa/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 */
 
声明: 本文为0xBBC原创, 转载注明出处喵~

发表评论

电子邮件地址不会被公开。 必填项已用*标注