十种经典排序算法

排序算法是一种很重要的算法，虽然标准库中有sort函数，但是还是要了解其中常用的几种排序算法，至于std::sort源码实现使用的排序算法是混合式排序，详见std::sort源码剖析

class Solution {
public:
    void mysort1(vector<int>& arr) {
        //冒泡排序：依次将最大数排到末尾,每次可少排一个元素
        //时间复杂度n + n-1 + n-2 + ... + 1  -> O(n) 空间复杂度 -> O(1)
        for (int i = 0; i < arr.size(); i++) {
            for (int j = 1; j < arr.size() - i; j++) {
                if (arr[j - 1] > arr[j]) {
                    int tmp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
    }

    void mysort2(vector<int>& arr) {
        //插入排序：
        
        
    }

    void mysort3(vector<int>& arr) {
        //选择排序

    }

    void mysort4(vector<int>& arr) {
        //希尔排序
    }

    void mysort5(vector<int>& arr) {
        //快速排序
    }
    
    void mysort6(vector<int>& arr) {
        //归并排序
    }

    void mysort7(vector<int>& arr) {
        //二叉堆排序
    }

    void mysort8(vector<int>& arr) {
        //计数排序
    }

    void mysort9(vector<int>& arr) {
        //桶排序
    }

    void mysort10(vector<int>& arr) {
        //基数排序
    }

    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int> tmp;
        mysort2(arr);
        for (int i = 0; i < k; i++) {
            tmp.push_back(arr[i]);
        }
        return tmp;
    }
};

十种经典排序算法

原文：https://www.cnblogs.com/chenwenjun/p/13068754.html