算法
此算法参考我之前写的JS 教程算法,然后做改动。
在 Solidity 内主要是经济模型的算法，在其他语言内的各种排序算法，在合约内使用场景并不是很常见，之所以在这里罗列，是一起熟悉下思路，算法是很基础的逻辑训练途径，下面仅以插入排序喝冒泡排序作为例子。快速排序和数组去重作为扩展练习
插入排序
插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
操作步骤：首先选取数组的第一项即 ary[0]，我们可以认为这个数是已经安排好序的，再取 ary[1]项插入到已经排好序的元素中，此时只有 ary[0]，我们比较 ary[0]和 ary[1]；大于 ary[0]就放在后面，小于就插到 ary[0] 前面；要插入的元素依次为 ary[1]至 ary[ary.leng-1]项；插入到排序好的数组中的时候，插入每一项都需要从后面往前面遍历已经排序好的元素；
如果排序好的元素比插入的元素大，则把该元素往后挪一位，直到已经排序的元素小于等于要插入的元素（或者已经遍历完已经排好序的数组项），则把要插入的元素放在该位置+1 的索引位置中（反向排的时候，需要放在数组的第 0 个位置），对每个插入的元素都执行上面的操作，最终数组就是排序好的；
错误版本
把原来 JS 算法 里写的代码拷贝进来修改后，竟然错了。
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.18;
// [11,2,31,45,6,78,37,33,21] => [2, 6, 11, 21, 31, 33, 37, 45, 78]
contract Demo {
function insertSort(uint256[] memory ary)
public
pure
returns (uint256[] memory)
{
uint256 temp; //定义一个临时变量，保存要插入的值；
uint256 len = ary.length;
for (uint256 i = 1; i < len; i++) {
if (ary[i] < ary[i - 1]) {
temp = ary[i]; //需要插入的值；
uint256 pIndex = i - 1; //需要插入值的前一个索引；
while (temp < ary[pIndex] && pIndex >= 0) {
ary[pIndex + 1] = ary[pIndex]; //相当于ary[i]=ary[i-1];
ary[pIndex] = temp; //相当于ary[i-1]=temp;完成一波交换；
pIndex--; //准备下一波交换；
}
}
}
return ary;
}
}
报错信息如下：出现了 overflow了。
{
"error": "Failed to decode output: Error: overflow (fault=\"overflow\", operation=\"toNumber\", value=\"35408467139433450592217433187231851964531694900788300625387963629091585785856\", code=NUMERIC_FAULT, version=bignumber/5.5.0)"
}
这个代表超出了 uint256的范围了，uint256 的范围是 0 至115792089237316195423570985008687907853269984665640564039457584007913129639935，肯定不是运算超出最大值了，只能是计算时候超出最小值了；基本可以锁定 pIndex--; 这一句导致的错误，运行到 0-- 等于 -1 ，导致出错了。
修复如下
原理: 只需要让 pIndex-- 最小运行到 1-- 就可以解决溢出问题了。
而让
pIndex最小值等 1，则需要pIndex >= 1其他一次修改即可
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.18;
// [11,2,31,45,6,78,37,33,21] => [2, 6, 11, 21, 31, 33, 37, 45, 78]
contract Demo {
function insertSort(uint256[] memory ary)
public
pure
returns (uint256[] memory)
{
uint256 temp; //定义一个临时变量，保存要插入的值；
uint256 len = ary.length;
for (uint256 i = 1; i < len; i++) {
if (ary[i] < ary[i - 1]) {
temp = ary[i]; //需要插入的值；
// 原代码
// uint256 pIndex = i - 1; //需要插入值的前一个索引；
// while (temp < ary[pIndex] && pIndex >= 0) {
// 新代码
uint256 pIndex = i;
while (temp < ary[pIndex - 1] && pIndex >= 1) {
// 原代码
// ary[pIndex + 1] = ary[pIndex]; //相当于ary[i]=ary[i-1];
// ary[pIndex] = temp; //相当于ary[i-1]=temp;完成一波交换；
// 新代码
ary[pIndex] = ary[pIndex - 1]; //相当于ary[i]=ary[i-1];
ary[pIndex - 1] = temp; //相当于ary[i-1]=temp;完成一波交换；
pIndex--; //准备下一波交换；
}
}
}
return ary;
}
}
但是这个版本的代码还是有问题的，因为我们代码中的 temp < ary[pIndex - 1] && pIndex >= 1 这里的 temp < ary[pIndex - 1] 在 pIndex--;后 pIndex 为 0，而此时 ary[pIndex - 1] 又出现错误了。
再次修复如下
这时候我们需要使用短路规则，把条件位置换一下，因为我们要求 pIndex >= 1,当 pIndex 为 0 时候就不需要继续运行了。
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.18;
// [11,2,31,45,6,78,37,33,21] => [2, 6, 11, 21, 31, 33, 37, 45, 78]
contract Demo {
// 47897 gas
function insertSort(uint256[] memory ary)
public
pure
returns (uint256[] memory)
{
uint256 temp; //定义一个临时变量，保存要插入的值；
uint256 len = ary.length;
for (uint256 i = 1; i < len; i++) {
if (ary[i] < ary[i - 1]) {
temp = ary[i]; //需要插入的值；
uint256 pIndex = i;
while (pIndex >= 1 && temp < ary[pIndex - 1]) {
ary[pIndex] = ary[pIndex - 1]; //相当于ary[i]=ary[i-1];
ary[pIndex - 1] = temp; //相当于ary[i-1]=temp;完成一波交换；
pIndex--; //准备下一波交换；
}
}
}
return ary;
}
}
这下终于执行成功了。 查看调用成功的 gas，花费了 47897 gas；
然后我们再次开始怎么优化这些 gas。
优化后的最终版本
然后我们再看看怎么优化，
if (ary[i] < ary[i - 1])与temp < ary[pIndex - 1]重复判断了输入变量的位置 memory，可以改为
calldatai++可以改为++;pIndex--;可以改为--pIndex;内部声明的所有变量，都可以提到循环外
最终的版本: gas 消耗从最开始的 47897 gas 优化成了 41125 gas
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.18;
// [11,2,31,45,6,78,37,33,21]
// => [2, 6, 11, 21, 31, 33, 37, 45, 78]
// 47897 gas
// ...
// 41125 gas
contract Demo {
// 47897 gas
function insertSort(uint256[] calldata ary)
public
pure
returns (uint256[] memory)
{
uint256[] memory tempArr = ary;
uint256 temp; //定义一个临时变量，保存要插入的值；
uint256 len = tempArr.length;
uint256 pIndex; // 上一个值
for (uint256 i = 1; i < len; ++i) {
temp = tempArr[i]; //需要插入的值；
pIndex = i;
while (pIndex >= 1 && temp < tempArr[pIndex - 1]) {
tempArr[pIndex] = tempArr[pIndex - 1]; //相当于ary[i]=ary[i-1];
--pIndex; //准备下一波交换；
}
tempArr[pIndex] = temp; //相当于ary[i-1]=temp; 因为上面 pIndex-- 了
}
return tempArr;
}
}
冒泡排序
冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 算法步骤：
1）比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3）针对所有的元素重复以上的步骤，除了最后一个。
4）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
contract Demo2 {
function sortAry(uint256[] calldata ary)
public
pure
returns (uint256[] memory)
{
uint256[] memory tempArr = ary;
uint256 len = tempArr.length; //获取数组的长度；有aryLen个数在排序；
uint256 temp; //临时变量，交换数据中用的
bool flag = false; //设置标志位，初始化为false
for (uint256 i = 0; i < len - 1; ++i) {
//外层循环n-1次；
for (uint256 j = 0; j < len - 1 - i; ++j) {
//每次循环完，都能从剩下的数组中找出个最大的数组放在 len-1-i 的位置；
if (tempArr[j] > tempArr[j + 1]) {
temp = tempArr[j];
tempArr[j] = tempArr[j + 1];
tempArr[j + 1] = temp;
flag = true; //如果交换好了，做个标记，避免无效的循环；
}
}
if (!!flag) {
//只要交换了位置，flag的值就重新设置为false了；
flag = false;
} else {
//如果没有交换，说明数组已经排好序了，可以结束循环了；
break;
}
}
return tempArr;
}
}
实战应用
快速排序和数组去重作为扩展练习，自己可以动手实现。
实现快速排序
实现数组去重
问答题
插入排序的写法
function insertSort(uint256[] calldata ary) public pure returns (uint256[] memory) { uint256[] memory tempArr = ary; uint256 temp; //定义一个临时变量，保存要插入的值； uint256 len = tempArr.length; uint256 pIndex; // 上一个值 for (uint256 i = 1; i < len; ++i) { temp = tempArr[i]; //需要插入的值； pIndex = i; while (pIndex >= 1 && temp < tempArr[pIndex - 1]) { tempArr[pIndex] = tempArr[pIndex - 1]; //相当于ary[i]=ary[i-1]; --pIndex; //准备下一波交换； } tempArr[pIndex] = temp; //相当于ary[i-1]=temp; 因为上面 pIndex-- 了 } return tempArr; }if (ary[i] < ary[i - 1])与temp < ary[pIndex - 1]重复判断了输入变量的位置 memory，可以改为
calldatai++可以改为++;pIndex--;可以改为--pIndex;内部声明的所有变量，都可以提到循环外