白天搞智能合约，晚上撸前端代码，只要咖啡还续着，凌晨照样在线！会说 Solidity、PHP、Node.js，还有 Vue 和 HTML 的“方言”，代码不怕我不写，就怕写完跑太快。Bug？那都是小场面，一出手就搞定。我的宗旨是——交付准时，调试无敌，客户满意才是真理！

10. 控制流，用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] "

完整合约

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.21;
contract InsertionSort {
    // if else
    function ifElseTest(uint256 _number) public pure returns(bool){
        if(_number == 0){
            return(true);
        }else{
            return(false);
        }
    }

    // for loop
    function forLoopTest() public pure returns(uint256){
        uint sum = 0;
        for(uint i = 0; i < 10; i++){
            sum += i;
        }
        return(sum);
    }

    // while
    function whileTest() public pure returns(uint256){
        uint sum = 0;
        uint i = 0;
        while(i < 10){
            sum += i;
            i++;
        }
        return(sum);
    }

    // do-while
    function doWhileTest() public pure returns(uint256){
        uint sum = 0;
        uint i = 0;
        do{
            sum += i;
            i++;
        }while(i < 10);
        return(sum);
    }

    // 三元运算符 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;
    }


    // 插入排序 错误版
    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);
    }

    // 插入排序 正确版
    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);
    }
}