C - 泡沫排序和快速排序
前言
交换排序有冒泡排序和快速排序这两种,
基本思想:所谓交换,就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置,交换排序的特点是:将键值较大的记录向序列的尾部移动,键值较小的记录向序列前部移动。
一、冒泡排序
1.简介
冒泡排序是一种计算机科学领域的较简单的排序算法。
基本原理:对元素个数为 N 的待排序序列进行排序时,共进行N-1次循环。在第 k 次循环中,对从第1到第N-k个元素从前往后进行比较,每次比较相邻的两个元素,若前一个元素大于后一个元素,则两者互换位置,否则保持位置不变。
时间复杂度:O(n²) 空间复杂度:O(1) 稳定性:稳定
2.算法思路
动态显示图,充分理解冒泡排序
从图中我们可以看见
1.每一次比较都是相邻的两个数,例如图中有15个元素,则比较的下标值是[0,1],[1,2],[2,3],[3,4],[4,5],[5,6],[6,7],[7,8],[8,9],…,[13,14]。共14趟。
2. **第一趟:**先从下标值0开始,每一次比较都是和后一个元素,如果后一个元素大于前一个元素,则进行交换,然后再进行后一个元素的比较,直到与末尾元素比较。此时末尾元素是最大值。
3. 第二趟开始,不需要比较末尾元素了,因为第一趟就是将最大值放在末尾。也就是说需要比较剩余的14个元素,重复步骤二,找到第二大的元素。
4. 依次下去,将大的元素排在后面,就形成了从小到大的有序序列
3.代码实现
#include <stdio.h> void Swap(int* px, int* py) { int tmp = *px; *px = *py; *py = tmp; } void BubbleSort(int* a, int n) { int end = n; while (end > 0) { int exchange = 0; for (int i = 1; i < end; ++i) { //当下一个元素大于当前元素时,进行交换 if (a[i - 1] > a[i]) { exchange = 1; Swap(&a[i - 1], &a[i]); } } --end; //当元素未进行交换,则本就是有序,直接结束循环 if (exchange == 0) { break; } } } int main() { int a[] = { 26, 2, 5, 3, 9, 4, 8, 5, 1, 7 }; BubbleSort(a, 10); for (int i = 0; i < 10; i++) { printf("%d ", a[i]); } }
注:如果序列是有序的,可以局部变量来判断,可以减少运行时间,提高效率。
运行结果:
二、快速排序
1.简介
快速排序是Hoare于1962年提出的一种二又树结构的交换排序方法。
基本思想: 任取待排序元素序列中为某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。
时间复杂度:O(N*logN) 空间复杂度:O(logN) 稳定性:不稳定
2.算法思路
快速排序一般有三种方法:左右指针法、挖坑法、前后指针法。而这三种都需要利用到递归方法。
2.1左右指针法
思路:
在待排序序列中,取一个元素为key,key为初始元素或者末尾元素。
此时取初始元素为key,右边开始遍历,当遍历到比key值小的元素时,停止;开始左边遍历,当左边遍历到比key元素小的时候,进行左右交换。
然后重复操作,直到两边指针相遇。此时左指针的值和key进行交换。然后再按照以上方法进行递归实现【left,keyi】和【keyi+1,right】,keyi是key的下标值
注:key选初始元素,右边先开始遍历;选末尾元素,则左边先开始遍历
动态展示图:
图片详解图:
绿色交换,是指左指针和右指针相遇之后和key交换;
红色(黄色)交换,是指左右指针的值交换。
从图我们可以看出来,每一次排序,都是将待排序分成2部分,一部分是比key小的,一部分是比key大的,再通过递归的方法,逐次排序。
代码实现:
void swap(int* w, int* t) { int tem = *w; *w = *t; *t = tem; } int Partion1(int* p, int left, int right) { //keyi值可进行改进,在文章结尾 int keyi = left; while (left < right) { while (left < right && p[right] >= p[keyi]) { right--; } while (left < right && p[left] <= p[keyi]) { left++; } swap(&p[left], &p[right]); } swap(&p[left], &p[keyi]); return left; } void Text1(int *p,int left,int right) { if (left >= right) return; int key=Partion1(p, left, right); //递归方法 Text1(p, left, key - 1); Text1(p, key + 1,right); } int main() { int arr[10]={6,1,2,7,9,3,5,10,8}; Text1(arr,0,9); for(int i=0;i<10;i++) { printf("%d ",arr[i]); } }
2.2挖坑法
思路:
先将最左边的值保存下来,作为key值。
将最左边的值抽出来了,然后右边遍历,遍历到比key小的值,填入坑中。相当于把数移到了坑里,而自身留下了坑位,然后左遍历,遍历到比key大的值,再移到右边的坑里。
重复上述操作,直到左右指针相遇,再把key的值填入相遇的位置。
注:思路和左右指针法是相似的。key选初始元素,右边先开始遍历;选末尾元素,则左边先开始遍历
代码实现:
void swap(int* w, int* t) { int tem = *w; *w = *t; *t = tem; } int Partion2(int* p, int left, int right) { //记录keyi的值。keyi值可进行改进,在文章结尾 int keyi = p[left]; int priot = left; while (left < right) { while (left < right && p[right] >= keyi) { right--; } p[priot] = p[right]; priot = right; while (left < right && p[left] <= keyi) { left++; } p[priot] = p[left]; priot = left; } swap(&p[left], &keyi); return left; } void Text1(int *p,int left,int right) { if (left >= right) return; int key=Partion2(p, left, right); //递归方法 Text1(p, left, key - 1); Text1(p, key + 1,right); } int main() { int arr[10]={6,1,2,7,9,3,5,10,8}; Text1(arr,0,9); for(int i=0;i<10;i++) { printf("%d ",arr[i]); } }
2.3前后指针法
思路:
1、选出一个key,一般是最左边或是最右边的。
2、起始时,prev指针指向序列开头,cur指针指向prev+1。
3、若cur指向的内容小于key,则prev先向后移动一位,然后交换prev和cur指针指向的内容,然后cur指针++;若cur指向的内容大于key,则cur指针直接++。如此进行下去,直到cur到达end位置,此时将key和++prev指针指向的内容交换即可。
经过一次单趟排序,最终也能使得key左边的数据全部都小于key,key右边的数据全部都大于key。
然后也还是将key的左序列和右序列再次进行这种单趟排序,如此反复操作下去,直到左右序列只有一个数据,或是左右序列不存在时,便停止操作
简单而言就是:cur找到比key小的就停下来,然后++prev,然后cur的值和prev的值交换,cur就再次继续向前移动,直到cur到最右边。
图片展示:
注:图中是两种前后指针的示意图,如果右边做key,cur指向下标为1,prev则是在后面;如果左边做key,cur则指向下标为2的值,prev也是在后面。
代码展示
void swap(int* w, int* t) { int tem = *w; *w = *t; *t = tem; } int Partion3(int* p, int left, int right) { int prev = left; int cur = left + 1; int keyi = left; while (cur <= right) { while (cur<=right&&a[cur] >= a[keyi]) { cur++; } if (cur <= right) { swap(&a[cur], &a[++prev]); cur++; } } swap(&a[prev], &a[keyi]); return prev; } void Text1(int *p,int left,int right) { if (left >= right) return; int key=Partion3(p, left, right); //递归方法 Text1(p, left, key - 1); Text1(p, key + 1,right); } int main() { int arr[10]={6,1,2,7,9,3,5,10,8}; Text1(arr,0,9); for(int i=0;i<10;i++) { printf("%d ",arr[i]); } }
改进:在左右指针和挖坑法里,有时候数组的第一个元素或者最后一个元素是序列里最小的,就面对了最坏的情况,如此效率就会下降,为了提高效率,我们将key为三数取中,即第一个元素,中间元素和最后一个元素里取值中的元素。先找到中间元素,然后与key进行互换。
方法如下:
上一篇: 气泡排序和优化详解
推荐阅读
-
[排序算法] 快速排序(Fast Sort)!示意图 + 实现细节!
-
如何在 Windows 上使用 WSL 和 VSCode 快速创建 C 语言开发环境
-
数据结构 - 八种排序(如下)、气泡排序、快速排序、陷阱排序、归一化排序
-
C92 树阵列 + 排序 P4113 [HEOI2012] 采花
-
[广度优先搜索] [拓扑排序] [C++ 算法] 913.猫和老鼠
-
快速排序的四种 Python 实现
-
LOJ2848 "ROI 2018 Day 2 "快速排序 [构建]
-
图解快速排序算法--双端检测法
-
正负偏差变量 即 d2+、d2- 分别表示决策值中超出和未达到目标值的部分。而 di+、di- 均大于 0 刚性约束和目标约束(柔性目标约束有偏差) 在多目标规划中,>=/<= 在刚性约束中保持不变。当需要将约束条件转换为柔性约束条件时,需要将 >=/<= 更改为 =(因为已经有 d2+、d2- 用来表示正负偏差),并附加上 (+dii-di+) 注意这里是 +di、-di+!之所以是 +di,-di+,是因为需要将目标还原为最接近的原始刚性约束条件 优先级因素和权重因素 对多个目标进行优先排序和优先排序 目标规划的目标函数 是所有偏差变量的加权和。值得注意的是,这个加权和都取最小值。而 di+ 和 dii- 并不一定要出现在每个不同的需求层次中。具体分析需要具体问题具体分析 下面是一个例子: 题目中说设备 B 既要求充分利用,又要求尽可能不加班,那么列出的时间计量表达式即为:min z = P3 (d3- + d3 +) 使用 + 而不是 -d3 + 的原因是:正负偏差不可能同时存在,必须有 di+di=0 (因为判定值不可能同时大于目标值和小于目标值),而前面是 min,所以只要取 + 并让 di+ 和 dii- 都为正值即可。因此,得出以下规则: 最后,给出示例和相应的解法: 问题:某企业生产 A 和 B 两种产品,需要使用 A、B、C 三种设备。下表显示了与工时和设备使用限制有关的产品利润率。问该企业应如何组织生产以实现下列目标? (1) 力争利润目标不低于 1 500 美元; (2) 考虑到市场需求,A、B 两种产品的生产比例应尽量保持在 1:2; (3)设备 A 是贵重设备,严禁超时使用; (4)设备 C 可以适当加班,但要控制;设备 B 要求充分利用,但尽量不加班。 从重要性来看,设备 B 的重要性是设备 C 的三倍。 建立相应的目标规划模型并求解。 解:设企业生产 A、B 两种产品的件数分别为 x1、x2,并建立相应的目标计划模型: 以下为顺序求解法,利用 LINGO 求解: 1 级目标: 模型。 设置。 variable/1..2/:x;! s_con_num/1...4/:g,dplus,dminus;!所需软约束数量(g=dplus=dminus 数量)及相关参数; s_con(s_con_num);! s_con(s_con_num,variable):c;!软约束系数; 结束集 数据。 g=1500 0 16 15. c=200 300 2 -1 4 0 0 5; 结束数据 min=dminus(1);!第一个目标函数;!对应于 min=z 的第一小部分;! 2*x(1)+2*x(2)<12;!硬约束 @for(s_con_num(i):@sum(variable(j):c(i,j)*x(j))+dminus(i)-dplus(i)=g(i)); !使用设置完成的数据构建软约束表达式; ! !软约束表达式 @for(variable:@gin(x)); !将变量约束为整数; ! 结束 此时,第一级目标的最优值为 0,第一级偏差为 0: 第二级目标: !求 dminus(1)=0,然后求解第二级目标。 模型。 设置。 变量/1..2/:x;!设置:变量/1..2/:x; ! s_con_num/1...4/:g,dplus,dminus;!软约束数量及相关参数; s_con(s_con_num(s_con_num));! s_con(s_con_num,variable):c;! 软约束系数; s_con(s_con_num,variable):c;! 结束集 数据。 g=1500 0 16 15; c=200 300 2 -1 4 0 0 5; 结束数据 min=dminus(2)+dplus(2);!第二个目标函数 2*x(1)+2*x(2)<12;!硬约束 @for(s_con_num(i):@sum(variable(j):c(i,j)*x(j))+dminus(i)-dplus(i)=g(i)); ! 软约束表达式;! dminus(1)=0; !第一个目标结果 @for(variable:@gin(x)); ! 结束 此时,第二个目标的最优值为 0,偏差为 0: 第三目标 !求 dminus(2)=0,然后求解第三个目标。 模型。 设置。 变量/1..2/:x;!设置:变量/1..2/:x; ! s_con_num/1...4/:g,dplus,dminus;!软约束数量及相关参数; s_con(s_con_num(s_con_num));! s_con(s_con_num,variable):c;! 软约束系数; s_con(s_con_num,variable):c;! 结束集 数据。 g=1500 0 16 15; c=200 300 2 -1 4 0 0 5; 结束数据 min=3*dminus(3)+3*dplus(3)+dminus(4);!第三个目标函数。 2*x(1)+2*x(2)<12;!硬约束 @for(s_con_num(i):@sum(variable(j):c(i,j)*x(j))+dminus(i)-dplus(i)=g(i)); ! 软约束表达式;! dminus(1)=0; !第一个目标约束条件; ! dminus(2)+dplus(2)=0; !第二个目标约束条件 @for(variable:@gin(x));! 结束 最终结果为 x1=2,x2=4,dplus(1)=100,最优利润为
-
学习部分排序、插入排序、气泡排序和希尔排序。