Python全栈之路5--常见的排序的算法

  • Z时代
  • 2024-01-10
  • 分类：综合

python

一、上节内容补充回顾 
 1、lambda
  func = lambda x,y: 9+x 
  参数：  x,y 
  函数体：9+x  ==》 return 9+x 
  func: 函数名 
  def func(x,y): 
   return x + 9
  def func(x,y): 
   return x + 9
  func = lambda x,y: 9+x 
  扩展：函数名可以当做参数传递 
    函数名() ==》 执行函数 
    函数名 ==》 代指函数 
 2、内置 
  xxx 
 3、open文件操作 
  open() 
  1、文件路径 
  2、模式 
   基本操作： 
    r，只读 
    w，只写（先清空） 
    x，不存在，创建，存在，报错： 只写 
    a，追加，只写 
   二进制 
    rb 
    wb 
    xb 
    ab 
   +
    r+，读写： 
      读，0开始读取 
      写， 
       先读，最后追加 
       主动seek，写从当前指针向后写 
        ==》 
    w+，读写 
    x+，读写 
    a+，读写 
      读，最后位置读取 
      写， 
       最后追加 
       主动seek，最后追加 
   r+ 最常用 
  3、文件操作 
   trancate，截取前面 
   read 
    read(1) :无b，字符 
    read(1) :有b，字节 
   write 
    str     ：无，字符串 
    bytes   ：有，字节 
   readline 
    只读取一行 
   readlines: 
    [“第一行”, "第二行"] 
   xrealines:  2.7
    for line in f.xrealines(): 
     line 
   f = open() 
   for i in f: 
    print(i) 
   flush 
    强行刷入硬盘 
   close 
   tell()  获取指针位置 
   seek()  跳转到某个位置 
  4、 whth open(xx) as f: 
    print
  5、with open(xx) as f1 ,open(xx) as f2:

上节重点

二、函数作为参数传入另一个函数

python;gutter:true;"># 2 函数参数 
def f1(): 
    return "F1"
def f2(arg): 
    arg() 
    return 'F2'
# 变量 x =123 
# 函数名 f1 = 对应def f1 内存地址 
# 函数名 f2 = 对应def f2 内存地址 
# print(f1) 
# 执行f2函数，f1当传参 
f2(f1)

filter方法的实现：

#filter 实现
def myfilter(fuc,seq):
    new_li = []
    for i in seq:
        #print(i)
        ret = fuc(i)
        if ret:
            new_li.append(i)
    return new_li
def f1(x):
    if x > 22:
        return True
    else:
        return False
li = [11,22,33,44]
new=myfilter(f1,li)
print(new)

map的实现方法

# map 实现
def mymap(fuc,seq):
    n_li = []
    for i in seq:
        n_i=fuc(i)
        n_li.append(n_i)
    # print(n_li)
    return n_li
def f2(x):
    return x+10
li = [11,22,33,44]
ret = mymap(f2,li)
print(ret)

三、基本的排序算法

3.1、冒泡排序：

利用第三个元素进行排序：

li = [33,2,10,1,11,99,88]  
 #让 第一个元素跟第二个元素替换 需要一个中间值存储 
 tmp = li[0] 
 li[0] = li[1] 
 li[1] = tmp 
 for j in range(1,len(li)): 
     for i in range(len(li)-j): 
         if li[i]>li[i+1]: 
            tmp = li[i] 
             li[i] = li[i+1] 
            li[i+1] = tmp

冒泡排序（不借助第三个变量）的基本步骤：

  • 比较相邻的元素，如果第一个比第二个大，就交换他们两个。

  • 循环一遍后，最大的数就“浮”到了列表最后的位置。

  • 将剩下的数再次循环，直道所有的排序完成

需求：请按照从小到大对列表 [13, 22, 6, 99, 11] 进行排序

思路：相邻两个值进行比较，将较大的值放在右侧，依次比较

大佐：

li = [13, 22, 6, 99, 11]
for m in range(4):     # 等价于 #for m in range(len(li)-1):
    if li[m]> li[m+1]:
        temp = li[m+1]
        li[m+1] = li[m]
        li[m] = temp

第一步

li = [13, 22, 6, 99, 11]
for m in range(4):     # 等价于 #for m in range(len(li)-1):
    if li[m]> li[m+1]:
        temp = li[m+1]
        li[m+1] = li[m]
        li[m] = temp
for m in range(3):     # 等价于 #for m in range(len(li)-2):
    if li[m]> li[m+1]:
        temp = li[m+1]
        li[m+1] = li[m]
        li[m] = temp
for m in range(2):     # 等价于 #for m in range(len(li)-3):
    if li[m]> li[m+1]:
        temp = li[m+1]
        li[m+1] = li[m]
        li[m] = temp
for m in range(1):     # 等价于 #for m in range(len(li)-4):
    if li[m]> li[m+1]:
        temp = li[m+1]
        li[m+1] = li[m]
        li[m] = temp
print li

第二步

li = [13, 22, 6, 99, 11]
for i in range(1,5):
    for m in range(len(li)-i): 
        if li[m] > li[m+1]:
            temp = li[m+1]
            li[m+1] = li[m]
            li[m] = temp

第三步

小东：

def swap(a,b):          　 #一种巧妙交换两个数的位置而不用第三个变量的方法 
    a=b-a 
    b=b-a                　# b=b-(b-a) = a 
    a=b+a                　# a=a+(b-a) = b 
    return a,b 
def BubbleSort(l):　　　　　　　　　　　　　　　　　　    # 冒泡排序 
    for i in range(1,len(l)): 
        for j in range(0,len(l)-i):　　　　　　　　　　 # 每次循环减i是因为最后面的数已经排好序 
            if l[j]>l[j+1]: 
                l[j],l[j+1]=l[j+1],l[j]　　　　　　　　# 交换两个数，这里用的交换是python里面特有的交换方式 
    return l 
print(BubbleSort([555,2,3,2,3,1,19,3.5,27,24]))　　　 # [1, 2, 2, 3, 3, 3.5, 19, 24, 27, 555]

3.2、选择排序

步骤：

  • 从第一个元素开始可以认为已经被排序，取出下一个元素，在已经排序的元素序列中从后向前扫描

  • 如果该元素（已排序）大于新元素，将该元素移到下一位置，直到找到已排序的元素小于或者等于新元素的位置

  • 将新元素插入到该位置后，如此反复循环，直道所有的排好序

def SelectionSort(l): 
    for i in range(len(l)): 
        min = i                                 　　　 #存放最小元素的下标 
        for j in range(i+1,len(l)): 
            if l[j]<l[min]: 
                min=j                          　　　　#记下最小元素的下标 
        l[i],l[min] = l[min],l[i]              　　　　#将最小元素放到列表起始位置 
    return l 
print(SelectionSort([555,2,3,2,3,1,19,3.5,27,24])) 　　#[1, 2, 2, 3, 3, 3.5, 19, 24, 27, 555]

3.3、插入排序

步骤：

  • 从第一个元素开始可以认为已经被排序，取出下一个元素，在已经排序的元素序列中从后向前扫描

  • 如果该元素（已排序）大于新元素，将该元素移到下一位置，直到找到已排序的元素小于或者等于新元素的位置

  • 将新元素插入到该位置后，如此反复循环，直道所有的排好序

def InsertionSort(l): 
    for i in range(1,len(l)): 
        if l[i]<l[i-1]: 
            temp=l[i]                               # 应该插入的数赋值给变量temp 
            for j in range(i-1,-1,-1):              # 从已排好的序列往前循环 
                if l[j]>temp: 
                    l[j+1] = l[j] 
                    index=j                         # 记下应该插入的位置 
                else: 
                    break
            l[index]=temp 
    return l 
print(InsertionSort([555,2,3,2,3,1,19,3.5,27,24]))   # [1, 2, 2, 3, 3, 3.5, 19, 24, 27, 555]

3.4、快速排序

步骤：

  • 从数列中挑出一个元素作为基准数(这里我选择的是第一个数)

  • 将比基准数大的放到左边，小于或等于它的数都放到右边

  • 再对左右区间递归执行上一步，直至各区间只有一个数

#这里我用了递归和列表推到式(不明白列表推到式的可暂时跳过，后面讲到) 
def QuickSort(l): 
    if len(l)<=1: 
        return l 
    return QuickSort([lt for lt in l[1:] if lt<l[0]]) + l[0:1] + QuickSort([ge for ge in l[1:] if ge>=l[0]]) 
print(QuickSort([555,2,3,2,3,1,19,3.5,27,24]))   # [1, 2, 2, 3, 3, 3.5, 19, 24, 27, 555]

四、猛料来了   递归 is comming

利用函数编写如下数列：

斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368

def func(arg1,arg2):
    if arg1 == 0:
        print arg1, arg2
    arg3 = arg1 + arg2
    print arg3
    func(arg2, arg3)
func(0,1)

递归中的return返回值

函数是一个功能块，该功能到底执行成功与否，需要通过返回值来告知调用者。

以上要点中，比较重要有参数和返回值：

如下  n5 返回值 返回给其调用者  再返回给上一层调用者。  如果 n4 n3 n2 n1 其中一个不加return 则返回none
def n5():
    return 5
def n4():
    return n5()
def n3():
    return n4()
def n2():
    return n3()
def n1():
    return  n2()
ret1 = n1()
print(ret1)

总结： return 函数()  

　　先调用函数，然后在return将获取的返回这返回给调用这个函数的变量

函数返回值

递归返回值图理解、

同上图类似，只不过函数名为同一个了

 练习  利用递归 打印 斐波那契数列第10个数

#!/usr/bin/env python
# _*_ coding:utf-8 _*_
def f(depth,arg1,arg2):
    if depth == 10:
        return arg1
    arg3 =arg1+arg2
    #print(arg1)
    return f(depth+1,arg2,arg3)
#
# ret = f(1,0,1)
# print(ret)
def new(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return  new(n-1)+new(n-2)
a=new(10)
print(a)

以上是 Python全栈之路5--常见的排序的算法 的全部内容， 来源链接： utcz.com/z/388821.html

回到顶部