排序汇总

 

#include <iostream>
#include <ctime>
#include <vector>
#include <algorithm>


using std::cout;
using std::endl;


/* xx排序，空间复杂度，时间复杂度，是否原地排序，是否稳定排序 */
/*
    1、冒泡排序
    2、插入排序
    3、选择排序
    4、希尔排序
    5、归并排序
    6、快速排序
    7、堆排序
    8、桶排序
    9、计数排序
    10、基数排序
*/


/* 冒泡排序，O(1)，O(n^2)，是，是 */
// 基础版
template<typename RandomAccessContainer>
void BubbleSort(RandomAccessContainer& _rac, int _len)
{
    for (int i = 0; i < _len - 1; ++i)
        for (int j = 0; j < _len - 1 - i; ++j)
            if (_rac[j] > _rac[j + 1])  // 注意：应该使用 > 而不是 >=，否则排序将可能不稳定
                std::swap(_rac[j], _rac[j + 1]);
}
// 第一次优化（已经有序时提前结束排序）
template<typename RandomAccessContainer>
void BubbleSort1(RandomAccessContainer& _rac, int _len)
{
    for (int i = 0; i < _len - 1; ++i)
    {
        bool isSorted = true;   // 有序标记，每轮开始为true
        for (int j = 0; j < _len - 1 - i; ++j)
        {
            if (_rac[j] > _rac[j + 1])
            {
                std::swap(_rac[j], _rac[j + 1]);
                isSorted = false;   // 有元素交换，代表未完成排序，标记变为 false
            }
        }
        if (isSorted) break;    // 若已经有序，结束排序
    }
}
// 第二次优化（已经有序时提前结束排序 + 右边序列已经有序）
template<typename RandomAccessContainer>
void BubbleSort2(RandomAccessContainer& _rac, int _len)
{
    int lastExchangeIndex = 0;  // 记录最后一次交换的位置
    int sortBorder = _len - 1;  // 无序边界，每次只需要比较到这里
    for (int i = 0; i < _len - 1; ++i)
    {
        bool isSorted = true;
        for (int j = 0; j < sortBorder; ++j)
        {
            if (_rac[j] > _rac[j + 1])
            {
                std::swap(_rac[j], _rac[j + 1]);
                isSorted = false;
                lastExchangeIndex = j;  // 更新最后一次交换的位置
            }
        }
        if (isSorted) break;
        sortBorder = lastExchangeIndex; // 把最后一次交换的位置作为无序边界
    }
}
// 第三次优化（已经有序时提前结束排序 + 两边序列已经有序，也叫鸡尾酒排序）
template<typename RandomAccessContainer>
void BubbleSort3(RandomAccessContainer& _rac, int _len)
{
    int lastRightExchangeIndex = 0; // 记录最后一次交换的位置（右）
    int sortRightBorder = _len - 1; // 无序边界，每次只需要比较到这里（右）
    int lastLeftExchangeIndex = _len - 1;   // 记录最后一次交换的位置（左）
    int sortLeftBorder = 0; // 无序边界，每次只需要比较到这里（左）

    for (int i = 0; i < (_len >> 1); ++i)   // 注意 i 的范围已经改变
    {
        bool isSorted = true;
        for (int j = sortLeftBorder; j < sortRightBorder; ++j)  // 奇数轮，从左向右
        {
            if (_rac[j] > _rac[j + 1])
            {
                std::swap(_rac[j], _rac[j + 1]);
                isSorted = false;
                lastRightExchangeIndex = j;
            }
        }
        sortRightBorder = lastRightExchangeIndex;
        if (isSorted || sortLeftBorder >= sortRightBorder) break;

        isSorted = true;    // 偶数轮，标记重新变为 true
        for (int j = sortRightBorder; j > sortLeftBorder; --j)  // 偶数轮，从右向左
        {
            if (_rac[j] < _rac[j - 1])
            {
                std::swap(_rac[j], _rac[j - 1]);
                isSorted = false;
                lastLeftExchangeIndex = j;
            }
        }
        sortLeftBorder = lastLeftExchangeIndex;
        if (isSorted || sortLeftBorder >= sortRightBorder) break;
    }
}


/* 插入排序，O(1)，O(n^2)，是，是 */
// 基础版
template<typename RandomAccessContainer>
void InsertionSort(RandomAccessContainer& _rac, int _len)
{
    for (int i = 1; i < _len; ++i)
    {
        auto insertValue = _rac[i];
        int j = i - 1;
        for (; j >= 0 && _rac[j] > insertValue; --j)    // 注意：应该使用 > 而不是 >=，否则排序将可能不稳定
            _rac[j + 1] = _rac[j];
        _rac[j + 1] = insertValue;  // 上面循环最后执行了 --j，因此使用 j + 1
    }
}
// 借助二分查找进行优化
// 二分查找第一个大于给定值的元素，返回下标
template<typename RandomAccessContainer, typename DataType>
int BinarySearch(RandomAccessContainer& _rac, int _startIndex, int _endIndex, const DataType& _target)
{
    while (_startIndex <= _endIndex)
    {
        int midIndex = _startIndex + ((_endIndex - _startIndex) >> 2);
        if (_rac[midIndex] > _target)
        {
            if (midIndex == _startIndex || _rac[midIndex - 1] <= _target) return midIndex;
            else _endIndex = midIndex - 1;
        }
        else _startIndex = midIndex + 1;
    }
    return _endIndex + 1;
}
// 插入排序优化
template<typename RandomAccessContainer>
void InsertionSort1(RandomAccessContainer& _rac, int _len)
{
    for (int i = 1; i < _len; i++)
    {
        auto insertValue = _rac[i];
        int j = i - 1;
        int tarIndex = BinarySearch(_rac, 0, j, insertValue);
        for (; j >= tarIndex; j--)
            _rac[j + 1] = _rac[j];
        _rac[tarIndex] = insertValue;
    }
}


/* 选择排序，O(1)，O(n^2)，是，否 */
template<typename RandomAccessContainer>
void SelectionSort(RandomAccessContainer& _rac, int _len)
{
    for (int i = 0; i < _len - 1; i++)
    {
        int minIndex = i;
        for (int j = i + 1; j < _len; j++)
            if (_rac[j] < _rac[minIndex]) minIndex = j;
        std::swap(_rac[i], _rac[minIndex]);
    }
}


/* 希尔排序，O(1)，O(n^2)~O(nlogn)，是，否 */
// 希尔排序是一种减增量的插入排序
template<typename RandomAccessContainer>
void ShellSort(RandomAccessContainer& _rac, int _len)
{
    auto d = _len;
    while (d > 1)
    {
        d >>= 1;
        for (int x = 0; x < d; ++x)
        {
            for (int i = x + d; i < _len; i += d)
            {
                auto insertValue = _rac[i];
                int j = i - d;
                for (; j >= 0 && _rac[j] > insertValue; j -= d)
                    _rac[j + d] = _rac[j];
                _rac[j + d] = insertValue;
            }
        }
    }
}


/* 归并排序，O(n)，O(nlogn)，否，是 */
// 归并排序中的 Merge 操作，合并两个小集合
template<typename RandomAccessContainer>
void Merge(RandomAccessContainer& _rac, int _startIndex, int _midIndex, int _endIndex)
{
    const int LEN = _endIndex - _startIndex + 1;
    auto data = _rac[0];
    std::unique_ptr<decltype(data)[]> tempArr(new decltype(data)[LEN]);   // 临时数组
    int p1 = _startIndex, p2 = _midIndex + 1, p = 0;
    while (p1 <= _midIndex && p2 <= _endIndex)  // 比较两个小序列，依次放入临时数组
    {
        if (_rac[p1] <= _rac[p2]) tempArr[p++] = _rac[p1++];    // 注意：应该使用 <= 而不是 <，否则排序将可能不稳定
        else tempArr[p++] = _rac[p2++];
    }
    while (p1 <= _midIndex) tempArr[p++] = _rac[p1++];  // 若左侧小序列有剩余，依次放入大序列
    while (p2 <= _endIndex) tempArr[p++] = _rac[p2++];  // 若右侧小序列有剩余，依次放入大序列
    for (int i = 0; i < LEN; i++) _rac[i + _startIndex] = tempArr[i];   // 把临时数组元素拷贝回原容器
}
// 归并排序递归调用
template<typename RandomAccessContainer>
void MergeSort(RandomAccessContainer& _rac, int _startIndex, int _endIndex)
{
    if (_startIndex < _endIndex)
    {
        // 折半成两个小序列，分别进行递归
        int midIndex = _startIndex + ((_endIndex - _startIndex) >> 2);
        MergeSort(_rac, _startIndex, midIndex);
        MergeSort(_rac, midIndex + 1, _endIndex);
        // 将两个有序小序列合并成一个有序大序列
        Merge(_rac, _startIndex, midIndex, _endIndex);
    }
}
// 归并排序
template<typename RandomAccessContainer>
void MergeSort(RandomAccessContainer& _rac, int _len)
{
    MergeSort(_rac, 0, _len - 1);
}


/* 快速排序，O(logn)，O(nlogn)，是，否 */
// O(logn)指栈空间
// 快速排序中的 Partition 操作（对 pivot 的选取可优化：随机数法、三数取中法）
template<typename RandomAccessContainer>
int Partition(RandomAccessContainer& _rac, int _startIndex, int _endIndex)
{
    auto pivot = _rac[_startIndex];
    while (_startIndex < _endIndex)
    {
        while (_startIndex < _endIndex && _rac[_endIndex] >= pivot)
            --_endIndex;
        _rac[_startIndex] = _rac[_endIndex];
        while (_startIndex < _endIndex && _rac[_startIndex] <= pivot)
            ++_startIndex;
        _rac[_endIndex] = _rac[_startIndex];
    }
    _rac[_startIndex] = pivot;
    return _startIndex;
}
// 快速排序递归调用
template<typename RandomAccessContainer>
void QuickSort(RandomAccessContainer& _rac, int _startIndex, int _endIndex)
{
    if (_startIndex < _endIndex)
    {
        int pivotIndex = Partition(_rac, _startIndex, _endIndex);
        QuickSort(_rac, _startIndex, pivotIndex - 1);
        QuickSort(_rac, pivotIndex + 1, _endIndex);
    }
}
// 快速排序
template<typename RandomAccessContainer>
void QuickSort(RandomAccessContainer& _rac, int _len)
{
    QuickSort(_rac, 0, _len - 1);
}


/* 堆排序，O(logn)，O(nlogn)，是，否 */
// 下沉调整
template<typename RandomAccessContainer>
void DownAdjust(RandomAccessContainer& _rac, int _parIndex, int _len)
{
    auto temp = _rac[_parIndex];
    auto childIndex = (_parIndex << 1) + 1;
    while ((childIndex < _len))
    {
        if (childIndex + 1 < _len && _rac[childIndex] < _rac[childIndex + 1])   // 找到孩子中较大的那个
            ++childIndex;
        if (temp >= _rac[childIndex])   // 孩子均小于 temp 时 break
            break;
        _rac[_parIndex] = _rac[childIndex];
        _parIndex = childIndex;
        childIndex = (_parIndex << 1) + 1;
    }
    _rac[_parIndex] = temp;
}
// 堆排序
template<typename RandomAccessContainer>
void HeapSort(RandomAccessContainer& _rac, int _len)
{
    // 对于数组可以这样：
    // std::make_heap(_rac, _rac + _len);
    // std::sort_heap(_rac, _rac + _len);
    // return

    // 对于容器可以这样：
    // std::make_heap(_rac.begin(), _rac.end());
    // std::sort_heap(_rac.begin(), _rac.end());
    // return

    for (int i = (_len - 2) >> 1; i >= 0; --i)  // 建堆（时间复杂度 O(n)）
        DownAdjust(_rac, i, _len);
    for (int i = _len - 1; i > 0; --i)  // 排序堆（时间复杂度 O(nlogn)）
    {
        std::swap(_rac[0], _rac[i]);
        DownAdjust(_rac, 0, i);
    }
}


/* 桶排序，O(n)，O(n)，否，取决于对桶的排序算法是否稳定 */
template<typename RandomAccessContainer>
void BucketSort(RandomAccessContainer& _rac, int _len)
{
    // 得到序列最大值和最小值,并计算差值 range
    auto max = _rac[0];
    auto min = _rac[0];
    for (int i = 1; i < _len; ++i)
    {
        if (_rac[i] > max) max = _rac[i];
        else if (_rac[i] < min) min = _rac[i];
    }
    auto range = max - min;
    // 初始化桶
    int bucketNum = _len;
    std::vector<std::vector<decltype(max)>> bucketArr(bucketNum);
    // 遍历原数组，将元素放入桶中
    for (int i = 0; i < _len; i++)
    {
        int  n = int(_rac[i] - min) * (bucketNum - 1) / range;
        bucketArr[n].push_back(_rac[i]);
    }
    // 对每个桶进行排序
    for (int i = 0; i < bucketNum; i++) std::sort(bucketArr[i].begin(), bucketArr[i].end());
    // 从桶中将元素复制回原序列
    int i = 0;
    for (const auto& d1 : bucketArr)
        for (const auto& d2 : d1)
            _rac[i++] = d2;
}


/* 计数排序，O(n)，O(m>n?m:n)，否，是 */
// n 代表元素个数，m>n?m:n 代表统计序列长度和元素个数的最大值
template<typename RandomAccessContainer>
void CountSort(RandomAccessContainer& _rac, int _len)
{
    // 得到序列最大值和最小值用于创建统计序列
    auto max = _rac[0];
    auto min = _rac[0];
    for (int i = 1; i < _len; ++i)
    {
        if (_rac[i] > max) max = _rac[i];
        else if (_rac[i] < min) min = _rac[i];
    }
    // 创建统计序列
    int countLen = max - min + 1;
    std::unique_ptr<int[]> countArr(new int[countLen] {0});
    for (int i = 0; i < _len; ++i) ++countArr[_rac[i] - min];
    // 统计序列变形
    int sum = 0;
    for (int i = 0; i < countLen; ++i)
    {
        sum += countArr[i];
        countArr[i] = sum;
    }
    // 倒序遍历原序列，从统计序列中找到正确的位置，放入临时的序列中
    std::unique_ptr<decltype(max)[]> sortedArr(new decltype(max)[_len]);
    for (int i = _len - 1; i >= 0; --i) sortedArr[--countArr[_rac[i] - min]] = _rac[i];
    // 从临时序列中复制回原序列
    for (int i = 0; i < _len; ++i) _rac[i] = sortedArr[i];
}


/* 基数排序，O(n)，O(mn)，否，是 */
// n代表元素个数，m 代表经过多少轮排序
// 对字符串排序
int GetCharByIndex(const std::string& _st, int _index)
{
    return _st.size() <= _index ? 0 : _st[_index];
}
void RadixSort(std::string _arr[], int _len, int _maxLen)   // _maxLen 代表所有字符串中最长的值
{
    // 创建临时排序结果序列，保存按位排序的临时结果
    std::unique_ptr<std::string[]> sortedArr(new std::string[_len]);
    // 从个位开始比较，
    for (int k = _maxLen - 1; k >= 0; --k)
    {
        // 创建统计序列
        int countLen = 128;
        std::unique_ptr<int[]> countArr(new int[_len]);
        for (int i = 0; i < _len; ++i) ++countArr[GetCharByIndex(_arr[i], k)];
        // 统计序列变形
        int sum = 0;
        for (int i = 0; i < countLen; ++i)
        {
            sum += countArr[i];
            countArr[i] = sum;
        }
        // 倒序遍历原序列，从统计序列中找到正确的位置，放入临时的序列中
        for (int i = _len - 1; i >= 0; --i) sortedArr[--countArr[GetCharByIndex(_arr[i], k)]] = _arr[i];
        // 从临时序列中复制回原序列
        for (int i = 0; i < _len; ++i) _arr[i] = sortedArr[i];
    }
}


int main()
{
    srand((unsigned)time(nullptr)); // 随机数种子

    constexpr int len = 200;
    int arr[len];
    for (auto& val : arr) val = rand() % 100;   // 随机生成数组元素

    auto IsSorted = [&arr, &len]    // 判断数组是否有序
    {
        for (int i = 0; i < len - 1; ++i) if (arr[i] > arr[i + 1]) return false;
        return true;
    };

    CountSort(arr, len);
    cout << IsSorted() << endl;

    return 0;
}

 

原文链接:https://www.cnblogs.com/teternity163/p/sort.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有