使用Python实现归并排序算法并优化


归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

下面是归并算法的Python实现

# 将arr[l...mid]和arr[mid+1...r]两部分进行归并
def __merge(arr, left, mid, right):
aux = [None] * (right - left + 1)

for i in range(left, right + 1):
aux[i - left] = arr[i]

# 初始化,i指向左半部分的起始索引位置l;j指向右半部分起始索引位置mid+1
i, j = left, mid + 1
for k in range(left, right + 1):
if i > mid: # 如果左半部分元素已经全部处理完毕
arr[k] = aux[j - left]
j += 1
elif j > right: # 如果右半部分元素已经全部处理完毕
arr[k] = aux[i - left]
i += 1
elif aux[i - left] < aux[j - left]: # 左半部分所指元素<右半部分所指元素
arr[k] = aux[i - left]
i += 1
else:
arr[k] = aux[j - left] # 左半部分所指元素>=右半部分所指元素
j += 1


# 递归使用归并排序,对arr[l...r]的范围进行排序
def __merge_sort(arr, left, right):
if left >= right:
return

mid = (left + right) // 2
__merge_sort(arr, left, mid)
__merge_sort(arr, mid+1, right)
__merge(arr, left, mid, right)


def merge_sort(arr, n):
__merge_sort(arr, 0, n-1)

 

下面是对归并算法的优化

# 对arr[l...r]范围的数组进行插入排序
def insertion_sort4(arr, left, right):
for i in range(left + 1, right + 1):
element = arr[i]
j = i
while j > left and arr[j - 1] > element:
arr[j] = arr[j - 1]
j -= 1
arr[j] = element


# 将arr[l...mid]和arr[mid+1...r]两部分进行归并
def __merge(arr, left, mid, right):
aux = [None] * (right - left + 1)

for i in range(left, right + 1):
aux[i - left] = arr[i]

# 初始化,i指向左半部分的起始索引位置l;j指向右半部分起始索引位置mid+1
i, j = left, mid + 1
for k in range(left, right + 1):
if i > mid: # 如果左半部分元素已经全部处理完毕
arr[k] = aux[j - left]
j += 1
elif j > right: # 如果右半部分元素已经全部处理完毕
arr[k] = aux[i - left]
i += 1
elif aux[i - left] < aux[j - left]: # 左半部分所指元素<右半部分所指元素
arr[k] = aux[i - left]
i += 1
else:
arr[k] = aux[j - left] # 左半部分所指元素>=右半部分所指元素
j += 1


def __merge_sort2(arr, left, right):

# 对于小规模数组,使用插入排序
if (right - left) <= 15:
insertion_sort4(arr, left, right)
return

mid = (left + right) // 2
__merge_sort2(arr, left, mid)
__merge_sort2(arr, mid+1, right)

if arr[mid] > arr[mid + 1]:
__merge(arr, left, mid, right)


def merge_sort2(arr, n):
__merge_sort2(arr, 0, n-1)

采取的优化方法是在细分到一定程度时不再继续细分,直接采用插入排序完成排序

算法时间测试结果:

项目地址:https://github.com/XThundering/Algorithms


使用Python实现插入排序算法并优化


插入排序算法:通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

首先是插入排序算法的两种实现:

# 插入排序
def insertion_sort(arr, n):
for i in range(1, n):
for j in range(i, 0, -1):
if arr[j] < arr[j-1]:
arr[j], arr[j-1] = arr[j-1], arr[j]
else:
break


# 插入排序写法2
def insertion_sort2(arr, n):
for i in range(1, n):
j = i
while j > 0 and arr[j] < arr[j-1]:
arr[j], arr[j - 1] = arr[j - 1], arr[j]
j -= 1

然后是对插入排序算法对优化,通过设置变量去存储应该插入的位置来减少交换次数

# 插入排序优化
def insertion_sort3(arr, n):
for i in range(1, n):
element = arr[i]

# j存储element 应该插入的位置
j = i
while j > 0 and arr[j-1] > element:
arr[j] = arr[j-1]
j -= 1
arr[j] = element

附算法时间测试结果:

可以观察到插入排序算法的时间复杂度符合o(n^2),另外对插入排序算法的优化有明显的效果

项目地址:https://github.com/XThundering/Algorithms


使用Python实现选择排序算法并优化


首先是一个简单的选择排序算法:

# 简单的选择排序
def selection_sort(arr, n):
for i in range(n):
min_index = i
for j in range(i+1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]

随后对选择排序进行优化,虽然时间复杂度还是o(n^2),但是还是优化了一点时间

# 选择排序优化 每一轮查找可同时查找未处理元素的最大、最小值
def selection_sort2(arr, n):
left, right = 0, n-1

while left < right:
min_index, max_index = left, right

# 在每一轮查找时, 要保证arr[minIndex] <= arr[maxIndex]
if arr[min_index] > arr[max_index]:
arr[min_index], arr[max_index] = arr[max_index], arr[min_index]

for i in range(left+1, right):
if arr[i] < arr[min_index]:
min_index = i
elif arr[i] > arr[max_index]:
max_index = i

arr[left], arr[min_index] = arr[min_index], arr[left]
arr[right], arr[max_index] = arr[right], arr[max_index]

left += 1
right -= 1

附一下这两个算法的测试结果:

可以观察到n变成2倍时,时间基本上是4倍,符合时间复杂度为o(n^2)的表现

算法代码和测试代码可在我的Github项目中查看:https://github.com/XThundering/Algorithms


设计模式 - 创建型模式总结


创建型模式(Creational Pattern)对类的实例化过程进行了抽象,能够将软件模块中对象的创建和对象的使用分离。为了使软件的结构更加清晰,外界对于这些对象只需要知道它们共同的接口,而不清楚其具体的实现细节,使整个系统的设计更加符合单一职责原则。

创建型模式在创建什么(What),由谁创建(Who),何时创建(When)等方面都为软件设计者提供了尽可能大的灵活性。创建型模式隐藏了类的实例的创建细节,通过隐藏对象如何被创建和组合在一起达到使整个系统独立的目的。

  • 简单工厂模式(Simple Factory)
  • 工厂方法模式(Factory Method)
  • 抽象工厂模式(Abstract Factory)
  • 建造者模式(Builder)
  • 原型模式(Prototype)
  • 单例模式(Singleton)

 1、简单工厂模式( Simple Factory Pattern )

  • 创建型模式对类的实例化过程进行了抽象,能够将对象的创建与对象的使用过程分离。
  • 简单工厂模式又称为静态工厂方法模式,它属于类创建型模式。在简单工厂模式中,可以根据参数的不同返回不同类的实例。简单工厂模式专门定义一个类来负责创建其他类的实例,被创建的实例通常都具有共同的父类。
  • 简单工厂模式包含三个角色:工厂角色负责实现创建所有实例的内部逻辑;抽象产品角色是所创建的所有对象的父类,负责描述所有实例所共有的公共接口;具体产品角色是创建目标,所有创建的对象都充当这个角色的某个具体类的实例。
  • 简单工厂模式的要点在于:当你需要什么,只需要传入一个正确的参数,就可以获取你所需要的对象,而无须知道其创建细节。
  • 简单工厂模式最大的优点在于实现对象的创建和对象的使用分离,将对象的创建交给专门的工厂类负责,但是其最大的缺点在于工厂类不够灵活,增加新的具体产品需要修改工厂类的判断逻辑代码,而且产品较多时,工厂方法代码将会非常复杂。
  • 简单工厂模式适用情况包括:工厂类负责创建的对象比较少;客户端只知道传入工厂类的参数,对于如何创建对象不关心。

 

 2、工厂方法模式(Factory Method Pattern)

  • 工厂方法模式又称为工厂模式,它属于类创建型模式。在工厂方法模式中,工厂父类负责定义创建产品对象的公共接口,而工厂子类则负责生成具体的产品对象,这样做的目的是将产品类的实例化操作延迟到工厂子类中完成,即通过工厂子类来确定究竟应该实例化哪一个具体产品类。
  • 工厂方法模式包含四个角色:抽象产品是定义产品的接口,是工厂方法模式所创建对象的超类型,即产品对象的共同父类或接口;具体产品实现了抽象产品接口,某种类型的具体产品由专门的具体工厂创建,它们之间往往一一对应;抽象工厂中声明了工厂方法,用于返回一个产品,它是工厂方法模式的核心,任何在模式中创建对象的工厂类都必须实现该接口;具体工厂是抽象工厂类的子类,实现了抽象工厂中定义的工厂方法,并可由客户调用,返回一个具体产品类的实例。
  • 工厂方法模式是简单工厂模式的进一步抽象和推广。由于使用了面向对象的多态性,工厂方法模式保持了简单工厂模式的优点,而且克服了它的缺点。在工厂方法模式中,核心的工厂类不再负责所有产品的创建,而是将具体创建工作交给子类去做。这个核心类仅仅负责给出具体工厂必须实现的接口,而不负责产品类被实例化这种细节,这使得工厂方法模式可以允许系统在不修改工厂角色的情况下引进新产品。
  • 工厂方法模式的主要优点是增加新的产品类时无须修改现有系统,并封装了产品对象的创建细节,系统具有良好的灵活性和可扩展性;其缺点在于增加新产品的同时需要增加新的工厂,导致系统类的个数成对增加,在一定程度上增加了系统的复杂性。
  • 工厂方法模式适用情况包括:一个类不知道它所需要的对象的类;一个类通过其子类来指定创建哪个对象;将创建对象的任务委托给多个工厂子类中的某一个,客户端在使用时可以无须关心是哪一个工厂子类创建产品子类,需要时再动态指定。

 

3、抽象工厂模式(Abstract Factory)

  • 抽象工厂模式提供一个创建一系列相关或相互依赖对象的接口,而无须指定它们具体的类。抽象工厂模式又称为Kit模式,属于对象创建型模式。
  • 抽象工厂模式包含四个角色:抽象工厂用于声明生成抽象产品的方法;具体工厂实现了抽象工厂声明的生成抽象产品的方法,生成一组具体产品,这些产品构成了一个产品族,每一个产品都位于某个产品等级结构中;抽象产品为每种产品声明接口,在抽象产品中定义了产品的抽象业务方法;具体产品定义具体工厂生产的具体产品对象,实现抽象产品接口中定义的业务方法。
  • 抽象工厂模式是所有形式的工厂模式中最为抽象和最具一般性的一种形态。抽象工厂模式与工厂方法模式最大的区别在于,工厂方法模式针对的是一个产品等级结构,而抽象工厂模式则需要面对多个产品等级结构。
  • 抽象工厂模式的主要优点是隔离了具体类的生成,使得客户并不需要知道什么被创建,而且每次可以通过具体工厂类创建一个产品族中的多个对象,增加或者替换产品族比较方便,增加新的具体工厂和产品族很方便;主要缺点在于增加新的产品等级结构很复杂,需要修改抽象工厂和所有的具体工厂类,对“开闭原则”的支持呈现倾斜性。
  • 抽象工厂模式适用情况包括:一个系统不应当依赖于产品类实例如何被创建、组合和表达的细节;系统中有多于一个的产品族,而每次只使用其中某一产品族;属于同一个产品族的产品将在一起使用;系统提供一个产品类的库,所有的产品以同样的接口出现,从而使客户端不依赖于具体实现。

 

4、建造者模式

  • 建造者模式将一个复杂对象的构建与它的表示分离,使得同样的构建过程可以创建不同的表示。建造者模式是一步一步创建一个复杂的对象,它允许用户只通过指定复杂对象的类型和内容就可以构建它们,用户不需要知道内部的具体构建细节。建造者模式属于对象创建型模式。
  • 建造者模式包含如下四个角色:抽象建造者为创建一个产品对象的各个部件指定抽象接口;具体建造者实现了抽象建造者接口,实现各个部件的构造和装配方法,定义并明确它所创建的复杂对象,也可以提供一个方法返回创建好的复杂产品对象;产品角色是被构建的复杂对象,包含多个组成部件;指挥者负责安排复杂对象的建造次序,指挥者与抽象建造者之间存在关联关系,可以在其construct()建造方法中调用建造者对象的部件构造与装配方法,完成复杂对象的建造
  • 在建造者模式的结构中引入了一个指挥者类,该类的作用主要有两个:一方面它隔离了客户与生产过程;另一方面它负责控制产品的生成过程。指挥者针对抽象建造者编程,客户端只需要知道具体建造者的类型,即可通过指挥者类调用建造者的相关方法,返回一个完整的产品对象。
  • 建造者模式的主要优点在于客户端不必知道产品内部组成的细节,将产品本身与产品的创建过程解耦,使得相同的创建过程可以创建不同的产品对象,每一个具体建造者都相对独立,而与其他的具体建造者无关,因此可以很方便地替换具体建造者或增加新的具体建造者,符合“开闭原则”,还可以更加精细地控制产品的创建过程;其主要缺点在于由于建造者模式所创建的产品一般具有较多的共同点,其组成部分相似,因此其使用范围受到一定的限制,如果产品的内部变化复杂,可能会导致需要定义很多具体建造者类来实现这种变化,导致系统变得很庞大。
  • 建造者模式适用情况包括:需要生成的产品对象有复杂的内部结构,这些产品对象通常包含多个成员属性;需要生成的产品对象的属性相互依赖,需要指定其生成顺序;对象的创建过程独立于创建该对象的类;隔离复杂对象的创建和使用,并使得相同的创建过程可以创建不同类型的产品。

 

5、单例模式

  • 单例模式确保某一个类只有一个实例,而且自行实例化并向整个系统提供这个实例,这个类称为单例类,它提供全局访问的方法。单例模式的要点有三个:一是某个类只能有一个实例;二是它必须自行创建这个实例;三是它必须自行向整个系统提供这个实例。单例模式是一种对象创建型模式。
  • 单例模式只包含一个单例角色:在单例类的内部实现只生成一个实例,同时它提供一个静态的工厂方法,让客户可以使用它的唯一实例;为了防止在外部对其实例化,将其构造函数设计为私有。
  • 单例模式的目的是保证一个类仅有一个实例,并提供一个访问它的全局访问点。单例类拥有一个私有构造函数,确保用户无法通过new关键字直接实例化它。除此之外,该模式中包含一个静态私有成员变量与静态公有的工厂方法。该工厂方法负责检验实例的存在性并实例化自己,然后存储在静态成员变量中,以确保只有一个实例被创建。
  • 单例模式的主要优点在于提供了对唯一实例的受控访问并可以节约系统资源;其主要缺点在于因为缺少抽象层而难以扩展,且单例类职责过重。
  • 单例模式适用情况包括:系统只需要一个实例对象;客户调用类的单个实例只允许使用一个公共访问点。

 

内容摘自图说设计模式


简单的Python爬虫


这段时间重新回顾了Python语法,学习写了一个简单的原生Python爬虫,先放在这吧。



import re
from urllib import request


class Spider:
url = 'https://www.panda.tv/cate/lol'
root_pattern = '<div class="video-info">([\s\S]*?)</div>'
name_pattern = '</i>([\s\S]*?)</span>'
number_pattern = '<span class="video-number">([\s\S]*?)</span>'

@staticmethod
def __fetch_content():
r = request.urlopen(Spider.url)
htmls = r.read()
htmls = str(htmls, encoding='utf-8')
return htmls

@staticmethod
def __analysis(htmls):
root_html = re.findall(Spider.root_pattern, htmls)
anchors = []
for html in root_html:
name = re.findall(Spider.name_pattern, html)
number = re.findall(Spider.number_pattern, html)
anchor = {'name': name, 'number': number}
anchors.append(anchor)
return anchors

@staticmethod
def __refine(anchors):
return map(lambda anchor: {'name': anchor['name'][0].strip(), 'number': anchor['number'][0]}, anchors)

def __sort(self, anchors):
anchors = sorted(anchors, key=self.__sort_seed, reverse=True)
return anchors

@staticmethod
def __sort_seed(anchor):
r = re.findall('\d*', anchor['number'])
number = float(r[0])
if '万' in anchor['number']:
number *= 10000
return number

@staticmethod
def __show(anchors):
for rank in range(0, len(anchors)):
print('rank ' + str(rank + 1)
+ ' : ' + anchors[rank]['name']
+ ' ' + anchors[rank]['number'] + '人气')

def go(self):
htmls = self.__fetch_content()
anchors = self.__analysis(htmls)
anchors = list(self.__refine(anchors))
anchors = self.__sort(anchors)
self.__show(anchors)


spider = Spider()
spider.go()