Golang中的goroutine泄漏问题

goroutine作为Go中开发语言中的一大利器,在高并发中发挥着无法忽略的作用。但东西虽好,真正做到用好还是有一些要注意的地方,特别是对于刚刚接触这门开发语言的新手来说。

出现的问题

先看一段代码:

package main

import (  
    "fmt"  
    "math/rand"  
    "runtime"  
    "time"  
)

func query() int {  
    n := rand.Intn(100)  
    time.Sleep(time.Duration(n) * time.Millisecond)  
    return n  
}

func queryAll() int {  
    ch := make(chan int)  
    go func() { ch <- query() }()  
    go func() { ch <- query() }()  
    go func() { ch <- query() }()  
	// <-ch
	// <-ch
    return <-ch  
}

func main() {  
    for i := 0; i < 4; i++ {  
        queryAll()  
        fmt.Printf("#goroutines: %d\n", runtime.NumGoroutine())  
    }  
}

运行结果

#goroutines: 3
#goroutines: 5
#goroutines: 7
#goroutines: 9

这里发现goroutine的数量一直在增涨,按理说这里的值应该一直是 1 才对的呀(只有一个Main 函数的主goroutine)。其实这里发生了goroutine泄漏的问题。

主要问题发生在 queryAll() 函数里,这个函数在goroutine里往ch里连续三次写入了值,由于这里是无缓冲的ch,所以在写入值的时候,要有在ch有接收者时才可以写入成功,也就是说在从接收者从ch中获取值之前, 前面三个ch<-query() 一直处于阻塞的状态。当执行到queryAll()函数的 return语句 时,ch接收者获取一个值(意思是说三个ch<-query() 中执行最快的那个goroutine写值到ch成功了,还剩下两个执行慢的 ch<-query() 处于阻塞)并返回给调用主函数时,仍有两个ch处于浪费的状态。

在Main函数中对于for循环
第一次:goroutine的总数量为 1个主goroutine + 2个浪费的goroutine = 3
第二次:3 + 再个浪费的2个goroutine = 5
第三次:5 + 再个浪费的2个goroutine = 7
第三次:7 + 再个浪费的2个goroutine = 9

正好是程序的输出结果。

好了,问题我们知道怎么回事了,剩下的就是怎么解决了

解决方案:

可以看到,主要是ch写入值次数与读取的值的次数不一致导致的有ch一直处于阻塞浪费的状态,我们所以我们只要保存写与读的次数完全一样就可以了。

这里我们把上面queryAll() 函数代码注释掉的 <-ch 两行取消掉,再执行就正常了,输出内容如下:

#goroutines: 1
#goroutines: 1
#goroutines: 1
#goroutines: 1

对于goroutine的数量只有一个,也必须有一个,因为Main()函数也是一个goroutine。(http://docs.studygolang.com/src/runtime/proc.go?s=102731:102737#L3607 https://www.kancloud.cn/mutouzhang/go/596824

当然对于解决goroutine的方法不是仅仅这一种,也可以利用context来解决,参考:https://www.cnblogs.com/chenqionghe/p/9769351.html

提醒:

垃圾收集器不会收集以下形式的goroutines:

go func() {
// <操作会在这里永久阻塞>
}()
// Do work

这个goroutine将一直存在,直到整个程序退出。

其它:

1.如何定义Golang中的goroutine中的泄漏概念? 有没有相应的泄漏检测工具?https://blog.51cto.com/13778063/2152654

参考:

https://studygolang.com/articles/12495

https://blog.csdn.net/qq_16205285/article/details/90113419

https://segmentfault.com/q/1010000007735676

https://www.cnblogs.com/chenqionghe/p/9769351.html

https://www.kancloud.cn/mutouzhang/go/596824

一列说明数组与Hash效率的区别到底多大

在数组中添加 10000 个元素,然后分别对这 10000 个元素进行检索,最后统计检索的时间。

数组Array

import time
# 插入数据,数组
result = []
for i in range(10000):
       result.append(i)
# 检索数据
time_start=time.time()
for i in range(10000):
       temp = result.index(i)
time_end=time.time()
print('检索时间', time_end-time_start)

运行结果:

检索时间为 1.2436728477478027 秒。

Hash哈希

import time
# 插入数据
result = {}
for i in range(1000000):
       result[i] = i
# 检索数据
time_start=time.time()
for i in range(10000):
       temp = result[i]
time_end=time.time()
print('检索时间:',time_end-time_start)

运行结果:

检索时间为 0.0019941329956054688 秒。

你能看到 Hash 方式检索差不多用了 2 毫秒的时间,检索效率提升得非常明显。这是因为 Hash 只需要一步就可以找到对应的取值,算法复杂度为 O(1),而数组检索数据的算法复杂度为 O(n)。

看来两者的运行效率差别还是挺大的,所以在开发中我们一定要根据不同的场景选择使用不同的算法为好。

golang中的内存对齐(进阶必看)

先看一个结构体

// 写法一
type T1 struct {
	a int8
	b int64
	c int16
}

// 写法二
type T2 struct {
	a int8
	c int16
	b int64
}

对于这两个结构体,都有a、b、c三个定义完全一样的字段,只是在定义结构体的时候字段顺序不一样而已,那么两种写法有什么影响吗?

对于新手来说,感觉着没有什么区别的,只是一个书写顺序不同而已,但对于go编译器来说,则有着很大的区别,特别是在不同架构上(32位/64位)的编译器,在一定程度上对内存的使用大小和执行效率有着一定的不同。这里的主要知识点就是golang语言中的内存对齐概念(alignment guarantee),https://gfw.go101.org/article/memory-layout.html

类型的尺寸和结构体字节填充(structure padding)

Go白皮书只对以下种类的类型的尺寸进行了明确规定

类型种类                  尺寸(字节数)
------                   ------
byte, uint8, int8        1
uint16, int16            2
uint32, int32, float32   4
uint64, int64            8
float64, complex64       8
complex128               16
uint, int                取决于编译器实现。通常在
                         32位架构上为4,在64位
                         架构上为8。
uintptr                  取决于编译器实现。但必须
                         能够存下任一个内存地址。

Go白皮书没有对其它种类的类型的尺寸最初明确规定。 请阅读值复制成本一文来获取标准编译器使用的各种其它类型的尺寸。

标准编译器(和gccgo编译器)将确保一个类型的尺寸为此类型的对齐保证的倍数。

为了满足上一节中规定的地址对齐保证要求,Go编译器可能会在结构体的相邻字段之间填充一些字节。 这使得一个结构体类型的尺寸并非等于它的各个字段类型尺寸的简单相加之和。

下面是一个展示了一些字节是如何填充到一个结构体中的例子。 首先,从上面的描述中,我们已得知(对于标准编译器来说):

  • 内置类型int8的对齐保证和尺寸均为1个字节; 内置类型int16的对齐保证和尺寸均为2个字节; 内置类型int64的尺寸为8个字节,但它的对齐保证在32位架构上为4个字节,在64位架构上为8个字节。
  • 下例中的类型T1T2的对齐保证均为它们的各个字段的最大对齐保证。 所以它们的对齐保证和内置类型int64相同,即在32位架构上为4个字节,在64位架构上为8个字节。
  • 类型T1T2尺寸需为它们的对齐保证的倍数,即在32位架构上为4n个字节,在64位架构上为8n个字节。
type T1 struct {
	a int8

	// 在64位架构上,为了让下一个字段b的地址为8字节对齐,
	// 需在在字段a这里填充7个字节。在32位架构上,为了让
	// 字段b的地址为4字节对齐,需在这里填充3个字节。

	b int64
	c int16

	// 为了让类型T1的尺寸为T1的对齐保证的倍数,
	// 在64位架构上需在这里填充6个字节,在32架构
	// 上需在这里填充2个字节。
}
// 类型T1的尺寸在64位架构上位24个字节(1+7+8+2+6),
// 在32位架构上为16个字节(1+3+8+2+2)。
// 以保存每个字段都是8(64位架构)或者4(32位架构)的的整数倍

type T2 struct {
	a int8

	// 为了让下一个字段c的地址为2字节对齐,
	// 需在字段a这里填充1个字节。

	c int16

	// 在64位架构上,为了让下一个字段b的地址为8字节对齐,
	// 需在字段c这里填充4个字节。在32位架构上,不需填充
	// 字节即可保证字段b的地址为4字节对齐的。

	b int64
}
// 类型T2的尺寸在64位架构上位16个字节(1+1+2+4+8),
// 在32位架构上为12个字节(1+1+2+8)。

从这个例子可以看出,尽管类型T1T2拥有相同的字段集,但是它们的尺寸并不相等。每个字段的大小都要受下一个字段大小的影响,以方便下个字段对齐。所以建议在开发中,字段占用空间小的放在前面。

T1的内存对齐
T2的内存对齐

一个有趣的事实是有时候一个结构体类型中零尺寸类型的字段可能会影响到此结构体类型的尺寸。 请阅读此问答获取详情。

这里推荐一个网站:http://golang-sizeof.tips/,可以用来查看结构的内存布局,Type size的值越小越好,这样就可以对结构体进行一些内存大小优化了。

如果还有些模糊的话可以看一下这篇文章:https://blog.csdn.net/Lazyboy_/article/details/88579966

goroutine和线程区别

从调度上看,goroutine的调度开销远远小于线程调度开销。

OS的线程由OS内核调度,每隔几毫秒,一个硬件时钟中断发到CPU,CPU调用一个调度器内核函数。这个函数暂停当前正在运行的线程,把他的寄存器信息保存到内存中(暂时保存线程状态),查看线程列表并决定接下来运行哪一个线程,再从内存中恢复线程的注册表信息,最后继续执行选中的线程。这种线程切换需要一个完整的上下文切换:即保存一个线程的状态到内存,再恢复另外一个线程的状态,最后更新调度器的数据结构。某种意义上,这种操作还是很慢的。

OS 线程调度器

Go运行的时候包涵一个自己的调度器,这个调度器使用一个称为一个M:N调度技术,m个goroutine到n个os线程(可以用GOMAXPROCS来控制n的数量),Go的调度器不是由硬件时钟来定期触发的,而是由特定的go语言结构来触发的,他不需要切换到内核语境,所以调度一个goroutine比调度一个线程的成本低很多。

从栈空间上,goroutine的栈空间更加动态灵活。

每个OS的线程都有一个固定大小的栈内存,通常是2MB,栈内存用于保存在其他函数调用期间哪些正在执行或者临时暂停的函数的局部变量。这个固定的栈大小,如果对于goroutine来说,可能是一种巨大的浪费。作为对比,goroutine在生命周期开始只有一个很小的栈,典型情况是2KB, 在go程序中,一次创建十万左右的goroutine也不罕见(2KB*100,000=200MB)。而且goroutine的栈不是固定大小,它可以按需增大和缩小,最大限制可以到1GB。

参考:https://time.geekbang.org/course/detail/160-86799

goroutine没有一个特定的标识。

在大部分支持多线程的操作系统和编程语言中,线程有一个独特的标识,通常是一个整数或者指针,这个特性可以让我们构建一个线程的局部存储,本质是一个全局的map,以线程的标识作为键,这样每个线程可以独立使用这个map存储和获取值,不受其他线程干扰。

goroutine中没有可供程序员访问的标识,原因是一种纯函数的理念,不希望滥用线程局部存储导致一个不健康的超距作用,即函数的行为不仅取决于它的参数,还取决于运行它的线程标识。

reference: 《Go程序设计语言》E-mail: huahuiyang@gmail.com https://www.linkedin.com/in/huahuiyang/

转自:https://www.cnblogs.com/yanghuahui/p/9043631.html

python中的@staticmethod和@classmethod区别(整理)

问题:Python中 @staticmethod@classmethod 两种装饰器装饰的函数有什么不同?
原地址http://stackoverflow.com/questions/136097/what-is-the-difference-between-staticmethod-and-classmethod-in-python


Python其实有3类方法:

  • 静态方法(staticmethod)
  • 类方法(classmethod)
  • 实例方法(instance method)

看一下下面的示例代码:

def foo(x):
    print "executing foo(%s)" %(x)

class A(object):
    def foo(self,x):
        print "executing foo(%s,%s)" %(self,x)

    @classmethod
    def class_foo(cls,x):
        print "executing class_foo(%s,%s)" %(cls,x)

    @staticmethod
    def static_foo(x):
        print "executing static_foo(%s)" %x

a = A()

在示例代码中,先理解下函数里面的 self 和 cls。这个 self 和 cls 是对类或者实例的绑定,对于一般的函数来说我们可以这么调用foo(x),这个函数就是最常用的,它的工作和任何东西(类、实例)无关。对于实例方法,我们知道在类里每次定义方法的时候都需要绑定这个实例,就是foo(self,x),为什么要这么做呢?因为实例方法的调用离不开实例,我们需要把实例自己传给函数,调用的时候是这样的a.foo(x)(其实是foo(a,x))。类方法一样,只不过它传递的是类而不是实例, 如A.class_foo(x)。注意这里的 self 和 cls 可以替换别的参数,但是python的约定是这两个,尽量不要更改。

对于静态方法其实和普通的方法一样,不需要对谁进行绑定,唯一的区别是调用时候需要使用a.static_foo(x)A.static_foo()来调用。

\实例方法类方法静态方法
a = A()a.foo(x)a.class_foo(x)a.static_foo(x)
A不可用A.class_foo(x)A.static_foo(x)

那么对于类方法和静态方法都可以不实例对象来调用,那两者的区别又有哪些呢?

从它们的使用上来看

  • @staticmethod 不需要表示自身对象的self和自身类的cls参数,就跟使用函数一样。
  • @classmethod 也不需要self参数,但第一个参数需要是表示自身类的cls参数。

如果在@staticmethod中要调用到这个类的一些属性方法,只能直接 类名.属性名类名.方法名

而@classmethod因为持有 cls 参数,可以来调用类的属性,类的方法,实例化对象等,避免硬编码。

代码:

class A(object):
    bar = 1
    def foo(self):
        print 'foo'
 
    @staticmethod
    def static_foo():
        print 'static_foo'
        print A.bar
 
    @classmethod
    def class_foo(cls):
        print 'class_foo'
        print cls.bar
        cls().foo()
 
A.static_foo()
A.class_foo()
输出
static_foo
1

class_foo
1
foo

摘自:
https://www.cnblogs.com/taceywong/p/5813166.html
https://blog.csdn.net/handsomekang/article/details/9615239

mac下安装python web框架django

前提

由于mac自带的python2.7(路径 /usr/bin/python)
后来手动又安装了python3.7(/usr/local/bin/python3)

两个版本共存。为了方便,直接在.zshrc文件里做了别名映射

alias python="/usr/local/bin/python3.7"

所以直接使用命令python实际上用的是3.7版本。

按照官方教程 https://docs.djangoproject.com/zh-hans/2.1/intro/install/ 安装django。发现在使用命令 pip install django 安装后发现检测不到django,很奇怪,后来发现了问题所在。

➜  ~ python
Python 3.7.1 (default, Nov  6 2018, 18:46:03)
[Clang 10.0.0 (clang-1000.11.45.5)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import django
Traceback (most recent call last):
  File "", line 1, in 
ModuleNotFoundError: No module named 'django'

原来python2对应一个是包安装命令是 pip,而python3对应的是一个叫做pip3的命令。所以使用新的命令

pip3 install django

安装成功。

➜  ~ python
Python 3.7.1 (default, Nov  6 2018, 18:46:03)
[Clang 10.0.0 (clang-1000.11.45.5)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import django
>>> print(django.get_version())
2.1.3

Golang中strcut结构体的的值方法和指针方法

平时我们在写struct的时候,经常会用到一些方法,有些方法是我们熟悉的普通方法,在golang中我们称之为值方法,而另一种则是指针方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
type Person struct {
    Firstname string
    Lastname string
    Age uint8
}
// 值方法
func (p Person) show() {
    fmt.Println(p.Firstname)
}
// 指针方法
func (p *Person) show2() {
    fmt.Println(p.Firstname)
}

可以看到所谓的值方法与指针方法在编写的时候,只是有无*号的区别,这个*就是指针的意思。

那么用法又有何不同呢?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 值方法
func (p Person) setFirstName(name string) {
    p.Firstname = name
}
// 指针方法
func (p *Person) setFirstName2(name string) {
    p.Firstname = name
}
func main() {
    p := Person{"sun", "xingfang", 30}
    //不一致的情况
    p.show() // sun 修改前
    p.setFirstName("tom")   // 值方法
    p.show() // sun, 未变化
    p.show() // sun 修改前
    p.setFirstName2("tom"// 指针方法
    p.show() // tom 修改后的tom
}

通过上面的输出我们可以看到,当调用值方法setFirstName后,输出的还是原来的值sun,而调用指针方法 setFirstNam2后,则输出的是新值。主要原因就是值方法func (p Person)在传递总结体的时候,用的只是原来结构体的一个副本,做的任何修改也只是对副本的修改,而打印的还是原来的结构体,两者互不影响。而指针方法,传递的则是指向结构体指针的值副本,指针值一样(X012242R424),指定的都是底层的数据结构,所以才会出现这种情况。

总结:

  1. 值方法的接收者是该方法所属的那个类型值的一个副本。我们在该方法内对该副本的修1改一般都不会体现在原值上,除非这个类型本身是某个引用类型(比如切片或字典)的别名类型。 而指针方法的接收者,是该方法所属的那个基本类型值的指针值的一个副本。我们在这样的方法内对该副本指向的值进行修改,却一定会体现在原值上。
  2. 一个自定义数据类型的方法集合中仅会包含它的所有值方法,而该类型的指针类型的方法集合却囊括了前者的所有方法,包括所有值方法所有指针方法
    严格来讲,我们在这样的基本类型的值上只能调用到它的值方法
    但是,Go 语言会适时地为我们进行自动地转译,使得我们在这样的值上也能调用到它的指针方法。本示例中的 p.show() 在调用的时候会自动转换成 show2() 这种指针方式,可以试着将例子中的 show() 改成 show2() 输出结果是一样的)比如,在Cat类型的变量cat之上,之所以我们可以通过cat.SetName(“monster”)修改猫的名字,是因为 Go 语言把它自动转译为了(&cat).SetName(“monster”),即:先取cat的指针值,然后在该指针值上调用SetName方法。以上是由“郝林”老师在“Go语言核心36讲”专栏中总结。
  3. 两种写法在使用接口的时候也会有所不同。

Golang中的unsafe.Sizeof()简述

测试环境:
系统 win7 64位
go version: go1.10 windows/amd64

我们先看一下代码的输出

package main

import "unsafe"

func main() {
	// string
	str1 := "abc"
	println("string1:", unsafe.Sizeof(str1)) // 16
	str2 := "abcdef"
	println("string2:", unsafe.Sizeof(str2)) // 16
	
	// 数组
	arr1 := [...]int{1, 2, 3, 4}
	println("array1:", unsafe.Sizeof(arr1)) // 32 = 8 * 4

	arr2 := [...]int{1, 2, 3, 4, 5}
	println("array2:", unsafe.Sizeof(arr2)) // 40 = 8 * 5

	// slice 好多人分不清切片和数组的写法区别,其实只要记住[]中间是空的就是切片,反之则是数组即可
	slice1 := []int{1, 2, 3, 4}
	println("slice1:", unsafe.Sizeof(slice1)) // 24

	slice2 := []int{1, 2, 3, 4, 5}
	println("slice2:", unsafe.Sizeof(slice2)) // 24

	slice3 := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
	println("slice3:", unsafe.Sizeof(slice3)) // 24
}
1、字符串类型
为什么字符串类型的 unsafe.Sizeof() 一直是16呢?
实际上字符串类型对应一个结构体,该结构体有两个域,第一个域是指向该字符串的指针,第二个域是字符串的长度,每个域占8个字节,但是并不包含指针指向的字符串的内容,这也就是为什么sizeof始终返回的是16。
组成可以理解成此结构体
typedef struct {
    char* buffer;
    size_tlen;
} string;
2、数组类型
编译的时候系统自动分配内存,int的长度是由系统平台来决定的,我用的是64位的系统,所以一个int 代表的就是 int64 数据类型,每个数字占用8个字节,成员数组元素个数正好等于输出的值。byte(1字节),uint8(1字节),uint16(2字节),uint32(4字节),uint64(占用8字节), byte是uint8的别名,这些全是无符号型的,对应的还有有符号型的,区别也就是一个值范围不同而已。

不同数据类型占用字节大小如下:

func main() {
	var a uint8
	a = 2
	fmt.Println("uint8 type size:", unsafe.Sizeof(a))

	var b uint16
	b = 2
	fmt.Println("uint16 type size:", unsafe.Sizeof(b))

	
	var c uint32
	c = 2
	fmt.Println("uint32 type size:", unsafe.Sizeof(c))
	
	var d uint64
	d = 2
	fmt.Println("uint64 type size:", unsafe.Sizeof(d))
}

数据类型

具体类型 取值范围
int8 -128到127
uint8 0到255
int16 -32768到32767
uint16 0到65535
int32 -2147483648到2147483647
uint32 0到4294967295
int64 -9223372036854775808到9223372036854775807
uint64 0到18446744073709551615
3、切片类型
可以看到切片和数组还是有些不一样的,我们看一下官方包的解释 /src/unsafe/unsafe.go
// Sizeof takes an expression x of any type and returns the size in bytes
// of a hypothetical variable v as if v was declared via var v = x.
// The size does not include any memory possibly referenced by x.
// For instance, if x is a slice, Sizeof returns the size of the slice
// descriptor, not the size of the memory referenced by the slice.
意思是说如果是slice的话,则返回的是slice描述符的长度,而不是slice的内存长度。

数据结构与算法

平时开发中,一般很少用到手动来写算法的情况,但实际上我们一直在接触一些数据结构与算法,如JAVA中的ArrayList 就用到了数据结构与算法,从名字可以看到了用到了Array这种数组结构和链表结构。下面根据目前学习的情况做一个总结。

数据结构

我们常见的数组结构一般有:

  • Array数组、
  • Stack栈、
  • Heap堆、
  • Queue队列
  • Hash 哈希类型
  • LinkedList 链表,其中又分为单向链表、双向链表、还有最少用的环形链表
  • Tree 这个Tree分的太多了,如B-Tree、 B+Tree(mysql使用)、Binary Search Tree二叉搜索树 、AVL高度平衡树、Red Black Tree红黑树 等

数据结构

http://www.bigocheatsheet.com/

 

算法

一般开发中用到的基本上排序算法居多,而算法大体上又分为比较排序和非比较排序。我们常用的比较排序算法有(参考:http://www.cnblogs.com/eniac12/p/5329396.html):

  • 快速排序 (Quick Sort)
  • 冒泡排序 (Bubble Sort)
  • 插入排序 (Insertion Sort)
  • 堆排序 (Heap Sort)
  • 归并排序 (Merge Sort)

而非比较排序算法有(由于排序算法时间复杂度是线性的,有时候我们也称此算法线性排序,参考http://www.cnblogs.com/eniac12/p/5332117.html):

  • 计数排序(Counting sort)
  • 基数排序 (Radix Sort)
  • 桶排序 (Bucket Sort)

http://www.bigocheatsheet.com/

 

Bucket sort 排序

Bucket sort 排序 (图出自:极客时间)

计数排序 Counting sort

计数排序 Counting sort (图出自:极客时间)

注意:
有些算法是属于稳定算法,也有些属于非稳定算法。所谓的稳定是指相同的排序值原来的顺序经过排序后,前后顺序并不改变。就像我们平时数据库中根据两个字段进行排序的时候一样。

算法时间复杂度和空间复杂度
时间复杂度:https://baike.baidu.com/item/时间复杂度/1894057
空间复杂度:https://baike.baidu.com/item/空间复杂度

复杂度大致可分为:

  • O(1) 最好
  • O(log n)
  • O(n)
  • O(n log n)
  • O(n^2)
  • O(2^n)
  • O(n!) 最差

O(log n):当数据增大n倍时,耗时增大log n倍(这里的log是以2为底的,比如,当数据增大256倍时,耗时只增大8倍,是比线性还要低的时间复杂度)。二分查找就是O(logn)的算法,每找一次排除一半的可能,256个数据中查找只要找8次就可以找到目标。

O(n log n):同理,就是n乘以logn,当数据增大256倍时,耗时增大256*8=2048倍。这个复杂度高于线性低于平方。归并排序就是O(nlogn)的时间复杂度。

O(n^2),就代表数据量增大n倍时,耗时增大n的平方倍,这是比线性更高的时间复杂度。比如冒泡排序、插入排序、选择排序,就是典型的O(n^2)的算法,对n个数排序,需要扫描n x n次。