【排序】快速排序(C语言实现)

文章目录

  • 前言
  • 1. Hoare思想
  • 2. 挖坑法
  • 3. 前后指针法
  • 4. 三路划分
  • 5. 快速排序的一些小优化
    • 5.1 三数取中
      • 常规的三数取中
      • 伪随机的三数取中
    • 5.2 小区间优化
  • 6. 非递归版本的快排
  • 7. 快速排序的特性总结




前言


快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。

本章会重点讲解快速排序的四种思想:

  1. Hoare思想
  2. 挖坑法
  3. 前后指针法
  4. 三路划分

以及快速排序的一些小优化,和递归与非递归的实现方式。

阅读本章建议有一点二叉树的基础,如果对二叉树不太了解的可以看看:《初阶二叉树》这篇文章


1. Hoare思想


我们先看一下Hoare的思想是怎么样实现的:
请添加图片描述
这里来解释一下这个思想的意思:

  1. 首先我们将数组起始位置的数据定义成key
  2. 我们从右边开始往前找一个比key的数
  3. 找到比key小的数,我们在从左边开始找一个比key的数
  4. 做完上面两个步骤以后,当R与L相遇时,我们再将key放到R和L相遇的位置上,此刻key已经排到了它所应该在的位置(就是排好序以后的位置),我们介绍的这几种方法本质都是将key放到它所应该在的位置

注意⚠️:
在实现这个代码之前,我们要注意几个点:

  1. 如果是排升序的话,一定是要先从右边开始找,再从左边找,这样就能确保找到的数,一定是小于key的,具体原因如下:
    在这里插入图片描述
  2. 我们要注意如果数组中所有数都比key大,那么我们往右边找比key小的数的时候,控制不当就会导致越界;同理,如果数组中所有的数都比key要小,那么我们往左边找比key大的数的时候,控制不当也会导致越界。
  3. 我们在交换R和L的值的时候,可能会遇到R和L遇到等于key的数,如果不做处理的话,这样R和L就会一直交换,导致死循环。

说了那么多,我们一起来看看Hoare版的快排用代码是怎么实现的:

int PartSort_Hoare(int* a, int begin, int end)
{int left = begin;int right = end - 1;// 在这块将key定义成下标,// 因为我们在后面的过程中会涉及将key与我们锁定的位置的数交换位置,// 如果写成int key = a[left]就不方便后面的交换int key_i = left;while (left < right){// 先走右边,再走左边while (left < right && a[right] >= a[key_i]) // 防止越界 && 找小{--right;}while (left < right && a[left] <= a[key_i]) // 防止越界 && 找大 {++left;}// 找到大的数和小的数,将它们交换位置Swap(&a[left], &a[right]);}// 出循环以后此刻left=right// 将在left位置和key_i位置的数交换一下位置Swap(&a[left], &a[key_i]);return left;
}void Quick_Sort(int* a, int begin, int end)
{if (begin >= end)return;int key = PartSort_Hoare(a, begin, end); // 区间分为: [begin, key) key[key + 1, end), 这里要注意, 我们给的区间是左闭右开的Quick_Sort(a, begin, key);Quick_Sort(a, key + 1, end);}

这里有一个细节不知道大家有没有发现
在这里插入图片描述
我在处理这两个地方的时候是先判断left是否小于right,这样处理的好处是有效的防止了我们对数组的越界访问,如果是后判断left是否小于right,那么在进行a[right] >= a[key_i]这步操作的时候,我们可能会进行越界访问数组的操作。


2. 挖坑法


我们先看一下挖坑法是怎么样实现的:
请添加图片描述

这里来解释一下这个思想的意思:

  1. 先将第一个数据存放在一个临时变量key中,然后形成一个坑位
  2. 右边开始找一个key小的数,将这个数放进坑位中,然后又将这个位置设置成坑位
  3. 左边开始找一个key大的数,将这个数放进坑位中,然后又将这个位置设置成坑位
  4. 当L和R相遇时,此时坑位一定是在L和R的交点处,我们将前面保存的临时变量key放入坑位中,此刻key已经排到了它所应该在的位置(就是排好序以后的位置)

我们来看一下挖坑法实现快排用代码是怎么实现的:

int PartSort_Hole(int* a, int begin, int end)
{int left = begin;int right = end - 1;// 这里不用像Hoare法那样设置成下标,// 因为我们在最后是直接将数据放入坑位中int key = a[begin];int hole = left; // 设置坑位while (left < right){// 先从右边走while (left < right && a[right] >= key)  //  防止越界 && 找小{--right;}//找到小于key的数了,将该数放在hole中,再将该位置设置为holea[hole] = a[right];hole = right;while (left < right && a[left] <= key)  // 防止越界 && 找大{++left;}//找到小于key的数了,将该数放在hole中,再将该位置设置为holea[hole] = a[left];hole = left;}a[hole] = key;return hole;
}void Quick_Sort(int* a, int begin, int end)
{if (begin >= end)return;int key = PartSort_Hole(a, begin, end);// 区间分为: [begin, key) key[key + 1, end), 这里要注意, 我们给的区间是左闭右开的Quick_Sort(a, begin, key);Quick_Sort(a, key + 1, end);
}


3. 前后指针法


我们先看一下前后指正法是怎么样实现的:
请添加图片描述
这里来解释一下这个思想的意思:

  1. 我们先定义两个指针prevcurkeyprevkey指向数组的起始位置,cur指向prev的下一个位置
  2. 我们先移动cur,找到比key小的数,就将cur位置的数据和 prev+1位置的数据交换位置,但这里出于考虑省略一些交换数据的消耗,我们可以判断prev+1位置的数据是否等于cur位置的数据,如过a[cur] < cur && a[prev+1] != a[cur],就将两个位置的数据进行交换
  3. 直到cur指针越界,我们这个过程就结束了,然后再将key的值放到prev的位置,此刻key已经排到了它所应该在的位置(就是排好序以后的位置)

我们来看一下前后指针实现快排用代码是怎么实现的:

int PartSort_PC_Point(int* a, int begin, int end)
{// 创建两个变量来指向数组int prev = begin;int cur = prev + 1;// 这里将key设置成int key_i = begin;while (cur < end){if (a[cur] < a[key_i] && ++prev != cur) // 找比key小的值 && 防止与自身交换{Swap(&a[cur], &a[prev]);}cur++;}// 此时cur已经比right大了,将prev与key_i位置的数换位置Swap(&a[key_i], &a[prev]);return prev;
}void Quick_Sort(int* a, int begin, int end)
{if (begin >= end)return;int key = PartSort_PC_Point(a, begin, end);// 区间分为: [begin, key) key[key + 1, end), 这里要注意, 我们给的区间是左闭右开的Quick_Sort(a, begin, key);Quick_Sort(a, key + 1, end);
}


4. 三路划分


三路划分这个思想用来处理大量重复数据的时候,效率特别高。

我们先看一下三路划分是怎样实现的:
请添加图片描述
这里来解释一下这个思想的意思:

  1. 我们先定义一个key等于数组起始位置的数据 ,之后在数组起始位置定义一个L指针,在L的下一个位置定义一个cur指针,最后在末尾位置定义一个R指针
  2. 我们从cur位置开始,找一个比key小的数,找到以后,交换curL的位置的值,并且++cur++L
  3. 如果cur等于key,++cur
  4. 如果cur遇到一个比key大的数,交换交换curR的位置的值,并且--R,这里要注意不能动cur的值,因为从R位置交换过来的值,我们没办法判断它与key的大小关系,所以保持cur的位置不变,再继续将cur位置的值与key做比较
  5. cur > R的时候,这个过程就结束了

在实现这个代码的过程中,我们需要返回的是一个范围:[begin,L)[R + 1,end)

为什么是这样呢?
在这里插入图片描述
因为我们在进行一次三路划分过后,已经将key与key相等的数排好位置了,剩下的就只剩[begin,L)[R + 1,end)需要排序(这里我是设置成左闭右开区间,大家写的时候,也可以自己设置成左闭右闭区间),因为实现三路划分需要得到一个范围,所以写成函数不太好控制,所以我就直接将这个过程写在Quick_Sort函数中了

我们来看一下三路划分法实现快排用代码是怎么实现的:

void Quick_Sort(int* a, int begin, int end)
{if (begin >= end)return;int left = begin;int right = end - 1;int cur = left + 1;int key = a[left];while (cur <= right) // cur > right 循环才结束{if (a[cur] < key) // cur位置的值小于key{// 交换cur和L的位置的值,并且++cur ,++leftSwap(&a[cur], &a[left]);++cur;++left;}else if (a[cur] > key) // cur位置的值大于key{// 交换cur和L的位置的值,并且--rightSwap(&a[cur], &a[right]);--right;}else // cur位置的值等于key{++cur;}}// [begin, left) 和 [right + 1, end)Quick_Sort(a, begin, left);Quick_Sort(a, right + 1, end);
}


5. 快速排序的一些小优化


我们在上面实现排序的时候,面对一些情况我们写的快排也还是有些吃力,所以我们也还需要对一些情况做一些处理

这里有一点,可以注意一下:
就是我在上面写4种思想实现快排的时候,前三种思想我是将递归过程单独写成子函数来调用的,这样做的目的是使我写这篇博客时的可读性提高。但如果是我们自己写的时候,也可以不用单独写成一个子函数来调用,可以直接将这些思想的过程写进函数体里面。毕竟函数调用时,还是会有一点消耗的,当然这些消耗可以忽略不计

5.1 三数取中

三数取中有两种取法(当然不止两种),这里我要介绍的是两种思想:

常规的三数取中

这个思想主要是:我们通过比较数组起始位置和中间位置还有末尾位置的数据,第二大的数作为key

具体我们写代码来看一下:

int GetMidi(int* a, int begin, int end) // 三数取中
{int left = begin;int right = end - 1;int mid = (left + right) / 2;if (a[left] < a[mid])                // a[left] < a[mid]{if (a[mid] < a[right])           // a[left] < a[mid] < a[right]return mid;else if (a[left] < a[right])     // a[mid] >= a[right] > a[left]return right;else                             // a[mid] > a[left] >= a[right]return left;}else                                 // a[left] >= a[mid]{if (a[left] < a[right])          // a[mid] <= a[left] < a[right]return left;else if (a[right] > a[mid])      // a[left] >= a[right] > a[mid]return right;else                             // a[left] > a[mid] >= a[right]return mid;}
}

伪随机的三数取中

这个思想主要是:我们通过比较数组起始位置和数组中一个随机的位置,和他们中间位置的数据,第二大的数作为key

具体实现过程如下:

int GetMidi_random(int* a, int begin, int end) 
{int left = begin;int right = begin + rand() % (end - begin); // 后面加的数是整个数组的范围int mid = (left + right) / 2;if (a[left] < a[mid])                // a[left] < a[mid]{if (a[mid] < a[right])           // a[left] < a[mid] < a[right]return mid;else if (a[left] < a[right])     // a[mid] >= a[right] > a[left]return right;else                             // a[mid] > a[left] >= a[right]return left;}else                                 // a[left] >= a[mid]{if (a[left] < a[right])          // a[mid] <= a[left] < a[right]return left;else if (a[right] > a[mid])      // a[left] >= a[right] > a[mid]return right;else                             // a[left] > a[mid] >= a[right]return mid;}
}int main()
{srand((unsigned)time(NULL)); // 生成随机数种子return 0;
}

我们在用三数取中时,获取到的是想要的数的位置,然后将这个位置的数和数组起始位置的数交换一下,这样就方便我们定义key了。具体实现方式,我写在了本小节的最后。

5.2 小区间优化

在这里插入图片描述

我们在学过二叉树以后,应该知道,完全二叉树,倒数第二层和最后一层加起来占了整个节点75%的节点,而我们在处理大量数据使用快排实现递归时当只有10个数据时,还会递归多次:
在这里插入图片描述
而在处理这些大量数据,我们递归下来时,无疑会产生大量范围为10及10以下的多组数据,如果我们此时继续递归,无疑会产生很多组小范围的数据。所以范围小于等于10的时候,就没必要使用快排继续递归了,这里可以考虑使用直接插入排序来排每组范围小于等于10的数组。这样就大大降低了递归时开辟栈帧的消耗了。在使用插入排序时,我们必须要弄清楚所需排序的范围:
在这里插入图片描述

下面我以三路划分的思想写一个我上述优化后的排序,里面有用到直接插入排序,这个不是本章的重点,不了解的可以看看这篇博客:《简单排序》:

int GetMidi_random(int* a, int begin, int end) 
{int left = begin;int right = begin + rand() % (end - begin); // 后面加的数是整个数组的范围int mid = (left + right) / 2;if (a[left] < a[mid])                // a[left] < a[mid]{if (a[mid] < a[right])           // a[left] < a[mid] < a[right]return mid;else if (a[left] < a[right])     // a[mid] >= a[right] > a[left]return right;else                             // a[mid] > a[left] >= a[right]return left;}else                                 // a[left] >= a[mid]{if (a[left] < a[right])          // a[mid] <= a[left] < a[right]return left;else if (a[right] > a[mid])      // a[left] >= a[right] > a[mid]return right;else                             // a[left] > a[mid] >= a[right]return mid;}
}void Quick_Sort(int* a, int begin, int end)
{if (begin >= end)return;if (end - begin > 10)  // 小区间优化{int left = begin;int right = end - 1;int cur = left + 1;int mid = 0;if (left < end){mid = GetMidi(a, left, end); //三数取中,获取我们要找的数Swap(&a[mid], &a[left]); // 将三数取中得到的数换到第一个位置}int key = a[left];while (cur <= right){if (a[cur] < key){Swap(&a[cur], &a[left]);++left;++cur;}else if (a[cur] > key){Swap(&a[cur], &a[right]);--right;}else++cur;}// 分区间进行递归Quick_Sort(a, begin, left);Quick_Sort(a, right + 1, end);}else{// 使用插入排序时,要注意使用的范围InsertSort(a + begin, end - begin);}
}



6. 非递归版本的快排


在我们使用快排时,其实用递归也递归不了多少层。所以在平时我们要使用快排时,使用递归版的完全够用了。但由于现在还在学习阶段,所以掌握一下非递归版的快排还是有必要的。

我们实现非递归版本的快排时,用到的思想是我上面介绍的几种思想,只不过接下来讲的不是用递归去完成这个过程,这里我们要使用一个工具——,能够看到这里的我相信大家都对栈有一定的了解了,所以我在下面代码中,就将直接使用我写的栈了。不太了解栈的也可以看看这篇文章:《栈和队列》

void QuickSortNonR(int* a,int begin, int end)
{int left = begin;int right = end;Stack stack; // 创建一个栈的数据结构StackInit(&stack); // 将这个栈初始化一下StackPush(&stack, left); // 插入最开始的数StackPush(&stack, right); // 插入最后一位数的下一位,因为我们上面实现的三种方法都是左闭右开的while (!StackEmpty(&stack)){right = StackTop(&stack); // 我们是先插入最右边的数,所以我们应该先拿出最右边的数StackPop(&stack); // 栈顶元素删除left = StackTop(&stack); // 在上面删除right时,栈顶元素就是left了StackPop(&stack); // 栈顶元素删除int key = PartSort_Hoare(a, left, right); // 将这段区间进行排序// [left,key) key [key+1,right)if (right > key + 1) // 如果这个区间存在,就将这个区间表示的范围入栈(这里要注意入栈顺序和出栈顺序){StackPush(&stack, key + 1);StackPush(&stack, right);}if (left < key) // 如果这个区间存在,就将这个区间表示的范围入栈(这里要注意入栈顺序和出栈顺序){StackPush(&stack, left);StackPush(&stack, key);}}// 销毁栈StackDestroy(&stack);
}

有人可能会问我们递归时用到的栈帧和我们自己做的栈,有什么区别呢?

因为我自己做的栈是在堆上开辟的空间,而如果使用递归版本的栈帧是在栈上开辟的空间。32位机器下,栈上的空间只有8MB左右,而堆上的空间有4G左右。所以这里选择在堆上开辟空间,可以很好的节约空间,也能减少递归时产生的消耗。


7. 快速排序的特性总结


  1. 快速排序整体的综合性能和使用场景都是比较好的,所以才敢叫快速排序

  2. 时间复杂度:O(N*logN)
    在这里插入图片描述

  3. 空间复杂度:O(logN)

    • 快速排序的空间复杂度取决于递归深度和每个递归函数栈空间的大小。
    • 在最坏情况下,快速排序的空间复杂度为O(n);在平均情况下,快速排序的空间复杂度为O(logn)1。
    • 快速排序是一种原地排序算法,它的工作原理是选择一个基准值,将待排序的数组划分为两个子数组,一个小于等于基准值,一个大于基准值,然后对两个子数组递归进行快速排序,直到整个数组有序。
  4. 稳定性:不稳定

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/238207.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

格密码基础:SIS问题的困难性

目录 一. SIS问题的困难性 二. SIS问题归约的性质 2.1 2004年 [MR04] 2.2 2008年 【GPV08】 2.3 2013年【MP13】 三. 归约证明 3.1 核心理解 3.2 归约步骤 3.3 性质理解 一. SIS问题的困难性 推荐先阅读&#xff1a; 格密码基础&#xff1a;SIS问题的定义与理解-CSD…

【Linux】应用与驱动交互及应用间数据交换

一、应用程序与 Linux 驱动交互主要通过以下几种方式&#xff1a; 1. 系统调用接口&#xff08;System Calls&#xff09;: 应用程序可以通过系统调用&#xff0c;如 open(), read(), write(), ioctl(), 等来与设备驱动进行交互。这些调用最终会通过内核转发到相应的驱动函数…

感染嗜肺军团菌是什么感觉?

记录一下最近生病的一次经历吧&#xff0c;可能加我好友的朋友注意到了&#xff0c;前几天我发了个圈&#xff0c;有热心的朋友还专门私信了我说明了他自己的情况和治疗经验&#xff0c;感谢他们。 ​ 那么关于这次生病的经历&#xff0c;给大家分享一下。 首先&#xff0c;这次…

解锁 JavaScript 数组的强大功能:常用方法和属性详解(上)

&#x1f90d; 前端开发工程师&#xff08;主业&#xff09;、技术博主&#xff08;副业&#xff09;、已过CET6 &#x1f368; 阿珊和她的猫_CSDN个人主页 &#x1f560; 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 &#x1f35a; 蓝桥云课签约作者、已在蓝桥云…

70.网游逆向分析与插件开发-角色数据的获取-自动化助手UI显示角色数据

内容参考于&#xff1a;易道云信息技术研究院VIP课 上一个内容&#xff1a;利用技能点属性分析角色数据基址-CSDN博客 码云地址&#xff08;ui显示角色数据 分支&#xff09;&#xff1a;https://gitee.com/dye_your_fingers/sro_-ex.git 码云版本号&#xff1a;367aa71f60b…

C++ 完成Client分页显示log

分页显示t_log 1、获取用户的输入 1.1、写一个Input成员函数&#xff0c;处理输入进来的语句 std::string XClient::Input() {//清空缓冲//cin.ignore(4096, \n);string input "";for (;;){char a getchar();if (a < 0 || a \n || a \r)break;cout <<…

蓝桥杯准备

书籍获取&#xff1a;Z-Library – 世界上最大的电子图书馆。自由访问知识和文化。 (zlibrary-east.se) 书评&#xff1a;(豆瓣) (douban.com) 一、观千曲而后晓声 别人常说蓝桥杯拿奖很简单&#xff0c;但是拿奖是一回事&#xff0c;拿什么奖又是一回事。况且&#xff0c;如果…

LeetCode讲解篇之78. 子集

文章目录 题目描述题解思路题解代码 题目描述 题解思路 初始化一个start变量记录当前从哪里开始遍历搜索nums 搜索过程的数字组合加入结果集 然后从start下标开始遍历nums&#xff0c;更新start&#xff0c;递归搜索 直到搜索完毕&#xff0c;返回结果集 题解代码 class …

wxWidgets实战:使用mpWindow绘制阻抗曲线

选择模型时&#xff0c;需要查看model的谐振频率&#xff0c;因此需要根据s2p文件绘制一张阻抗曲线。 如下图所示&#xff1a; mpWindow 左侧使用mpWindow&#xff0c;右侧使用什么&#xff1f; wxFreeChart https://forums.wxwidgets.org/viewtopic.php?t44928 https://…

npm run dev,vite 配置 ip 访问

启动项目通过本地 ip 的方式访问 方式一.通过修改 package.json "scripts": {"dev": "vite --host 0.0.0.0",}, 方式二.通过修改 vite.config.ts export default defineConfig({plugins: [vue(), vueJsx()],server: { // 配置 host 与 port 方…

AI大模型学习笔记二

文章目录 一、Prompt Engineering1&#xff09;环境准备 二、LangChain&#xff08;一个框架名字&#xff09;三、Fine-tuning&#xff08;微调&#xff09; 一、Prompt Engineering 1&#xff09;环境准备 ①安装OpenAI库 pip install --upgrade openai附加 安装来源 pyth…

DDNS-GO配置使用教程

环境&#xff1a;openwrt 下载地址&#xff1a;Releases jeessy2/ddns-go GitHub 下载 ssh至openwrt根目录&#xff0c;根据你的处理器选择要下载的版本&#xff0c;我是路由器&#xff0c;选择的是 ddns-go_5.7.1_linux_arm64.tar.gz wget github链接 安装 tar -zxvf…

基于STM32的CMT液晶屏控制器驱动程序设计与优化

本文以STM32微控制器为基础&#xff0c;设计并优化了一个用于控制CMT液晶屏的驱动程序。在设计过程中&#xff0c;我们首先介绍了液晶屏的基本工作原理&#xff0c;包括CMT液晶屏的结构和信号传输机制。然后&#xff0c;我们详细讨论了STM32微控制器的GPIO、SPI和DMA模块的特性…

Windows下面基于pgsql15的备份和恢复

一、基础备份 1.创建一个文件用来存储备份数据 2.备份指令 $CurrentDate Get-Date -Format "yyyy-MM-dd" $OutputDirectory "D:\PgsqData\pg_base\$CurrentDate" $Command "./pg_basebackup -h 127.0.0.1 -U postgres -Ft -Pv -Xf -z -Z5 -D $O…

分布形态的度量_峰度系数的探讨

集中趋势和离散程度是数据分布的两个重要特征,但要全面了解数据分布的特点&#xff0c;还应掌握数据分布的形态。 描述数据分布形态的度量有偏度系数和峰度系数, 其中偏度系数描述数据的对称性,峰度系数描述与正态分布的偏离程度。 峰度系数反映分布峰的尖峭程度的重要指标. 当…

书生·浦语大模型实战营笔记(四)

Finetune模型微调 直接使用现成的大语言模型&#xff0c;在某些场景下效果不好&#xff0c;需要根据具体场景进行微调 增量预训练&#xff1a;投喂垂类领域知识 陈述形式&#xff0c;无问答&#xff0c;即只有assistant 指令跟随&#xff1a;system-user-assistant XTuner …

【Git】本地仓库管理远程库(GitHub)——clone(下载)、commit(添加到本地仓库)、push(提交到远程仓库)、pull(拉取)操作

目录 使用远程仓库的目的将本地仓库同步到git远程仓库 1.克隆远程仓库(clone)2.新建一个文件3.将工作区的文件添加到暂存区4.将暂存区的文件添加到本地仓库(commit)5.提交(同步)到远程仓库(push)6.远程库拉取到本地库(pull)7.团队协作开发和跨团队协作开发(开源项目) 使用远程…

CSS 圆形分割按钮动画 带背景、图片

<template><view class="main"><view class="up"> <!-- 主要部分上 --><button class="card1"><image class="imgA" src="../../static/A.png"></image></button><butt…

Blazor 的基本原理探索

背景 为了提升开发效率&#xff0c;关键是对js不够熟悉&#xff0c;所以要使用C#进行全栈的开发&#xff0c;使用了mudblazor和radzen blazor&#xff0c;以及可能会用到其他的blazor组件&#xff0c;所有很有必要对blazor有个比较全面的不求甚解&#xff0c;其基本原理以及bl…

MVC设计模式和与三层架构的关系

MVC设计模式和与三层架构的关系 MVC是一种设计模式&#xff0c;将软件按照模型、视图、控制器来划分&#xff1a; M&#xff1a;Model&#xff0c;模型层&#xff0c;指工程中的JavaBean&#xff0c;作用是处理数据 JavaBean分为两类&#xff1a; 一类称为数据承载Bean&#x…