排序算法汇总

这篇具有很好参考价值的文章主要介绍了排序算法汇总。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

https://blog.csdn.net/weixin_30342639/article/details/105343780

#include
#include
#include
#include
using namespace std;

// https://blog.csdn.net/weixin_30342639/article/details/105343780

总览

1、选择排序- 不稳定!

2、冒泡排序-稳定

3、插入排序-稳定

4、快排

5、堆排

6、归并排序–稳定

(稳定的只有插入、冒泡、归并)

下面是非比较排序,稳定与否就不要记了。(好像都是稳定的)

7、希尔排序(插入排序的一种)–不稳定!
是插入排序的改进版本,基于分组的思想

8、计数排序 时间复杂度是O(n),很低,代价是空间复杂度很大,为O(n),不稳定

计数排序会创建一个临时的数组,里面存放每个数出现的次数。
计数排序仅适合数据跨度不大的场景。

9、桶排序 复杂度:桶排序执行的高效与否和是否是稳定的取决于哈希散列的算法以及内部排序的结果

桶排序类似于哈希表,通过一定的映射规则将数组中的元素映射到不同的桶中,每个桶内进行内部排序,最后将每个桶按顺序输出就行了。
桶排序执行的高效与否和是否是稳定的取决于哈希散列的算法以及内部排序的结果。
需要注意的是,这个映射算法并不是常规的映射算法,要求是每个桶中的所有数都要比前一个桶中的所有数都要大,这样最后输出的才是一个排好序的结果。
比如说第一个桶中存1-30的数字,第二个桶中存31-60的数字,第三个桶中存61-90的数字...

10、基数排序 复杂度就不要记了

不是很了解

1 选择排序----了解即可

//时间复杂度O(N2),空间复杂度O(1)
//算法:第一次遍历找到最小的,和第一个元素交换。第二次遍历找到最小的,和第二个元素交换

class Solution1
{
   
public:
    void sort(vector<int>& nums)
    {
        int n=nums.size();
        for(int i=0;i<n;i++)
        {
            int minindex=i;
            for(int j=i;j<n;j++)
            {
                if(nums[j]<nums[i])
                    minindex=j;
            }
            swap(nums[i],nums[minindex]);
        }
        return ;
    }

};

2–冒泡排序—了解即可–时间复杂度太高

//时间复杂度O(N2) 空间复杂度O(1)
//算法流程:从前往后遍历,两两比较。将大的放在后面。遍历完一次后,数组的最后一个元素就是最大的。遍历n次

class Solution2
{
public:
        void sort(vector<int> & nums)
        {
            int n=nums.size();
            for(int i=0;i<n-1;i++)
            {
                for(int j=0;j<n-i-1;j++)
                {
                    if(nums[j]>nums[j+1])
                        swap(nums[j],nums[j+1]);
                }
            }
            return ;
        }
};

3-插入排序–重点

//时间复杂度O(n2),,空间复杂度O(1),并且是稳定的
//之所以必上面两种时间复杂度好,是因为,他在数组的有序的部分,不会进行多余的比较。也就是,在基本有序时,时间复杂度会接近O(N)

class Solution3
{
public:
    void sort(vector<int> & nums)
    {
        int n=nums.size();
        for(int i=1;i<n;i++)
        {
            for(int j=i;j>0;j--)
            {
                if(nums[j]<nums[j-1])
                    swap(nums[j],nums[j-1]);

                else 
                    break;
            }
        }
        return ;
    }
};

上面三种是基本的排序,后面是高阶的时间复杂度格更低的排序

4–快速排序

//1 版本1–
//每次确定一个元素的位置

class Solution3
{
public:
    void quicksort(vector<int> & nums)
    {
        int n=nums.size();
        process(nums,0,n-1);
        return ;
    }
    //这个函数将L~R的位置的元素排好序
    void process(vector<int>& nums,int L,int  R )
    {
        if(L>=R) return ;
  
        int mid=partition(nums,L,R);
        process(nums,L,mid-1);
        process(nums,mid+1,R);

    }
    //这个函数以nums最右边的元素作为基准,将其放在其应该在的位置,小于等于nusm[r]的防左边
    int partition(vector<int> & nums,int L,int R)
    {
        if(L>R)
        {
            return -1;

        }
        if(L==R)
        {
            return L;
        }
        int prewrite=L;
        int index=L;
        while(index<R)
        {
            if(nums[index]<=nums[R])
            {
                swap(nums[index],nums[prewrite]);
                prewrite++;
            }
            index++;
        }
        swap(nums[prewrite],nums[R]);
        return prewrite;
    }
};

版本2–每次确定一组值相同的元素的位置:


class Solution3
{
public:
    void quicksort(vector<int> & nums)
    {
        int n=nums.size();
        process(nums,0,n-1);

    }
    //这个函数将L~R的位置的元素排好序
    void process(vector<int>& nums,int L,int  R )
    {
        //递归的base-case
        if(L>=R)
        {
            return ;
        }
        vector<int> equalarea =partition(nums,L,R);
        process(nums,L,equalarea[0]-1);
        process(nums,equalarea[1]+1,R);

    }

    //这个函数以nums最右边的元素作为基准,将其放在其应该在的位置,小于等于nusm[r]的防左边
    //注意的是less指针和more指针的含义不再是待改写的指针,而是已经完成排序的边界,也就是完成的排序的范围是[,less]和[more,]。也就是说,待改写的区域是(less,more),而不是[less,more]

    vector<int> partition(vector<int> & nums,int L,int R)
    {
        if(L>R)
            return{-1,-1};

        if(L==R)
        {
            return{L,R};
        }
        int less=L-1;
        int more=R;
        int index=L;
        while(index<more)
        {
            if(nums[index]==nums[R])
            {
                index++;
            }
            else if(nums[index]<nums[R])
            {
                swap(nums[++less],nums[index]);
                index++;
            }
            else if(nums[index]>nums[R])
            {
                swap(nums[index],nums[--more]);
                //index并不变化
            } 
        }
        swap(nums[more],nums[R]);
        return {less+1,more};

    }
};

版本三:最终版本


class Solution
{
    public:
    vector<int> quicksort(vector<int>& nums)
    {
        int n=nums.size();
        process(nums,0,n-1);
        return nums;
    }

    void process(vector<int>& nums,int L,int R)
    {
        if(L>=R)
        {
            return;
        }
        int temp=rand()%(R-L+1);
        swap(nums[L+temp],nums[R]);

        vector<int> equalarea=partition(nums,L,R);
        process(nums,L,equalarea[0]-1);
        process(nums,equalarea[1]+1,R);


    }
    vector<int> partition(vector<int>& nums,int L,int R)
    {
        if(L>R)
            return{-1,-1};
        if(L==R)
            return {L,L};
        
        int less=L-1;
        int more=R;
        int index=L;
        while(index<more)
        {
            if(nums[index]==nums[R])
                index++;
            else if(nums[index]<nums[R])
            {
                swap(nums[index],nums[++less]);
                index++;
            }
            else if(nums[index]>nums[R])
            {
                swap(nums[index],nums[--more]);
            }

        }
        swap(nums[more],nums[R]);
        return {less+1,more};
    }
};


int main()
{
    vector<int> nums{1,4,3,6,5,8,9,4};
    Solution1 slu;
    slu.sort(nums);
    for(auto it:nums)
    {
        cout<<it<<endl;
    }
    return 0;
}

5 归并排序

class Solution
{
    public:
    vector<int> sortArray(vector<int> & nums)
    {
        int l=0;
        int r=nums.size()-1;
        mergesort(nums,l,r);
        return nums;
    }

    //将left到right变为有序的
    void mergesort(vector<int>&nums,int left,int right)
    {
        //base_case
        if(left==right)
            return;
        int mid=left+(right-left)/2;

        //将left到mid变为有序的
        mergesort(nums,left,mid);
        //将mid到right变为有序的
        mergesort(nums,mid+1,right);

        //merge的过程,mid两侧有序的数组合并为整个数组有序的
        merge(nums,left,mid,right);

    }
    void merge(vector<int> & nums,int L,int M,int R)
    {
        vector<int> temp(R-L+1);
        int i=0;
        //左侧数据的起始的位置
        int p1=L;
        //右侧数据的起始的位置
        int p2=M+1;

        while(p1<=M && p2<=R)
        {
            if(nums[p1]<nums[p2])
            {
                temp[i]=nums[p1];
                p1++;
            }
            else 
            {
                temp[i]=nums[p2];
                p2++;
            }
            i++;

        }
        while(p1<=M)
        {
            temp[i]=nums[p1];
            p1++;
            i++;
        }
        while(p2<=R)
        {
            temp[i]=nums[p2];
            p2++;
            i++;
        }

        for(int i=0;i<temp.size();i++)
        {
            nums[L+i]=temp[i];
        }


    }

};

堆排—小根堆排序

i 结点的父结点 par = floor((i-1)/2) 「向下取整」

i 结点的左子结点 2 * i +1

i 结点的右子结点 2 * i + 2

//模拟priority_queue

class Heap
{
public:
    vector<int> vec;
    int capacity;
    int count;


    void swapNode(int i,int j)
    {
        swap(vec[i],vec[j]);
    }

    //小根堆的上浮操作---在堆中将index节点上浮
    void siftup_minheap(int index)
    {
        if(index==0) return;
        cout<<"..."<<endl;
        int parentNode=(index-1)/2;
        while(parentNode>=0)
        {
            
            if(vec[parentNode]<vec[index])
                break;//父节点比这个节点小,则停止上滤
            
            swapNode(index,parentNode);
            index=parentNode;
            if(index==0) break;
            parentNode=(index-1)/2;

        }
    }


    //小根堆的下沉操作--下沉的范围是[index,n),一般是vec.size()
    void siftdown_minheap(int index,int n)
    {
        int i=index;
        int j=2*i+1;//index节点的左儿子
        while(j<n)
        {
            if(j+1<n && vec[j+1]<vec[j]) j++;//j是左儿子和右儿子。较小的那个的下标
            if(vec[i]<vec[j]) break;//如果 当前节点比两个孩子都要小,那么停止下沉
            swapNode(i,j);
            i=j;
            j=2*i+1;
        }
    }

    //小根堆的插入操作
    void insert(int num)
    {
        vec.push_back(num);
        int index=vec.size();
        siftup_minheap(index-1);
    }

    //小根堆的删除堆顶元素操作--先将根节点和末尾元素互换,然后popback,然后从根节点开始下沉
    void del()
    {
        int n=vec.size();
        swapNode(0,n-1);

        vec.pop_back();

        siftdown_minheap(0,vec.size());

    }

    //原地建堆的操作--复杂度是NlogN
    void  buildHeap_1()
    {
        for(int i=0;i<vec.size();i++)
        {
            siftup_minheap(i);
        }
    }

//时间复杂度是N的,建堆方法--从第一个非叶子节点,往前遍历,并进行下沉操作
//根节点是0开始编号的时候,第一个非叶子节点是最后一个节点的父节点,也就是(n-1-1)/2=(n-2)/2
    void buildHeap()
    {
        int n=vec.size();
        for(int i=(n-2)/2;i>=0;i--)
        {
            siftdown_minheap(i,vec.size());
        }
    }


    int top()
    {
        int temp=vec[0];
        return temp;
    }



public:

    Heap(vector<int>& vec_)
    {
        vec=vec_;
    }

};

int main()
{
    vector<int> vec{9,4,7,1,5,3};
    Heap heap_(vec);
    heap_.buildHeap();

    while(heap_.vec.size()>0)
    {
        cout<<heap_.top()<<endl;
        heap_.del();
    }

    return 0;

}

//稳定性:只有冒泡、插入、归并,这三个是稳定性的排序算法。文章来源地址https://www.toymoban.com/news/detail-521645.html

到了这里,关于排序算法汇总的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】十大经典排序算法-快速排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 快速排序(Quick Sort)是一种高效的排序算法,是对冒泡排序的优化。它采用分治法(Divide and Conquer)的思想,将待排序序列

    2024年02月13日
    浏览(65)
  • 【数据结构与算法】十大经典排序算法-冒泡排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌴 掘金 :HelloCode 🌞 知乎 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 冒泡排序(Bubble Sort)是一种简单的排序算法,它通过重复地交换相邻元素的位置来将最大(或最小)的元素逐步“冒泡”到

    2024年02月14日
    浏览(75)
  • 【数据结构与算法】十大经典排序算法-插入排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 插入排序(Insertion Sort)是一种简单直观的排序算法,其基本思想是将一个记录插入到已排好序的有序序列中,直到所有记录

    2024年02月13日
    浏览(83)
  • 数据结构——排序算法之快速排序

        个人主页: 日刷百题 系列专栏 : 〖C/C++小游戏〗 〖Linux〗 〖数据结构〗   〖C语言〗 🌎 欢迎各位 → 点赞 👍+ 收藏 ⭐️+ 留言 📝  ​ ​ 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。 基本思想: 任取待排序元素序列中 的某元素作为基准值,按照

    2024年01月21日
    浏览(60)
  • 【数据结构与算法】排序算法(选择排序,冒泡排序,插入排序,希尔排序)

    基本概念这了就不浪费时间解释了,这四种都是很简单的排序方式,本专栏后续文章会出归并排序,计数排序,快速排序,堆排序,桶排序等排序算法,今天这篇文章中给出选择排序,冒泡排序,插入排序和希尔排序的实现; 如果发现文章中有错误,还请大家指出来,我会非

    2024年02月15日
    浏览(86)
  • 数据结构与算法-排序算法

    递归将整个函数的调用过程 调用过程 如何在CSDN博客中插入公式和各种符号 类似二叉树的后续遍历 递归行为和递归行为时间复杂度的估算 master 公式 : T ( n ) = a × T ( n b ) + O ( n d ) T(n) = a times T (frac{n}{b}) + O(n^d) T ( n ) = a × T ( b n ​ ) + O ( n d ) T ( n ) T(n) T ( n ) : 母问题的规模

    2024年02月15日
    浏览(54)
  • 算法 数据结构 递归插入排序 java插入排序 递归求解插入排序算法 如何用递归写插入排序 插入排序动图 插入排序优化 数据结构(十)

    1. 插入排序(insertion-sort):                                           是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入     算法稳定性:                  

    2024年02月09日
    浏览(56)
  • 数据结构与算法:插入排序&希尔排序

    假设现在你有一个有序的数组,你要把一个数据插入到数组中,保证插入后依然有序,要怎么做? 对于人来说,这个问题就像是在整理扑克牌,瞄一眼就知道应该插入什么位置。但是对于程序来说,就需要一一对比,直到找到一个位置 左边比它大,右边比它小 ,就算找到了

    2024年01月17日
    浏览(58)
  • 数据结构与算法—插入排序&选择排序

    目录 一、排序的概念 二、插入排序   1、直接插入排序  特性总结: 2、希尔排序 特性总结:  三、选择排序 1、直接选择排序  特性总结: 2、堆排序—排升序(建大堆) 向下调整函数 堆排序函数 特性总结: 代码完整版:   头文件  函数文件  测试文件 排序 :所谓排序,

    2024年01月20日
    浏览(63)
  • 数据结构与算法—归并排序&计数排序

    目录 一、归并排序 1、主函数 2、递归实现 3、优化递归  4、非递归实现 5、特性总结: 二、计数排序 1、代码: 2、特性总结: 三、各种排序总结 时间空间复杂度汇总  基本思想: 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用 分治法 的一个非常典型的

    2024年02月04日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包