jiao-huan-pai-xu

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

template <typename T>
void printVec(const T &t)
{
    for (size_t i = 0; i < t.size(); i++)
    {
        cout << t[i] << " ";
    }
    cout << endl;
}

template <typename T>
void BubbleSort(vector<T> &vec)
{
    bool flag = true;
    size_t i = vec.size() - 1;
    while (i > 0 && flag) //有交换且还有元素没有确定有序时所在位置
    {
        flag = false;
        for (size_t j = 0; j < i; j++)
        {
            if (vec[j] > vec[j + 1])//非递减
            {
                flag = true;
                std::swap(vec[j], vec[j + 1]);
            }
        }
        i--;
    }
}

int main(int argc, char **argv)
{
    vector<int> vec = {6, 5, 4, 3, 2, 5, 6, 2, 5};
    BubbleSort<int>(vec);
    printVec<vector<int>>(vec);
    // 2 2 3 4 5 5 5 6 6
    return 0;
}

快速排序

快速排序由Hoare于1962年提出，它的基本思想就是通过一组待排序的序列分割成两个独立的部分，其中一部分的所有数据比另外一部分的所有数据小，用此方法一直分割下去，整个排序过程可以递归进行。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

template <typename T>
void printVec(const T &t)
{
    for (size_t i = 0; i < t.size(); i++)
    {
        cout << t[i] << " ";
    }
    cout << endl;
}

template <typename T>
size_t Partition(vector<T> &vec, size_t low, size_t high)
{
    size_t i = low, j = high;
    T pivot = vec[low]; //选第一个元素作为基准元素
    while (i < j)
    {
        //向左扫描 找到右边比基准元素小的
        while (i < j && vec[j] > pivot)
            j--;
        if (i < j)
        {
            std::swap(vec[i], vec[j]);
            ++i;
        }
        //向右扫描 找到左边比基准元素大的
        while (i < j && vec[i] <= pivot)
            i++;
        if (i < j)
        {
            std::swap(vec[i], vec[j]);
            --j;
        }
    }
    return i;
}

template <typename T>
void QuickSort(vector<T> &vec, size_t low, size_t high)
{
    size_t mid;
    if (low < high)
    {
        mid = Partition<T>(vec, low, high);
        QuickSort(vec, low, mid - 1);
        QuickSort(vec, mid + 1, high);
    }
}

int main(int argc, char **argv)
{
    vector<int> vec = {6, 5, 4, 3, 2, 5, 6, 2, 5};
    QuickSort<int>(vec, 0, vec.size() - 1);
    printVec<vector<int>>(vec);
    // 2 2 3 4 5 5 5 6 6
    return 0;
}

递归调用所使用的栈空间为递归树的深度n，空间复杂度为O(n)

因为前后两个方向扫描并交换，相等的两个元素有可能出现排序前后位置不一致的情况，所以快速排序是不稳定的排序方法

template <typename T>
size_t PartitionPro(vector<T> &vec, size_t low, size_t high)
{
    size_t i = low, j = high;
    T pivot = vec[low]; //选第一个元素作为基准元素
    while (i < j)
    {
        while (i < j && vec[j] > pivot)
            j--; //向左扫描找到一个比基准小的
        while (i < j && vec[i] <= pivot)
            i++;
        if (i < j)
        {
            std::swap(vec[i++], vec[j--]);
        }
    }
    //将基准元素放到相应位置
    if (vec[i] > pivot)
    {
        std::swap(vec[i - 1], vec[low]);
        return i - 1;
    }
    std::swap(vec[i], vec[low]); // pivot<=vec[i]
    return i;
}

😃 交换排序

交换排序

冒泡排序

快速排序