排序算法

2021-12-19 19:10:00

根据这是算法的实现方式不同给它们进行了一些分类，首先是根据算法实现是否需要比较分为了比较排序与非比较排序，对于比较排序它存在一个算法极限，并在笔记中进行分析。在比较排序中根据数据结构又可以分为简单排序与基于二叉树实现的排序，基于二叉树的排序的算法虽然复杂一些但是可以大大提升排序的时间复杂度，并且二叉树排序还体现出了算法设计中的常用的分而治之(Divide Conquer Combine)的思想。非比较排序非常巧妙的不需要比较就对一组数据进行了排序，非常有趣并且有启发意义。

image_2022-09-02_11-00-19

1、 比较排序

比较排序就是在排序过程中需要通过比较来确定元素的大小并根据元素的大小来排序，是我们常用的一种排序的方法。

1.1 简单排序

简单排序是日常生活中常用的排序方法，其逻辑比较简单，所依赖的数据结构就是顺序表，其平均算法复杂度为\(\mathcal{O}(n^2)\)。

1.1.1 冒泡排序(Bubble sort)

/*
 * 冒泡排序(稳定)
 *      1. 时间复杂度：
 *          平均：O(n^2)
 *          最好：O(n)
 *          最坏：O(n^2)
 *      2. 空间复杂度：
 *          O(1)
 *      3. 思路
 *          从后面开始，一个一个的冒上来
 *
 */
template<typename T>
void bubbleSort(std::vector<T>& nums){
    for(auto i = nums.begin(); i != nums.end(); i++){
        bool flag = true;           // 标志是否已经排好序
        for(auto j = nums.begin(); j < nums.end() - 1; j++){
            if((*j) > (*std::next(j))){
                std::iter_swap(j, std::next(j));
                flag = false;
            }
        }
        if(flag){return;}
    }
}

如果内层循环中没有发生元素交换则可以说明已经完成排序了，所以可以设置一个标志位，如果检测到已经完成排序那么直接返回即可，减少不必要的操作降低算法复杂度

1.1.2 选择排序(Select sort)

选择排序应该是排序算法中最简单的那个了，它就是遍历数组将最小的那个找出来将其与数组的第一个数组进行交换位置，然后再次遍历除第一个数组之外的其他数组元素找出第二小的放在数组第二位，如此循环直到数组元素按照从小到大的顺序完成排列。

/*
 * 选择排序(不稳定)
 *      1. 时间复杂度：
 *          平均：O(n^2)
 *          最好：O(n^2)
 *          最坏：O(n^2)
 *      2. 空间复杂度：
 *          O(1)
 *      3. 思路
 *          一个一个的选择出后面的最小值，让后在前面一个一个的排序
 *
 */
template<typename T>
void selectSort(std::vector<T>& nums){
    int n = nums.size();
    for(auto i = nums.begin(); i != nums.end(); i++){
        auto temp = i;
        for(auto j = i + 1; j != nums.end(); j++){
            if((*j) < (*temp)){
                temp = j;
            }
        }
        std::iter_swap(i, temp);
    }
}

1.1.3 插入排序(Insert sort)

插入排序就像我们打牌的时候整理牌一样，把第二个元素与第一个元素进行比较如果小于就插入到第一个元素前面（即交换两元素的位置），如果大于就不变，然后再将第三个元素插入的前面合适的位置，依此循环直到数组完成从小到大的排列。

/*
 * 插入排序(稳定)
 *      1. 时间复杂度：
 *          平均：O(n^2)
 *          最好：O(n)
 *          最坏：O(n^2)
 *      2. 空间复杂度：
 *          O(1)
 *      3. 思路
 *          每次抽取一张，往前面插入
 *
 */
template<typename T>
void insertSort(std::vector<T>& nums){
    for(auto i = nums.begin(); i != nums.end(); i++){
        auto j = i + 1;
        while(j > nums.begin() && (*j) < (*std::prev(j))){
            std::iter_swap(j, std::prev(j));
            j = std::prev(j);
        }
    }
}

1.1.4 希尔排序(Shell sort)

希尔排序是一插入排序的优化版，当插入排序中较小的元素在靠右的那边时，需要很多次比较才能将数组排列好。希尔排序就是按照一定的间隔(interval)将数组划分为几个子数组，对子数组进行插入排序，排序好之后再对组合成的完整数组进行选择排序，对于较大的数组也可以进行多次不同间隔的分割。

/*
@func:
    实现希尔排序算法
@para:
    SqList *L: 排序用的结构体，包含int型数组r与其长度length
@note:
    1. 希尔排序是一种基于选择排序的排序算法，在选择排序中如果最小值在数组的最右边就会产出非常多的比较次数，
    希尔排序就把一个数组按照一个interval将数组分为几个sub-list，对每个子数组进行选择排序然后再把他们合并。
    2. 希尔排序使用分治策略(Divide Conquer Conbine)
    3. shell sort有使用increment型的也有使用interval型的，increment就是取出连续的increment构成子序列，而interval
    是每隔interval构成一组
*/
void shell_sort(SqList *L){
    // 这里interval是一个经验值，目前没有固定的算法
    // interval为几就是分为几份
    // 如果右式有小数点的话直接舍去
    int interval = L->length/3 + 1;
    for(int i=0;i < interval; i++){
        for(int j=0;j < L->length; j += interval){
            for(int k=j+interval; k > 0; k -= interval){
                if(L->r[k] < L->r[k-interval]){
                    swag(L, k, k-interval);
                }
            }
        }
    }
    // 在完成分组排序后直接调用插入排序
    insert_sort(L);
}

1.2 基于二叉树的排序

下面几种算法是基于二叉树的排序方法，核心思想就是分而治之，一般采用递归求解，因为递归一般使用树这这数据结构表示，树中的二叉树结构最为简单且可以非常方便的通过一维数组进行储存，所以他们一般基于二叉树进行求解。

1.2.1 堆排序(Heap sort)

​ 堆排序是基于堆这种数据结构的一种排序方法，事实上堆这种数据结构是在堆排序这种算法提出的时候一齐提出来的，堆实际上是一种特殊的完全二叉树1，堆包含最大堆与最小堆，最大堆要求父节点要比两个子节点都要大，所以堆的根节点应该是堆中所以元素的最大值，最小堆则刚好与之相反。下面以最大堆为例介绍堆排序的大致过程，堆排序的大致思想就是先形成一个最大堆，然后将最大堆的根节点拿走，再使得剩下的元素形成一个最大堆，再将其根节点拿走，依此循环直到只剩下最后一个元素。因为每次重新形成的最大堆的根节点都是是剩余元素中的最大值，所以依此将其排列即可完成数组的排序。所以根排序的核心就是如何将一组元素形成最大堆，这是相关的代码。

template<typename T>
void heapify(std::vector<T>& nums, int i){
    int l = 2*i;        // left node
    int r = 2*i + 1;    // right node
    int maxIndex = i;   // max value index

    // max heap require the root value greater than left and right value
    if(l < nums.size() && nums[l] > nums[i]){
        maxIndex = l;
    }

    if(r < nums.size() && nums[r] > nums[maxIndex]){
        maxIndex = r;
    }
    if(i != maxIndex){
        std::swap(nums[i], nums[maxIndex]);
        heapify(nums, maxIndex);
    }
}

​ 还有一个值得提一下的是最大堆的建立，这个它的代码

template<typename T>
void buildMaxHeap(std::vector<T>& nums){
    int n = nums.size()/2;
    for(int i = n; i >= 0; i--){
        heapify(nums, i);
    }
}

可以看到，最大堆的建立是采用自底向上进行建立的，并且是从\(\lfloor{\frac{length}{2}}\rfloor\)开始的，因为在往下面走就都是叶子节点了我们上面的max_heapify只需要堆非叶子节点进行维护就可以了。下面我们证明一下为什么再往下面走就是叶子节点了，对于节点\(\lfloor{\frac{length}{2}}\rfloor\)其左孩子节点为 \[ \begin{aligned} \text{LEFT}(\lfloor n / 2 \rfloor + 1) & = 2(\lfloor n / 2 \rfloor + 1) \\\\ & > 2(n / 2 - 1) + 2 \\\\ & = n - 2 + 2 \\\\ & = n. \end{aligned} \] 因为它的左孩子节点应该大于数组元素数量\(n\)所以它就是一个叶子节点，对于它后面的肯定也为叶子节点。

​ 再实现堆排序的时候需要包含以下几个元素，一个是包含所有元素的数组，一个是数组长度还有一个是堆的大小，因为我们在抽离堆的根节点的时候要将堆的大小减一，但是堆的长度不变，下面是堆排序的主程序代码。

/*
 * 堆排序
 *      1. 时间复杂度：
 *          平均：O(n log n)
 *          最好：O(n log n)
 *          最坏：O(n log n)
 *      2. 空间复杂度：
 *          O(1)
 *      3. 思路
 *          采用堆数据结构（实际上是完整二叉树）进行排序
 *
 */
template<typename T>
void heapSort(std::vector<T>& nums){
    buildMaxHeap(nums);         // build new max heap
    std::vector<T>ans;
    while(!nums.empty()){
        std::iter_swap(nums.begin(), nums.end()-1);
        ans.push_back(nums.back());
        nums.pop_back();
        heapify(nums, 0);
    }
    nums = ans;
}

1.2.2 并归排序(Merge sort)

Merge sort是分而治之策略的典型体现，它首先将一个数组不断细分为不同的子数组，直到最终的子数组的长度为1，然后再将这些子数组按照顺序合并再一起就形成了一个排好序的数组了。首先来看合并部分

将两个已经排好序的数组合并成一个数组，

例如将nums1=[2,4,5,6]，nums2=[1,2,3,6]，合并成ans=[1,2,3,5,6]

通过C++编程的代码如下

/*
 * 并归排序
 *      1. 时间复杂度：
 *          平均：O(n log n)
 *          最好：O(n log n)
 *          最坏：O(n log n)
 *      2. 空间复杂度：
 *          O(n)
 *      3. 思路
 *          采用分治的思想进行排序
 *
 */

template<typename T>
void merge(std::vector<T> &vec, std::vector<T> &v1, std::vector<T> &v2) {
    auto siz1 = v1.size();
    auto siz2 = v2.size();
    size_t p1 = 0;
    size_t p2 = 0;

    while (p1 < siz1 && p2 < siz2) {
        if (v1.at(p1) < v2.at(p2))
            vec.push_back(v1.at(p1++));
        else
            vec.push_back(v2.at(p2++));
    }

    while (p1 < siz1) vec.push_back(v1.at(p1++));
    while (p2 < siz2) vec.push_back(v2.at(p2++));
}


template<typename T>
void mergeSort(std::vector<T> &vec) {
    if (vec.size() <= 1)
        return;

    auto mid = vec.begin() + vec.size() / 2;
    std::vector<T> v1(vec.begin(), mid);
    std::vector<T> v2(mid, vec.end());

    mergeSort(v1);
    mergeSort(v2);

    vec.clear();
    merge(vec, v1, v2);
}

快速排序

image-20220906110047376 
template<typename T>
int quickSortPartition(std::vector<T>& nums, int p, int r){
    int x = nums[r];        // as reference value
    int i = p - 1;
    for(int j = p; j < r; j++){
        if(nums[j] <= x){
            i++;
            std::swap(nums[i], nums[j]);
        }
    }
    std::swap(nums[i+1], nums[r]);
    return i+1;
}

template<typename T>
void quickSortAuxiliary(std::vector<T>& nums, int p, int r){        // p as start point, r as reference point
    if(p < r){

        int q = quickSortPartition(nums, p, r);         // partition

        quickSortAuxiliary(nums, p, q-1);
        quickSortAuxiliary(nums, q+1, r);
    }
}

template<typename T>
void quickSort(std::vector<T>& nums){
    quickSortAuxiliary(nums, 0, nums.size()-1);         // [left, right]
}

1.3 选择排序算法复杂度分析

2、非比较排序

2.1 计数排序

2.2 基数排序

2.3 桶排序

3、取值

  1. 完全二叉树 - 维基百科，自由的百科全书 (wikipedia.org)↩︎