Skip to content

Files

Latest commit

0c53238 · Jun 25, 2024

History

History

10_InsertionSort

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
Jun 24, 2022
Mar 13, 2024
Jun 25, 2024
title tags
10. 控制流
solidity
basic
wtfacademy
if-else/for/while/ternary

WTF Solidity极简入门: 10. 控制流,用Solidity实现插入排序

我最近在重新学 Solidity,巩固一下细节,也写一个“WTF Solidity极简入门”,供小白们使用(编程大佬可以另找教程),每周更新 1-3 讲。

推特:@0xAA_Science@WTFAcademy_

社区:Discord微信群官网 wtf.academy

所有代码和教程开源在 github: github.com/AmazingAng/WTF-Solidity


这一讲,我们将介绍Solidity中的控制流,然后讲如何用Solidity实现插入排序(InsertionSort),一个看起来简单,但实际上很容易写出bug的程序。

控制流

Solidity的控制流与其他语言类似,主要包含以下几种:

  1. if-else

    function ifElseTest(uint256 _number) public pure returns(bool){
        if(_number == 0){
            return(true);
        }else{
            return(false);
        }
    }
  2. for循环

    function forLoopTest() public pure returns(uint256){
        uint sum = 0;
        for(uint i = 0; i < 10; i++){
            sum += i;
        }
        return(sum);
    }
  3. while循环

    function whileTest() public pure returns(uint256){
        uint sum = 0;
        uint i = 0;
        while(i < 10){
            sum += i;
            i++;
        }
        return(sum);
    }
  4. do-while循环

    function doWhileTest() public pure returns(uint256){
        uint sum = 0;
        uint i = 0;
        do{
            sum += i;
            i++;
        }while(i < 10);
        return(sum);
    }
  5. 三元运算符

    三元运算符是Solidity中唯一一个接受三个操作数的运算符,规则条件? 条件为真的表达式:条件为假的表达式。此运算符经常用作if语句的快捷方式。

    // 三元运算符 ternary/conditional operator
    function ternaryTest(uint256 x, uint256 y) public pure returns(uint256){
        // return the max of x and y
        return x >= y ? x: y; 
    }

另外还有continue(立即进入下一个循环)和break(跳出当前循环)关键字可以使用。

Solidity实现插入排序

写在前面:90%以上的人用Solidity写插入算法都会出错。

插入排序

排序算法解决的问题是将无序的一组数字,例如[2, 5, 3, 1],从小到大依次排列好。插入排序(InsertionSort)是最简单的一种排序算法,也是很多人学习的第一个算法。它的思路很简单,从前往后,依次将每一个数和排在他前面的数字比大小,如果比前面的数字小,就互换位置。示意图:

插入排序

python代码

我们可以先看一下插入排序的python代码:

# Python program for implementation of Insertion Sort
def insertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while j >=0 and key < arr[j] :
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
    return arr

改写成Solidity后有BUG

一共8行python代码就可以完成插入排序,非常简单。那么我们将它改写成Solidity代码,将函数,变量,循环等等都做了相应的转换,只需要9行代码:

    // 插入排序 错误版
function insertionSortWrong(uint[] memory a) public pure returns(uint[] memory) {    
    for (uint i = 1;i < a.length;i++){
        uint temp = a[i];
        uint j=i-1;
        while( (j >= 0) && (temp < a[j])){
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = temp;
    }
    return(a);
}

那我们把改好的放到remix上去跑,输入[2, 5, 3, 1]。BOOM!有bug!改了半天,没找到bug在哪。我又去google搜”solidity insertion sort”,然后发现网上用solidity写的插入算法教程都是错的,比如:Sorting in Solidity without Comparison

Remix decoded output 出现错误内容

10-1

正确的Solidity插入排序

花了几个小时,在Dapp-Learning社群一个朋友的帮助下,终于找到了bug所在。Solidity中最常用的变量类型是uint,也就是无符号整数,取到负值的话,会报underflow错误。而在插入算法中,变量j有可能会取到-1,引起报错。

这里,我们需要把j加1,让它无法取到负值。正确代码:

// 插入排序 正确版
function insertionSort(uint[] memory a) public pure returns(uint[] memory) {
    // note that uint can not take negative value
    for (uint i = 1;i < a.length;i++){
        uint temp = a[i];
        uint j=i;
        while( (j >= 1) && (temp < a[j-1])){
            a[j] = a[j-1];
            j--;
        }
        a[j] = temp;
    }
    return(a);
}

运行后的结果:

"输入[2,5,3,1] 输出[1,2,3,5] "

总结

这一讲,我们介绍了Solidity中控制流,并且用Solidity写了插入排序。看起来很简单,但实际很难。这就是Solidity,坑很多,每个月都有项目因为这些小bug损失几千万甚至上亿美元。掌握好基础,不断练习,才能写出更好的Solidity代码。