当前位置：首页 > news >正文

广州企业建站公司镇江网站托管

news 2026/4/17 13:53:45

广州企业建站公司,镇江网站托管,罗湖住房和建设局网站官网,app下载网址进入前言本篇文章我们先会学习快速排序这个算法#xff0c;之后我们会学习sort这个函数分治算法在学习快速排序之前#xff0c;我们先来学习一下分治算法#xff0c;快速排序就是分治算法的一种#xff0c;下面是分治算法的介绍#xff0c; 分治算法#xff0c;就是”…前言本篇文章我们先会学习快速排序这个算法之后我们会学习sort这个函数分治算法在学习快速排序之前我们先来学习一下分治算法快速排序就是分治算法的一种下面是分治算法的介绍分治算法就是”分而治之“ 分为分解、治理和合并这三个步骤后面我们学习快速排序也是从这三个步骤入手简单来说分治算法就是将一个大问题分解成许多小的问题又因为这些小的问题的解决方案与大问题相同只是规模更小而已所以当子问题划分得足够小时就可以用很简单的方法来解决原本看起来很复杂的大问题。通过上面的学习我们可以看出快速排序就是分治算法中的一种快速排序算法可优化版本基本步骤分解首先将数组中的一个元素作为pivot轴点 / 基准点可以理解为分界点之后从最左侧的元素和最右侧的元素开始遍历比轴点大的放到最右侧比轴点小的就放到最左侧对于轴点的选择我们可以选择数组首元素作为轴点或者最后一个元素又或者是数组中的任意一个元素治理一次排序完成后分别对轴点左侧和右侧的剩余元素进行排序使用递归重复上面的步骤合并将最终排序好的各个子串合并到一起就实现了快速排序这个算法基本思想就是这样下面让我们来逐步实现分步实现排序一次首先以首元素作为基准点一般都是第一个元素赋值给pivot变量数组最左侧元素下标赋值给left变量最右侧下标赋值给right这个变量然后从右向左开始逐个与轴点比较当其小于轴点时将这个元素与这个串中left下标指向的元素位置互换left向右移动一位然后从左向右开始逐个与轴点比较当其大于轴点时将这个元素与这个串中right指向的那个元素互换right向左移动一位重复二三步直到left与right重合一次排序完成对分割后的子串进行排序排序完一次之后轴点左侧的元素比轴点小右侧的元素比轴点大之后分别对左侧的子串和右侧的子串进行排序此处需要使用递归直到传入的参数leftright时开始回归又因为函数返回类型是void那么也就可以理解为函数调用结束数组排序完成例子图解下面通过对一个数组进行排序来更生动的去学习这个算法以数组6 1 2 7 9 3 4 5 10 8为例下面只解释第一次排序的过程选取轴点首先选取首元素6作为轴点进行第一次排序如图所示从右向左开始排序从8开始向左逐个查找查找到5的时候发现5比轴点小那么就将5这个元素与轴点也就是left下标指向的元素互换left向右移动一位跳过已经排序完的元素right变为轴点所在的下标如图从右向左排序从left所指向的元素开始与轴点比较当遇到比轴点大的就与轴点互换然后right–向左移动一位跳过已经排序完的元素left变为轴点所在的下标继续排序重复以上两步先从右侧开始向左查找替换、再从左向右开始查找替换当left和right重合时说明本次查找完成递归查找剩下的子串通过上面的学习我们可以知道对与一个串的排序其基本操作是一样的只不过规模大小不同罢了这就是分治算法中提到的分解与治理代码实现基本步骤和具体思路都介绍完了剩下的就是通过代码去实现它了函数主体 int main() {int a[10001];int N;cout 请输入要排序的元素个数 endl;cin N;cout 请输入要排序的元素 endl;for (int i 0; i N; i){cin a[i];}cout endl;//可有可无此处换行只是为了美观Quicksort(a, 0, N - 1);cout 排序后的数组结果 endl;for (int i 0; i N; i){cout a[i] ;//这里输入一个空格也是为了美观方便阅读}cout endl;return 0; }Quicksort函数就是实现递归排序的函数 Quicksort函数 void Quicksort(int* r, int left, int right) {int mid 0;if (left right){mid part(r, left, right);Quicksort(r, left, mid - 1);Quicksort(r, mid 1, right);} } part函数是实现一次排序的函数 part函数 part函数是实现一次排序的函数并且part函数返回的是一次排序完成后的新的基准值就是left和right下标重合的位置 int part(int* r, int left, int right) {int i left;int j right;int pivot r[left];//选择首元素作为基准点while (i j){while (ij r[j]pivot)//从右向左查找小于基准点的元素{j--;}if (i j){swap(r[i], r[j]);//交换基准点和left下标的元素并且left下标向右移动一位}while (i j r[i] pivot)//从左向右查找大于基准点的元素{i;}if (i j){swap(r[i], r[j--]);交换基准点和right下标的元素并且right下标向左移动一位}return i;//返回的是最终划分完成后人即left和right重合的新的基准点//作为字串的left或right的下标}} swap函数在part函数中为了更快捷的将两个元素互换我们使用到了swap函数下面就对swap函数做一个简单的介绍 swap(a, b);这个函数很厉害它不仅可以交换整型、浮点型它还可以交换结构体当然成员个数得一样下面给一个交换结构体的例子 #includeiostream #includestring #includealgorithm//sort函数包含的头文件 using namespace std; //定义一个学生类型的结构体 typedef struct student {string name; //学生姓名int achievement; //学生成绩 } student;//用来显示学生信息的函数 void show(student * stu, int n) {for (int i 0; i n; i){cout 姓名: stu[i].name \t 成绩: stu[i].achievement endl;} }int main() {student stu1[] { {李四,87},{王二,100} };student stu2[] { {22,2},{33,3} };cout 交换前 endl;show(stu1, 3);show(stu2, 3);swap(stu1, stu2);cout 交换后 endl;show(stu1, 3);show(stu2, 3);return 0; } 并且使用swap函数不用担心精度的损失补充说明对于排序方式的解释对于为什么要先从右向左开始查找同学们可能会有疑惑那么我们不妨试一试先从左向右查找看看结果如何还是以“6 1 2 7 9 3 4 5 10 8”这个数组为例子第一次排序时我们先让left从左边开始遇到小于等于6的继续走大于6的停下于是left停在了7的位置再让right从右边走小于6的时候停下于是right停在5的位置这个时候left right 于是7和5交换位置变成“6 1 2 5 9 3 4 7 10 8” 继续上面的操作9和4交换变成“6 1 2 5 4 3 9 7 10 8”继续left先移动停在了9的位置这个时候left right了那么这一轮就比较完了最后需要交换left和pivot位置的数基准数归位这个时候6与9交换变成了下面的序列“9 1 2 5 4 3 6 7 10 8” 这个序列并不是完成了一轮处理之后基准数左边的都比基准数小右边的都比它大。所以这样先从左边开始搜索得不到正确结果的。因此我们可以得到下面的结论当基准数选择最左边的数字时那么就应该先从右边开始搜索当基准数选择最右边的数字时那么就应该先从左边开始搜索。不论是从小到大排序还是从大到小排序快速排序的优化其实我们不需要每次遇到比轴点大 / 比轴点小的元素就与轴点进行交换可以直接将这两个元素交换再移动left与right直到二者相等这就完成了一次排序再将轴点更新为left下标所在的位置进行递归排序至于具体的代码我还没想明白在此只是提出这个思路之后再去实现快速排序与冒泡排序冒泡排序我们都知道这里就不再重复叙述快速排序与冒泡排序相比快速排序的优点是快速排序的每次交换是跳跃式的就是距离很大当轴点左侧的元素大于轴点时会被直接放到右侧right指针所指向的位置这样交换时跨越的距离是很大的而冒泡排序每次只能是相邻的两个元素进行比较这样就比较低效了结语关于快速排序这个算法知识就介绍到这里了希望大家都有所收获我们下篇文章见~

查看全文

http://www.hkea.cn/news/14301930/