[游戏开发]快速排序 归并排序 冒泡排序 插入排序 C++ 代码一览

快速排序

迭代快速排序

/*****
 * @brief quick sort base on iterative implementation. O(nlogn)
 * @param arr array
 * @param left left boundary
 * @param right right boundary
 * @param lower_to_upper lower to upper
 *****/
template <typename T>
void quick_sort_iterative(std::vector<T> &arr, int left, int right, const bool &lower_to_upper = true)
{
    int size = arr.size();
    if (size < 2 or left >= right or left < 0 or right > size - 1)
        return;

    std::stack<std::pair<int, int>> range;
    range.push({left, right});
    std::pair<int, int> cur_range;

    while (range.empty() == false)
    {
        cur_range = range.top();
        range.pop();

        if(cur_range.first >= cur_range.second)
            continue;

        int cur_left = cur_range.first, cur_right = cur_range.second, origin_pos = cur_range.first;
        T pivot_val = arr[origin_pos];

        while (cur_left < cur_right)
        {
            while (lower_to_upper and arr[cur_right] >= pivot_val and cur_left < cur_right or
                  !lower_to_upper and arr[cur_right] <= pivot_val and cur_left < cur_right)
                cur_right--;
            while (lower_to_upper and arr[cur_left] <= pivot_val and cur_left < cur_right or
                  !lower_to_upper and arr[cur_left] >= pivot_val and cur_left < cur_right)
                cur_left++;

            if (cur_left < cur_right)
                std::swap(arr[cur_left], arr[cur_right]);
        }
        std::swap(arr[origin_pos], arr[cur_left]);

        int pivot = cur_left;
        range.push( { cur_range.first, pivot - 1 } );
        range.push( { pivot + 1, cur_range.second } );
    }
}

递归快速排序

/*****
 * @brief quick sort base on recursive implementation. O(nlogn)
 * @param arr array
 * @param left left boundary
 * @param right right boundary
 * @param lower_to_upper lower to upper
 *****/
template <typename T>
void quick_sort_recursive(std::vector<T> &arr, int left, int right, bool lower_to_upper = true)
{
    int size = arr.size();
    if (size < 2 or left >= right or left < 0 or right > size - 1)
        return;

    int origin_left = left, origin_right = right, origin_pos = left;
    T pivot_val = arr[origin_pos];
    while (left < right)
    {
        while (lower_to_upper and arr[right] >= pivot_val and left < right or
              !lower_to_upper and arr[right] <= pivot_val and left < right)
            right--;
        while (lower_to_upper and arr[left] <= pivot_val and left < right or
              !lower_to_upper and arr[left] >= pivot_val and left < right)
            left++;

        if (left < right)
            std::swap(arr[left], arr[right]);
    }
    std::swap(arr[origin_pos], arr[left]);

    int pivot = left;
    quick_sort_recursive(arr, origin_left, pivot - 1, lower_to_upper);
    quick_sort_recursive(arr, pivot + 1, origin_right, lower_to_upper);
}

归并排序

迭代归并排序

/*****
 * @brief merge sort base on iterative implementation. O(nlogn)
 * @param arr array
 * @param left left boundary
 * @param right right boundary
 * @param lower_to_upper lower to upper
 *****/
template <typename T>
void merge_sort_iterative(std::vector<T> &arr, int left, int right, const bool &lower_to_upper = true)
{
    int size = arr.size();
    if (size < 2 or left >= right or left < 0 or right > size - 1)
        return;

    std::vector<T> buffer(size);
    int l_left, l_right, r_left, r_right;

    for (int step = 1; step < size; step *= 2)
        for (l_left = left; l_left <= right; l_left = r_right + 1)
        {
            l_right = right < l_left + step - 1 ? right : l_left + step - 1;
            r_left  = right < l_right + 1       ? right : l_right + 1;
            r_right = right < r_left + step - 1 ? right : r_left + step - 1;

            int counter = 0, origin = l_left;

            if (lower_to_upper)
                while (l_left <= l_right and r_left <= r_right)
                    buffer[counter++] = arr[l_left] < arr[r_left] ? arr[l_left++] : arr[r_left++];
            else
                while (l_left <= l_right and r_left <= r_right)
                    buffer[counter++] = arr[l_left] > arr[r_left] ? arr[l_left++] : arr[r_left++];

            while (l_left <= l_right)
                buffer[counter++] = arr[l_left++];
            while (r_left <= r_right)
                buffer[counter++] = arr[r_left++];

            for (int outer = origin, counter = 0; outer <= r_right; ++outer)
                arr[outer] = buffer[counter++];
        }

    return;
}

递归归并排序

/*****
 * @brief merge sort base on recursive implementation. O(nlogn)
 * @param arr array
 * @param left left boundary
 * @param right right boundary
 * @param lower_to_upper lower to upper
 *****/
template <typename T>
void merge_sort_recursive(std::vector<T> &arr, int left, int right, const bool &lower_to_upper = true)
{
    int size = arr.size();
    if (size < 2 or left >= right or left < 0 or right > size - 1)
        return;

    int mid = left + (right - left) * 0.5;
    int l_left = left, l_right = mid, r_left = mid + 1, r_right = right;

    merge_sort_recursive(arr, l_left, l_right, lower_to_upper);
    merge_sort_recursive(arr, r_left, r_right, lower_to_upper);

    std::vector<T> buffer;
    int counter = 0;

    if (lower_to_upper)
        while (l_left <= l_right and r_left <= r_right)
            buffer.emplace_back(arr[l_left] < arr[r_left] ? arr[l_left++] : arr[r_left++]);
    else
        while (l_left <= l_right and r_left <= r_right)
            buffer.emplace_back(arr[l_left] > arr[r_left] ? arr[l_left++] : arr[r_left++]);

    while (l_left <= l_right)
        buffer.emplace_back(arr[l_left++]);
    while (r_left <= r_right)
        buffer.emplace_back(arr[r_left++]);

    for (int outer = left; outer <= right; ++outer)
        arr[outer] = buffer[counter++];

    return;
}

冒泡排序

/*****
 * @brief bubble sort. O(n*n)
 * @param arr array
 * @param left left boundary
 * @param right right boundary
 * @param lower_to_upper lower to upper
 *****/
template <typename T>
void bubble_sort(std::vector<T> &arr, int left, int right, const bool &lower_to_upper = true)
{
    int size = arr.size();
    if (size < 2 or left >= right or left < 0 or right > size - 1)
        return;

    for (int outer = left; outer < right; ++outer)
        for (int inner = left; inner + 1 < size - outer; ++inner)
            if (lower_to_upper and arr[inner] > arr[inner + 1] or
               !lower_to_upper and arr[inner] < arr[inner + 1])
                std::swap(arr[inner], arr[inner + 1]);

    return;
}

插入排序

/*****
 * @brief insert sort. O(n*n)
 * @param arr array
 * @param left left boundary
 * @param right right boundary
 * @param lower_to_upper lower to upper
 *****/
template <typename T>
void insert_sort(std::vector<T> &arr, int left, int right, const bool &lower_to_upper = true)
{
    int size = arr.size(), outer, inner;
    if (size < 2 or left >= right or left < 0 or right > size - 1)
        return;

    for (outer = left + 1; outer < right + 1; ++outer)
    {
        T cur_val = arr[outer];
        for (inner = outer - 1; inner >= left; --inner)
            if (lower_to_upper and cur_val < arr[inner] or
               !lower_to_upper and cur_val > arr[inner])
                arr[inner + 1] = arr[inner];
            else
                break;

        arr[inner + 1] = cur_val;
    }

    return;
}

调用接口

快速排序和归并排序建议使用迭代版，以减少递归函数调用的开销。

快速排序

/*****
 * @brief quick sort. O(nlogn)
 * @param arr array
 * @param lower_to_upper lower to upper
 *****/
template <typename T>
void quick_sort(std::vector<T> &arr, const bool &lower_to_upper = true)
{
    int size = arr.size();
    if (size < 2)
        return;

    quick_sort_iterative(arr, 0, size - 1, lower_to_upper);
    // quick_sort_recursive(arr, 0, size - 1, lower_to_upper);
    return;
}

归并排序

/*****
 * @brief merge sort. O(nlogn)
 * @param arr array
 * @param lower_to_upper lower to upper
 *****/
template <typename T>
void merge_sort(std::vector<T> &arr, const bool &lower_to_upper = true)
{
    int size = arr.size();
    if (size < 2)
        return;

    merge_sort_iterative(arr, 0, size - 1, lower_to_upper);
    // merge_sort_recursive(arr, 0, size - 1, lower_to_upper);
    return;
}

冒泡排序

/*****
 * @brief bubble sort. O(n*n)
 * @param arr array
 * @param lower_to_upper lower to upper
 *****/
template <typename T>
void bubble_sort(std::vector<T> &arr, const bool &lower_to_upper = true)
{
    int size = arr.size();
    if (size < 2)
        return;

    bubble_sort(arr, 0, size - 1, lower_to_upper);
    return;
}

插入排序

/*****
 * @brief insert sort. O(n*n)
 * @param arr array
 * @param left left boundary
 * @param right right boundary
 * @param lower_to_upper lower to upper
 *****/
template <typename T>
void insert_sort(std::vector<T> &arr, const bool &lower_to_upper = true)
{
    int size = arr.size(), outer, inner;
    if (size < 2)
        return;

    insertion_sort(arr, 0, size - 1, lower_to_upper);
    return;
}

? ? ? ? 最近总结了下常用排序算法，暂时写了四种，先放上来吧~上面的代码比较分散，如果需要完整文件，可以从 Github 上访问完整文件，链接如下：

排序算法源文件仓库https://github.com/zionFisher/Toy-STL/tree/master/include/algorithm/sort? ? ? ? 出于兴趣目的，准备实现个 toy stl，目前先整理下 stl 涉及的算法和容器吧，有空可能会在上面的链接里实现基于迭代器的算法和容器分离的 toy stl。