1、冒泡排序
冒泡排序,Bubble
Sort,是一种简单的排序算法。它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢浮到数列的顶端。
2、插入排序
插入排序,Insertion
Sort,是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,在从后向前的扫描过程中,需要把已排序元素逐步向后挪位,为最新元素提供插入空间。
3、选择排序
选择排序,Selection
Sort,是一种简单直观的排序算法。它的工作原理如下:首先在未排序序列中找到最小、最大元素,存放到排序序列的起始位置,然后再从剩余未排序元素中继续寻找最小、最大元素。放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
列表的sort方法就是用来进行排序的。
主要就是两个参数,key,reverse
先说reverse,这个很简单,就是指出是否进行倒序排序:一般情况下,1排在2的前面,而倒序则相反。
key参数:一般它是一个函数,它接受列表中每一个元素,返回一个可用用于比较的值。
s=[1,2,3,4,5]
s.sort(key=lambda _: _**2%7)
print(s)
输出的是:[1, 3, 4, 2, 5]
如果看不懂lambda表达式,可以看这一段等价的写法:
def myfn(x):
....return (x * x) % 7
s=[1,2,3,4,5]
s.sort(key=myfn)
print(s)
输出的结果是一样的。
key使用的函数可以是自定义函数也可以pytho内置的函数,或者是某个类或者实例的方法,只要它能接受一个参数,返回一个可比较的值即可。比如这样:
s=[[1,2,4],[3,3,5],[1,1,1],[5,7,9]]
s.sort(key=max) # 直接使用max函数作为排序依据
print(s)
[[1, 1, 1], [1, 2, 4], [3, 3, 5], [5, 7, 9]]
很多时候,我们需要对List进行排序,Python提供了两个方法,对给定的ListL进行排序:
方法1.用List的成员函数sort进行排序
方法2.用built-in函数sorted进行排序(从2.4开始)
这两种方法使用起来差不多,以第一种为例进行讲解:
从Python2.4开始,sort方法有了三个可选的参数,Python
Library
Reference里是这样描述的
复制代码代码如下:
cmp:cmp
specifies
a
custom
comparison
function
of
two
arguments
(iterable
elements)
which
should
return
a
negative,
zero
or
positive
number
depending
on
whether
the
first
argument
is
considered
smaller
than,
equal
to,
or
larger
than
the
second
argument:
"cmp=lambda
x,y:
cmp(x.lower(),
y.lower())"
key:key
specifies
a
function
of
one
argument
that
is
used
to
extract
a
comparison
key
from
each
list
element:
"key=str.lower"
reverse:reverse
is
a
boolean
value.
If
set
to
True,
then
the
list
elements
are
sorted
as
if
each
comparison
were
reversed.In
general,
the
key
and
reverse
conversion
processes
are
much
faster
than
specifying
an
equivalent
cmp
function.
This
is
because
cmp
is
called
multiple
times
for
each
list
element
while
key
and
reverse
touch
each
element
only
once.
以下是sort的具体实例。
实例1:
复制代码代码如下:
>>>L
=
[2,3,1,4]
>>>L.sort()
>>>L
>>>[1,2,3,4]
实例2:
复制代码代码如下:
>>>L
=
[2,3,1,4]
>>>L.sort(reverse=True)
>>>L
>>>[4,3,2,1]
实例3:
复制代码代码如下:
>>>L
=
[('b',2),('a',1),('c',3),('d',4)]
>>>L.sort(cmp=lambda
x,y:cmp(x[1],y[1]))
>>>L
>>>[('a',
1),
('b',
2),
('c',
3),
('d',
4)]
实例4:
复制代码代码如下:
>>>L
=
[('b',2),('a',1),('c',3),('d',4)]
>>>L.sort(key=lambda
x:x[1])
>>>L
>>>[('a',
1),
('b',
2),
('c',
3),
('d',
4)]
实例5:
复制代码代码如下:
>>>L
=
[('b',2),('a',1),('c',3),('d',4)]
>>>import
operator
>>>L.sort(key=operator.itemgetter(1))
>>>L
>>>[('a',
1),
('b',
2),
('c',
3),
('d',
4)]
实例6:(DSU方法:Decorate-Sort-Undercorate)
复制代码代码如下:
>>>L
=
[('b',2),('a',1),('c',3),('d',4)]
>>>A
=
[(x[1],i,x)
for
i,x
in
enumerate(L)]
#i
can
confirm
the
stable
sort
>>>A.sort()
>>>L
=
[s[2]
for
s
in
A]
>>>L
>>>[('a',
1),
('b',
2),
('c',
3),
('d',
4)]
以上给出了6中对List排序的方法,其中实例3.4.5.6能起到对以List
item中的某一项
为比较关键字进行排序.
效率比较:
复制代码代码如下:
cmp
<
DSU
<
key
通过实验比较,方法3比方法6要慢,方法6比方法4要慢,方法4和方法5基本相当
多关键字比较排序:
实例7:
复制代码代码如下:
>>>L
=
[('d',2),('a',4),('b',3),('c',2)]
>>>
L.sort(key=lambda
x:x[1])
>>>
L
>>>[('d',
2),
('c',
2),
('b',
3),
('a',
4)]
我们看到,此时排序过的L是仅仅按照第二个关键字来排的,如果我们想用第二个关键字
排过序后再用第一个关键字进行排序呢?有两种方法
实例8:
复制代码代码如下:
>>>
L
=
[('d',2),('a',4),('b',3),('c',2)]
>>>
L.sort(key=lambda
x:(x[1],x[0]))
>>>
L
>>>[('c',
2),
('d',
2),
('b',
3),
('a',
4)]
实例9:
复制代码代码如下:
>>>
L
=
[('d',2),('a',4),('b',3),('c',2)]
>>>
L.sort(key=operator.itemgetter(1,0))
>>>
L
>>>[('c',
2),
('d',
2),
('b',
3),
('a',
4)]
为什么实例8能够工作呢?原因在于tuple是的比较从左到右之一比较的,比较完第一个,如果
相等,比较第二个