《啊哈算法》第一章--排序

向右看齐 2024-03-17 17:57 48阅读 0赞

![在这里插入图片描述][f4e0159841ab450d861dde9e8fb5ba0d.gif_pic_center]

#### 文章目录 ####

*  前言
 *  一、排序算法
 *  二、桶排序
 *  三、冒泡排序
 *  三、快速排序
 *  总结

--------------------

## 前言 ##

今年蓝桥杯没有拿到省一，所以就决定沉下心来学习算法，为了使得算法的学习更加稳固，所以就拿起了，最基础的且最经典的一本算法书《啊哈算法》，并决定把我的学习过程写成博客，进行记录和分享。

--------------------

## 一、排序算法 ##

**冒泡排序**

最慢的，并且是在数据比较少的时候使用，时间复杂度为O(n^2)

**桶排序**

时间复杂度最低，即速度快，为O(N + C)，N为循环次数，C为N\*(logN - logM)，M为桶的数量 这里可以看本书的第一节结尾部分

**快速排序**

时间复杂度为O(N\*logN)，类似函数sort()排序，这也是以后算法比赛当中经常用到的排序，主要思想是 分治 思想

## 二、桶排序 ##

桶排序，顾名思义要设置很多桶或者容器，显然在计算机内可以是数组，所以我们在排序 0 ~ 2e9（2*109），就需要2\*109个桶，也就是申请2*10^ 9个变量，即使只对3个数排序，仍需要这么大的空间，就很浪费.

![在这里插入图片描述][065c091986dd418990e5bfebed305f30.png]

eg:五个小朋友拿到的旗子上边的数字分别为 5 3 5 2 8 ，然后要求你从大到小进行排序

#include<iostream>
    using namespace std;
    int book[10];//全局变量 自动 初始化为0 
    int main()
    {
        
    	int t;
    	for(int i=0;i<5;i++)//输入五个数字 
    	{
        
    		cin>>t;//输入的数字 
    		book[t]++;//出现的数字次数++ 
    	}
    	for(int i=8;i>=0;i--)//i定义为分数 
    		for(int j=0;j<book[i];j++)//分数出现的次数 
    			cout<<i<<" ";
    	return 0;
    }

**数据如下**

输入：5 3 5 2 8
    输出：8 5 5 3 2

## 三、冒泡排序 ##

冒泡排序又叫Bubble Sort，其原理就是每次比较相邻两个元素，如果顺序不对，就交换。  
![在这里插入图片描述][28637f9c3b1a449692905ae88596d8d3.png]  
前面我在C语言学习的时候就多次写过关于冒泡排序的代码，详细可以去看博客[C语言—数组—总结][C]

eg:现在有5名同学的分数需要我们去从大到小进行排序 分数分别为 89 90 69 100 67

#include<iostream>
    using namespace std;
    int score[6];//全局变量自动初始化为0
    int i,j;
    int main()
    {
        
    	for(i=0;i<5;i++)//五次输入
    		cin>>score[i];
    		
    	for(i=0;i<5-1;i++)//冒泡排序的趟数
    		for(j=0;j<5-1-i;j++)
    		{
        
    			if(score[j]<score[j+1])//交换
    			{
        
    				int tmp=score[j];
    				score[j]=score[j+1];
    				score[j+1]=tmp;
    			}
    		}
    	//输出
    	for(i=0;i<5;i++) cout<<score[i]<<" ";
    	cout<<endl;
    	
    	return 0;
    }

**数据如下**

输入：89 90 69 100 67
    输出：100 90 89 69 67

## 三、快速排序 ##

快速排序的知识讲解：

**快速排序的核心思想**：基于分治  
**快速排序主要的内容就是：**

*  确定分界点：q\[L\],q\[(L+R)/2\],q\[R\] `其实就是分为左边界，中间值和右边界，甚至随机一个数`
 *  调整区间，`其实就是把元素放到x的两侧`
 *  递归处理左右两段  
    ![在这里插入图片描述][1939d89100124cbda460277a289190db.png]  
    下面就是具体讲解步骤二的调整区间  
    ![在这里插入图片描述][f5311e9ae85947df9be4a4eac3ff594c.png]
 *  两个指针，i，j不断在这里面移动
 *  当指针i指向的元素<=x的时候就指针向右移动，同理指针j遇到>=x的时候就指针向左移动
 *  当i指针指向的元素>=x的时候停下来，等到j指针指向的元素<=x的时候就也停下来
 *  最后使得这两个元素进行swap交换一下

![在这里插入图片描述][bc641c94d01e474887fc705296807292.png]  
以上就是快速排序的基础知识啦，下面就要讲解一些习题来巩固和练习我们所讲解的知识点啦

**快排思想图:**  
![在这里插入图片描述][629f1b0d45c08fa15795f95d23947e9e.gif_pic_center]

详细可以看我写的**acw算法笔记**[【algorithm】算法基础课—排序算法（附笔记 | 建议收藏）][algorithm_ _]

--------------------

## 总结 ##

算法确实很难，但是不是谁都是一开始就很厉害，而是开始了才会变得厉害！！！

[f4e0159841ab450d861dde9e8fb5ba0d.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/9d2453dc275740d9b623bf4772fb0ecd.png
[065c091986dd418990e5bfebed305f30.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/65f8e9683da04fd18778ad10bfa6ed1c.png
[28637f9c3b1a449692905ae88596d8d3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/1d1b5f86e0d64a23af49d54fcbd80101.png
[C]: https://congfen214.blog.csdn.net/article/details/128277113
[1939d89100124cbda460277a289190db.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/2770305087ac4b8b9c053c6119b6cba4.png
[f5311e9ae85947df9be4a4eac3ff594c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/5d926dc1f9d14bbe909b7f74b97576bb.png
[bc641c94d01e474887fc705296807292.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/e2bc278b363b442f800e0c1aac02b6eb.png
[629f1b0d45c08fa15795f95d23947e9e.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/a32f27af146c4636bccb7eb7c3579371.png
[algorithm_ _]: https://congfen214.blog.csdn.net/article/details/128625595