这次MATLAB算法的主题是排序算法(下图),参考资料和分类方法基本都是网络上第一,比如维基百科、CSDN等。 会附上原理部分,上面也会有**,便于直观理解,就不多说了。
1.插入排序。
.直接插入:
由于 MATLAB 中的向量长度不确定,因此写出的 ** 看起来很简单。 但实际上,插入排序要复杂得多。
由于二进制搜索在MATLAB的语法中没有找到使**简洁的技巧,因此直接被内置的向量操作所取代。
步骤:
1. 将 a[2] 与 a[1] 进行比较,如果 a[2] 较大,则跳到下一步; 如果 a[1] 较大,则将 a[2] 放在 a[1] 之前。
2. 将 a[3] 与 a[2] 进行比较,如果 a[3] 更大,则跳到下一步; 将 a[3] 与 a[1] 进行比较,如果 a[3] 较大,则在 a[1] 和 a[2] 之间插入 a[3]; 如果 a[1] 较大,则将 a[3] 放在 a[1] 之前。
3. 将 a[4] 与 a[3] 进行比较,如果 a[4] 更大,则跳到下一步; 将 a[4] 与 a[2] 进行比较,如果 a[4] 较大,则在 a[2] 和 a[3] 之间插入 a[4]; 如果 a[2] 较大,则将 a[4] 与 a[1] 进行比较,如果 a[4] 较大,则在 a[1] 和 a[2] 之间插入 a[4]; 如果 a[1] 较大,则将 a[4] 放在 a[1] 之前。
在遍历所有元素之前,排序完成。
例:
数组 a=[4 2 5 3 1]。
1. 将 4 与 2 进行比较,得到 a=[2 4 5 3 1]。
2. 将 5 与 4 进行比较,得到 a=[2 4 5 3 1]。
3. 比较 3 与 5、3<5、3 与 4、3<4、33 与 2、3>2,得到 a=[2 3 4 5 1]。
4. 比较 1 与 5、1<5、1 与 4、1<4、1 与 3、1<3、1 与 2、1<2,得到 a=[1 2 3 4 5] 完成。
2.山体排序:
Hill Sort 算法以其设计者 Donald Shell 的名字命名,于 1959 年发布,是 Insert Sort 的更高效、更改进的版本。 它不会一次做一个。 取而代之的是,初始选择大步幅(较大增量)间隔比较,使记录跳到接近其排序位置; 然后增量缩小; 最终增量为1,大大减少了记录的移动次数,提高了分拣效率。 Hill 排序对增量序列的选择没有严格的规则。 ”
与合并排序类似:
步骤:
1.取整数 d,将所有模数为 d 的记录视为一个组,并在每个组内插入和排序。
2.d = floor(d 2),按 d 重新组合以对插入物进行排序。
3.如果 d = 1,则重复步骤 2。
其他排序:1.鸡尾酒分拣
也就是说,略微变形的气泡分拣版本,效率更高。 可视化将非常有趣。
步骤:
已知数组 A 有 n 个元素。
1. 比较 a(1) 和 a(2),如果 a(1) > a(2),则将两者互换。 (将较大的移到后面)。
2、至a(2)、a(3); a(3)、a(4)..a(n-1) 和 a(n) 来比较整个未排序的数组。 (将最大的数字排在最后)。
3. 比较 a(n-1) 和 a(n-2),如果 a(n-1)4, a(n-2) 和 a(n-3); a(n-3)、a(n-4)..a(2) 和 a(1) 来比较整个未排序的数组。 (将最小的数字排在最前面)。
5. 对删除有序数字的数组重复该操作。 直到排序完成。
例:
数组 a=[4 2 5 7 3 1 6]。
做一次:a=[2 4 5 3 1 6 7]。
做一次:a=[1 2 4 5 3 6 7]。
重复:a=[1 2 4 3 5 6 7]。
重复:a=[1 2 3 4 5 6 7]。
2.猴子分拣
根据无限猴子定理,现在中文维基百科的**被缩短并变得有序(xyx)。
步骤:
1.重新随机化原始数组。
2.如果数组未按升序或降序排序,请重复 1。