算法基础学习笔记——①排序

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

博主:命运之光
专栏:算法基础学习

算法基础学习笔记——①排序


前言:算法学习笔记记录日常分享,需要的看哈O(∩_∩)O,感谢大家的支持!

✨快速排序——分治

image.png

因为x参与交换之后仍然会被留在左右区间中的一个里。

1.确定分界点:(这里的分界点不一定是x,可以随意取值,常用取值方法如下)
q[l],q[(l+r)/2],q[r],随机//这里随机数的表示:q[rand() % (r - l) + l]
2.调整区间:
image.png
3.递归处理左右两段(<=x和>=x这两段)
image.png
如何实现2:
方法1.
image.png
方法2.
image.png
将两个指针i,j从两头挪向分界点,直到有一个i>=x,此时这个i
需要放到右半边,一个j<x,此时这个j需要放到左半边,此时交
换i.j(swap),故此时i<=x,j>x,直到i,j相遇就可以把整个区间
一分为二
image.png
j的后面(不包括j)>=3,i的前面(不包括i)<=3(注意边界)
🍓代码实现
image.png
image.png
🍓快速排序模板:

void quick_sort(int q[], int l, int r)//简单理解:这里的l一般0,r一般是个数-1(减去第0个数)
{
     if (l >= r) return;//排序首先看边界,如果区间里没有数或只有一个数则不用排序,否则如下进行上述的1,2,3点
     int i = l - 1, j = r + 1 ,x = q[l + r >> 1];//问:为什么不是i=l,j=r?答:因为是先移动完指针再进行判断,因此指针要先放在两个指针的左右两侧一格,这样往中间移动一格后才能到正真的边界,注意:这里的i,j,l,r都为下标。
     while (i < j) 
     {
         do i ++ ; while (q[i] < x);//指针移动的判断不带等号,因为如果选取的x是数组里最大的数,那么一直满足q[i]<=x,i会一直++发生越界都不会停下,j同理。eg.123,选取3,i<=3,i++,i=3也会向后继续移动,已越界,错误,故此不能加=
         do j -- ; while (q[j] > x);
         if (i < j) swap(q[i], q[j]);//如果这两个指针还没有相遇,则交换,如果不用swap可以写:int t=q[i];q[i]=q[j];q[j]=t;
     }
     quick_sort(q, l, j);
     quick_sort(q, j + 1, r);//eg.1 2排序:
}

🍓对以上快速排序代码进行测试,模板可用(●’◡’●)!
image.png
🍓测试代码

#include<bits/stdc++.h> 
using namespace std;
void quick_sort(int q[], int l, int r)
{
     if (l >= r) return;
     int i = l - 1, j = r + 1 ,x = q[l + r >> 1];
     while (i < j) 
     {
         do i ++ ; while (q[i] < x);
         do j -- ; while (q[j] > x);
         if (i < j) swap(q[i], q[j]);
     }
     quick_sort(q, l, j);
     quick_sort(q, j + 1, r);
}
int main()
{
	int a[5]={5,3,2,8,6};//对5,3,2,8,6进行排序 
	quick_sort(a,0,4);//传入数组,传入l,r进行快速排序 
	for(int i;i<5;i++)
	{
		cout<<a[i]<<" ";	//快速排序结果为:23568 
	}
	return 0;
}

✨归并排序——分治 O(nlogn)

image.png
1.确定分界点:mid=(l+r)/2

要格外注意分界点:归并排序是下标的中间值,快速排序是随机一个数组里面的值

2.递归排序left,right
3.归并——合二为一 //实际是一个双指针算法
image.png
🍓归并排序模板:

void merge_sort(int q[], int l, int r)
{
	int tmp[5];//可变
	if (l >= r) return;
	int mid = l + r >> 1;
	merge_sort(q, l, mid);//l是左半边起点
	merge_sort(q, mid + 1, r);//mid+1是右半边起点
	int k = 0, i = l, j = mid + 1;
	while (i <= mid && j <= r)//i,j分别是左右两边的指针
	   if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];//tmp[k++]=q[i++]等价于tmp[k]=q[i],k++,i++
	   else tmp[k ++ ] = q[j ++ ];//比较q[i],q[j],哪个小就把哪个放到tmp里(最后tmp的顺序就可以从小到大依次排)
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];//把左右两边没有循环完的数放到最后(因为左右两边本身就已经从小到大排好序故这些数一定从小到大)
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];//将tmp里的数复制回q中
}

🍓对以上快速排序代码进行测试,模板可用(●’◡’●)!
image.png
🍓测试代码文章来源地址https://www.toymoban.com/news/detail-469879.html

#include<bits/stdc++.h> 
using namespace std;
void merge_sort(int q[], int l, int r)
{
	int tmp[5];
	if (l >= r) return;
	int mid = l + r >> 1;
	merge_sort(q, l, mid);
	merge_sort(q, mid + 1, r);
	int k = 0, i = l, j = mid + 1;
	while (i <= mid && j <= r)
	   if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
	   else tmp[k ++ ] = q[j ++ ];
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
int main()
{
	int a[5]={8,3,2,7,6};//对5,3,2,8,6进行排序 
	merge_sort(a,0,4);//传入数组,传入l,r进行快速排序 
	for(int i;i<5;i++)
	{
		cout<<a[i]<<" ";	//快速排序结果为:23568 
	}
	return 0;
}

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

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

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

相关文章

  • 【密码学基础】半/全同态加密算法基础学习笔记

    定义:只支持乘法或加法中的一种的同态加密。同态加密指的是允许直接对密文进行计算,密文计算结果解密后与明文直接计算结果相同。 Paillier加解密过程 Paillier的同态性 明文加法 = 密文乘法 明文乘法 = 密文指数幂 Paillier的安全性 基于大整数分解困难问题 相比Paillier,

    2024年02月13日
    浏览(54)
  • 【软考程序员学习笔记】——数据结构与算法基础

    目录  🍊一、数据结构概念和分类 🍊二、数组特点存储方式 🍊三、矩阵 特殊矩阵 非特殊矩阵 🍊四、栈和队列 🍊 五、二叉树的性质 🍊六、二叉树的遍历 (1)前序遍历(先根遍历,先序遍历) (2)中遍历(中根遍历) (3)后序遍历(后根遍历,后序遍历) 🍊七、二叉排序树 🍊八、

    2024年02月12日
    浏览(64)
  • 算法基础学习笔记——⑩DFS与BFS\树与图

    ✨博主:命运之光 ✨专栏:算法基础学习 目录 DFS与BFS树与图 ✨DFS ✨BFS 🍓宽搜流程图如下: 🍓宽搜流程: 🍓广搜模板 ✨树与图 🍓树是特殊的图(连通无环的图) 🍓树与图的存储: 🍓用宽搜框架来搜索图: 前言: 算法学习笔记记录日常分享,需要的看哈O(∩_∩)O,

    2024年02月09日
    浏览(36)
  • 算法基础学习笔记——⑬高斯消元\组合计数\容斥原理

    ✨ 博主: 命运之光 ✨ 专栏: 算法基础学习 目录 ✨高斯消元 ✨组合计数 🍓通过预处理逆元的方式求组合数: 🍓Lucas定理: 🍓分解质因数法求组合数: 前言: 算法学习笔记记录日常分享,需要的看哈O(∩_∩)O,感谢大家的支持! 高斯消元(Gaussian Elimination)是一种用于解线

    2024年02月07日
    浏览(39)
  • 深度学习笔记(七)——基于Iris/MNIST数据集构建基础的分类网络算法实战

    文中程序以Tensorflow-2.6.0为例 部分概念包含笔者个人理解,如有遗漏或错误,欢迎评论或私信指正。 截图和程序部分引用自北京大学机器学习公开课 在神经网络的构建过程中,都避不开以下几个步骤: 导入网络和依赖模块 原始数据处理和清洗 加载训练和测试数据 构建网络

    2024年01月18日
    浏览(36)
  • 算法基础学习笔记——④前缀和\差分\双指针\位运算

    ✨ 博主: 命运之光 ✨ 专栏: 算法基础学习 目录 ✨前缀和 ✨一维前缀和 🍓一维前缀和模板: ✨二维前缀和 🍓二位前缀和模板: 前言: 算法学习笔记记录日常分享,需要的看哈O(∩_∩)O,感谢大家的支持! 原i:a[1] a[2] a[3] …a[n] 前缀和:s[i]=a[1]+a[2]+…+a[i] s[0]=0(方便处理

    2024年02月08日
    浏览(51)
  • 【算法基础】(一)基础算法 --- 归并排序

    ✨个人主页:bit me ✨当前专栏:算法基础 🔥专栏简介:该专栏主要更新一些基础算法题,有参加蓝桥杯等算法题竞赛或者正在刷题的铁汁们可以关注一下🌹 🌹 🌹   题目要求: 给定你一个长度为 n 的整数数列。   请你使用归并排序对这个数列按照从小到大进行排序。  

    2024年01月21日
    浏览(33)
  • 【算法基础】(一)基础算法 --- 快速排序

    ✨个人主页:bit me ✨当前专栏:算法基础 🔥专栏简介:该专栏主要更新一些基础算法题,有参加蓝桥杯等算法题竞赛或者正在刷题的铁汁们可以关注一下,互相监督打卡学习 🌹 🌹 🌹   题目要求: 给定你一个长度为n的整数数列 请你使用快速排序对这个数列按照从小到大

    2023年04月14日
    浏览(43)
  • 算法基础15 —— 分治算法(归并排序 + 快速排序)

    分治法的基本概念、思想 分治法是一种很重要的算法。 字面解释,分治分治,分而治之。就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。 不难发现,分

    2024年02月03日
    浏览(55)
  • 排序算法笔记-快速排序

    快速排序:确定分界数,左边小于分界,右边大于分界数,通过递归来不断重置分界数划分区域,直至完成排序 最优 n*logn 最差 n^2 原地排序,所以空间复杂度是 O(1) 细节不在阐述,自己理解一下 力扣912. 排序数组 套用模版,完美解决 力扣215 数组中的第K个最大元素 题中要求

    2024年02月16日
    浏览(48)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包