# Solidity极简入门: 7. 控制流，用solidity实现插入排序
Use solidity to write Insertion Sort

**Published by:** [DAO4Resilience](https://paragraph.com/@dao4resilience/)
**Published on:** 2022-04-24
**URL:** https://paragraph.com/@dao4resilience/solidity-7-solidity-use-solidity-to-write-insertion-sort

## Content

这一讲，我们将介绍solidity中的控制流，然后讲如何用solidity实现插入排序（InsertionSort），一个看起来简单，但实际上很容易写出bug的程序。控制流Solidity的控制流与其他语言类似，主要包含以下几种： 1. if-else // if else function IfElseTest(uint256 _number) public returns(uint256){ if(条件){ ...; }else{ ...; } } 2 for循环 for(uint256 i = 0; i < n; i++){ ...; } 3. while循环 while(i < n){ ...; } 4. do-while循环 do{ ...; }while(i < n); 另外还有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 改写成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写的插入算法教程都是错的，比如 1. Sorting in Solidity without Comparison 2. Solidity Insertion sort for sorting less than 10 items with reference正确的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]输入[2,5,3,1] 输出[1,2,3,5]总结这一讲，我们介绍了solidity中控制流，并且用solidity写了插入排序。看起来很简单，但实际很难。这就是solidity，坑很多，每个月都有项目因为这些小bug损失几千万甚至上亿美元。掌握好基础，不断练习，才能写出更好的solidity代码。

## Publication Information

- [DAO4Resilience](https://paragraph.com/@dao4resilience/): Publication homepage
- [All Posts](https://paragraph.com/@dao4resilience/): More posts from this publication
- [RSS Feed](https://api.paragraph.com/blogs/rss/@dao4resilience): Subscribe to updates