学习部分排序、插入排序、气泡排序和希尔排序。
1.插入排序
<1>.首先我们举个例子
我们要把6进行前面的插入,那我们要进行比较,首先确定一个end的指针,然后他指向的数字就是我们需要比较的,如果end指向的数比我们end+1 的大的话,那我们就往前挪一个,让end指向的数位置换到刚才end+1 的位置,也就是6的位置。然后end--,如果end指向的数比6小大,我们循环停止。如果按照我们的例子来看,那么就应该是这样的
那么我们前面的的数怎么办,他们还没有成为有序的数组,那如果我们前面一开始就是有序的,那么是不是从后面开始比较,然后停止的时候,是不是就全都是有序的。那我们如果从一开始,一点一点让他们成为有序的,一直到end指向数组最后一个数的前一个数,然后进行刚才的比较,那么全都是有序的。也就是说应该是这样的
第一次单个3就算是有序的数组,然后和五进行比较
第二次,3 5 和8进行比较然后3 5 8就是有序的
第三次,3 5 8和4 开始比较,那么按照顺序就是 3 4 5 8.。。。。依次类推,然后 我们就得到了排序
那么end就是在有序数组的最后一个,然后把end+1的位置存进tmp,如果比较成立,end的数字向后移动,覆盖end+1位置的数,当如果是逆序排列,end就会到达-1的位置,那么遍历也就结束了,这也成为了我们while的判断条件
void InsertSort(int* arr, int n)
{
for(int i=0;i<n-1;i++)
{
int end=i;
int tmp = arr[end + 1];
while (end >= 0)
{
if (arr[end] > tmp)
{
arr[end + 1] = arr[end];
end--;
}
else
{
break;
}
}
arr[end + 1] = tmp;
}
}
代码就是这样写的
提醒大家的是while循环结束后,把end+1的位置放tmp,就是我们每次较完之后end,如果要进行挪动,那么end最后的位置就是空的,那么我们就要把刚才存的end+1的位置的数字tmp存进去。
2冒泡排序
冒泡排序我们在c语言里面实现过我们就不多说了
第一层循环时为了把第一个数依次向后比较,第二层控制第一层进行比较的次数,第一次,最后一个数就排好了,那么第一层循环就少了一层。
void BubbleSort(int* arr, int n)
{
for (int i = 0; i < n-1; i++)
{
int exchang = 0;
for (int j = 1; j < n - i; j++)
{
if (arr[j - 1] > arr[j])
{
Swap(&arr[j - 1], &arr[j]);
exchang = 1;
}
}if (exchang == 0)
{
break;
}
}
}
void Swap(int* x, int* y)
{
int t = *x;
*x = *y;
*y = t;
}
3.希尔排序
希尔排序时我们以插入排序为基础,比之前有点难度。、
按照之前的希尔排序在我们设立的每次依次分的有序数组,他进行规范行的分组,画图
假设我们每次规定的一个数组是间隙三个的,然后我们第一次调整蓝色的有序数组,那么第一次就是3为有序数组,然后和4 比较,接着3 4和7 比较
接着红色这组,再然后绿色的。这样遍历就可以。我们红色算一组,可以按照刚才的插入的排序写一个循环,我们怎么知道我们要循环几次,其实间隙是几,我们就循环几次。先实现一下。
int gap = 3;这个写法是进行固定一个小组进行轮换,然后在进行下一个小组
for (int j = 0; j < gap; j++)//间隙有几个就进行几次循环
{
for (int i = 0; i < n - gap; i+=gap)i<gap这样的话最后的end不会越界
{
int end = i;
int tmp = arr[end + gap];
while (end >= 0)
{
if (arr[end] > tmp)
{
arr[end + gap] = arr[end];
}
else
{
break;
}
}
arr[end+gap]=tmp;
}
}
n是数组个数,我们为什么要让i小于n-gap(间隙),刚才插入排序是不是小于n-1,其实道理差不多,如果我们end按照间隙加,那最后一次如果超过n不就越界访问了,所以让end<n-gap,使得找end+gap的情况不越界。
那么我们的间隙该怎么定呢。间隙越大,换的越快,越不接近有序数组。间隙越小,换的越慢,越接近有序数组。那我们如果让间隙是变化的,那这样不久越来越好了。应该从大往小变,为什么,第一次间隙为1,直接写成插入排序了。哈哈哈哈。但是这这只是预排序,那么之后该怎么排序才能完全成为有序的呢。那么我们最后一次进行插入排序是不是就可以了。那么正好是不是和刚才的间隙对应上了,如果我们让间隙从大变小,直到变为1,那就完成了希尔排序。第一次的间隙我们取数组的一半,为什么?你想想如果比一半大,那还能找到end+gap的数嘛,直接越界了。哈哈哈哈哈哈哈哈哈哈哈哈。
void ShellSort(int* arr, int n)
{
int gap = n;
while (gap)
{
gap /= 2;
for (int i = 0; i < n - gap; i++)//从每个的头开始依次遍历,进行循环调整
{
int end = i;
int tmp = arr[end + gap];
while (end <n)
{
if (arr[end] > tmp)
{
arr[end + gap] = arr[end];
end -= gap;
}
else
{
break;
}
}
arr[end + gap] = tmp;
}
}
}
有没有发现和刚才不一样,for循环从两个变成一个了,我们进行了改进,反正我们从蓝色完了就是红色,再然后就是绿色。那我们直接从第一个开始依次加间隙,直到end加间隙越界,不就行了。也就是蓝色组第一个,接着红色组第一个,绿色组第一个,然后蓝色第二个。。。。
感谢观看,欢迎指出错误。
推荐阅读
-
正负偏差变量 即 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,最优利润为
-
学习部分排序、插入排序、气泡排序和希尔排序。
-
经典排序算法和 python 详情(II):冒泡排序、双向冒泡排序、插入排序和希尔排序
-
气泡排序和一些优化
-
气泡排序(超级详细)--升序",从小到大;另一种是 "降序",从大到小。该主题可抽象为 "按升序对 n 个数字排序 "的一般形式。 排序是一种重要的基本算法。排序的方法有很多种,但在本题中我们将使用冒泡排序法。 冒泡法的基本思想 冒泡法的基本思想是,每次比较相邻的两个数字时,较小的那个会被移到前面。如果有 5 个数字9,8,5,2,0,第一次将前两个数字 8 和 9 互换。第二次将第二个和第三个数字(9 和 5)对调......这样一共对调 4 次,得到 8-5-2-0-9 的顺序,可以看到:最大的数字 9 一直在 "下沉",成为最下面的一个数字,而小的数字 "上升" 最小的数字 "上升"。最小的数字 0 已经向上 "浮 "了一个位置。经过第一次比较(共 4 次比较和交换),得到了最大的数字 9。 然后进行第二趟比较,对剩下的前 4 个数字(8、5、2、0)进行新一轮比较,这样第二个最大的数字就 "沉到了底部"。同样,按照上述方法进行第二轮比较。经过 3 次比较和交换,我们得到了第二大数 8。 按照这个规律,我们可以推断出,比较 5 个数字需要 4 次旅行,才能将 5 个数字从小到大排列起来。在第一次旅行中,两个数字之间进行了 4 次比较,在第二次旅行中,进行了 3 次比较......在第四次旅行中,只进行了一次比较。 思路总结 总结:如果有 n 个数字,那么要进行 n-1 次比较。在第一次行程中进行 n-1 次比较,在第 i 次行程中进行 n-i 次比较。
-
一分钟内透彻理解 JavaScript 的气泡排序和选择排序功能
-
气泡排序、两种实现方式和优化
-
排序算法:冒泡排序、插入排序、选择排序、希尔排序
-
经典气泡排序和优化气泡排序法
-
六种排序] Final : 泡泡排序和快速排序决赛:气泡排序和快速排序