常见算法的python实现

2019-05-08 07:29:30来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

  提到排序算法,常见的有如下几种:冒泡排序、选择排序、插入排序、快速排序、堆排序、归并排序、希尔排序;查找算法最常见二分查找。这些算法的时间复杂度如下:

算法名称 时间复杂度(一般情况)

冒泡排序

O(n2)

选择排序

O(n2)

插入排序

O(n2)

快速排序

O(nlog2n)

堆排序

O(nlog2n)

归并排序

O(nlog2n)

希尔排序

O(1.3n)

二分查找

O(log2n)

  二分查找前提要求序列必须是有序的,所以下面我先介绍各排序算法的实现。注:默认按照升序排列


1、冒泡排序

  冒泡排序的原理是从序列的第一个元素开始,与相邻的元素比较大小,如果左边的元素比右边的大,则交换两个元素的位置,依次类推,则一个循环完成后,序列中最大的元素就会到达序列的最右侧,通过多次同样的循环操作将序列从小到大排列。代码实现较简单:

1 def bubble(array):
2     for i in range(len(array)-1):  # 仅需循环序列长度-1次即可完成排序
3         for j in range(len(array)-i-1):  # 每次循环,右侧排好的元素不在进行比较
4             if array[j] > array[j+1]:
5                 array[j], array[j+1] = array[j+1], array[j]
6     return array

   除此之外,冒泡排序算法还有一个优化的写法。假设一个很大的序列,应用冒泡排序完成几次循环后,进行下一次循环发现并没有任何两个元素交换了位置,那说明什么呢?说明该序列已经变成了有序的序列,所以我们不需要在继续比较下去了,此时结束循环以便节省时间,变成代码实现如下:

 1 def bubble_better(array):
 2     for i in range(len(array)-1):
 3         exchange = False  # 每次大循环开始,将此标志设置为False
 4         for j in range(len(array)-i-1):
 5             if array[j] > array[j+1]:
 6                 array[j], array[j+1] = array[j+1], array[j]
 7                 exchange = True
 8         if not exchange:  # 如果此标志为False,说明本次循环没有元素交换位置,则结束整个循环
 9             break
10     return array

 

2、选择排序

  选择排序的原理是从序列中选择出最小的元素,放在序列的最左边,然后从剩下的元素中继续寻找最小的元素,放在最左边元素的右边,依次类推,右侧无序的元素越来越少,左侧有序元素越来越多,直至完成排序。代码实现如下:

1 def choice(array):
2     for i in range(len(array)-1):
3         min_index = i
4         for j in range(i+1, len(array)):
5             if array[min_index] > array[j]:
6                 min_index = j
7         array[i], array[min_index] = array[min_index], array[i]
8     return array

 

3、插入排序

  插入排序的原理是从序列的第二个元素开始循环至序列最后,每次循环从当前元素开始不断的与左边相邻的元素进行比较,如果左边的元素较大,则交换两个元素位置,这样序列左边逐步有序。代码实现如下:

1 def insert_sort(array):
2     for i in range(1, len(array)):
3         while i > 0 and array[i] < array[i-1]:
4             array[i], array[i-1] = array[i-1], array[i]
5             i -= 1
6     return array

 

4、快速排序

  快速排序的原理是取序列的第一个元素为基准元素,指定两个指针分别指向序列的开始和结尾,拿结尾指针指向的元素与基准元素比较,如果该元素比基准元素大,则指针减一继续比较,一旦发现比基准元素小的元素,则将该元素放至序列的最左侧,然后拿开始指针指向的元素与基准元素比较,如果该元素比基准元素小,则指针增一继续比较,一旦发现比基准元素大的元素,则将该元素放至结尾指针指向的位置,重复上述过程,则比基准元素大的元素全部到了基准元素右侧,比基准元素小的元素全部到了基准元素左侧,然后对左右两部分继续上述过程,不难发现可应用递归完成最终的排序。

  单次排序代码实现如下:

 1 # 快速排序中的一次调整,即将第一个元素放在某个位置,使该元素右边的元素都比该元素大,左边的元素都比该元素小
 2 def query_mid(array, left, right):
 3     tmp = array[left]
 4     while left < right:
 5         while left < right and tmp <= array[right]:
 6             right -= 1
 7         array[left] = array[right]
 8         while left < right and tmp >= array[left]:
 9             left += 1
10         array[right] = array[left]
11     array[left] = tmp
12     return left

  应用递归完成全部排序,代码实现如下:

1 # 应用递归实现快速排序
2 def _quick_sort(array, left, right):
3     if left < right:
4         mid = query_mid(array, left, right)
5         _quick_sort(array, left, mid-1)
6         _quick_sort(array, mid+1, right)
7     return array

 

5、堆排序

  堆排序应用了二叉树这种数据结构-完全二叉树,分为大顶堆(父节点比任一孩子节点都大)和小顶堆(父节点比任一孩子节点都小),该排序算法的原理是首先将序列构造成大顶堆或者小顶堆,然后取下堆顶元素,将最后一个孩子节点放至堆顶位置,对堆进行调整,变成大顶堆或者小顶堆,通过不断的取下堆顶元素形成一个有序的序列。

  堆得一次构造过程代码实现如下:

 1 # 构建堆的调整过程
 2 def shift(array, low, high):
 3     tmp = array[low]
 4     i = low
 5     j = 2 * i + 1
 6     while j <= high:
 7         if j + 1 <= high and array[j] < array[j + 1]:
 8             j += 1
 9         if tmp < array[j]:
10             array[i] = array[j]
11             i = j
12             j = 2 * i + 1
13         else:
14             break
15     array[i] = tmp

  排序过程代码实现如下:

 1 def heap_sort(array):
 2     n = len(array)
 3     # 将array构造成大顶堆
 4     for i in range(n//2-1, -1, -1):
 5         shift(array, i, n-1)
 6     # 从堆顶开始取数
 7     for i in range(n):
 8         array[0], array[n-1-i] = array[n-1-i], array[0]
 9         shift(array, 0, n-i-2)
10     return array

 

6、归并排序

  归并排序分为分解与合并两个过程,分解过程是将序列细分成两两元素的比较,然后在合并这些两两有序的元素,不断扩大合并,这种合并过程就是序列分成两部分,每一部分都是有序的,然后将这两部分合并成一个大的有序的序列。

  一次归并排序的代码实现如下:

 1 # 一次归并排序
 2 def merge(array, low, mid, high):
 3     tmp_list = []
 4     i = low
 5     j = mid + 1
 6     while i <= mid and j <= high:
 7         if array[i] < array[j]:
 8             tmp_list.append(array[i])
 9             i += 1
10         elif array[i] > array[j]:
11             tmp_list.append(array[j])
12             j += 1
13         else:
14             tmp_list.append(array[i])
15             i += 1
16     if j <= high:
17         for num in array[j:high+1]:
18             tmp_list.append(num)
19     if i <= mid:
20         for num in array[i:mid+1]:
21             tmp_list.append(num)
22     array[low:high+1] = tmp_list
23     return array

  应用递归实现分解与合并的过程代码实现如下:

1 def _merge_sort(array, low, high):
2     if low < high:
3         mid = (low+high) // 2
4         _merge_sort(array, low, mid)
5         _merge_sort(array, mid+1, high)
6         merge(array, low, mid, high)
7     return array

 

7、希尔排序

  希尔排序的原理是,针对待排序的序列,选定一个步长(初始步长一般为序列长度一半),拿出索引相差该步长位置的元素进行插入排序,然后步长减半,再次拿出索引相差该步长位置的元素进行插入排序,直至步长变为1。该排序代码实现如下:

 1 def shell_sort(array):
 2     gap = len(array) // 2
 3     while gap >= 1:
 4         for i in range(gap, len(array)):
 5             tmp = array[i]
 6             j = i - gap
 7             while j >= 0 and array[j] > tmp:
 8                 array[j+gap] = array[j]
 9                 j -= gap
10             array[j+gap] = tmp
11         gap = gap / 2
12     return array

 


  基于以上算法对序列进行排序后,就可以应用二分查找来查找相应的元素,每次拿序列的中间位置元素与被查找元素比较,如果中间位置元素比被查找元素小,则在中间元素右侧的序列中继续该方式查找;如果中间位置元素比被查找元素大,则在中间元素左侧的序列中继续该方式查找,通过该方式每次将范围缩短一半,大大缩短了查找时间,代码实现较简单,如下:

 1 def half_find(array, data):
 2     begin = 0
 3     end = len(array) - 1
 4     while begin <= end:
 5         mid = (begin+end) // 2
 6         if array[mid] == data:
 7             return '%s founded at %s' % (data, mid)
 8         elif array[mid] > data:
 9             end = mid - 1
10         else:
11             begin = mid + 1
12     return 'not found'

 


各算法运行时间比较

  这里构造了一个长度为10000的列表,打乱元素顺序,分别应用以上算法对该列表进行排序,通过一个计算运行时间的装饰器计算出各个排序算法所耗时间,装饰器代码如下:

 1 # 计算算法执行时间装饰器
 2 def use_time(func):
 3     def use_time_inner(*args, **kwargs):
 4         begin_time = time.time()
 5         f = func(*args, **kwargs)
 6         end_time = time.time()
 7         global t
 8         t = end_time - begin_time
 9         print('use time(%s):%ss' % (func.__name__, t))
10         return f
11     return use_time_inner

  使用该装饰器对各个算法进行装饰,执行以下代码得出时间:

 1 # 生成序列
 2 a = list(range(10000))
 3 random.shuffle(a)
 4 l1 = copy.copy(a)
 5 l2 = copy.copy(a)
 6 l3 = copy.copy(a)
 7 l4 = copy.copy(a)
 8 l5 = copy.copy(a)
 9 l6 = copy.copy(a)
10 l7 = copy.copy(a)
11 l8 = copy.copy(a)
12 
13 # 各排序算法执行
14 r1 = bubble_sort(l1)  # 冒泡排序
15 r2 = bubble_better(l2)  # 冒泡排序优化
16 r3 = choice_sort(l3)  # 选择排序
17 r4 = insert_sort(l4)  # 插入排序
18 r5 = quick_sort(l5)  # 快速排序
19 r6 = heap_sort(l6)  # 堆排序
20 r7 = merge_sort(l7)  # 归并排序
21 r8 = shell_sort(l8)  # 希尔排序
22 
23 # 二分查找执行
24 r9 = half_find(r6, random.randint(0, len(a)))

  运行结果如下,可以看到冒泡、选择、插入排序与其他排序算法时间相差还是很悬殊的!

use time(bubble_sort):15.331599950790405s
use time(bubble_better):14.486400127410889s
use time(choice_sort):7.4547998905181885s
use time(insert_sort):13.032400131225586s
use time(quick_sort):0.062399864196777344s
use time(heap_sort):0.062400102615356445s
use time(merge_sort):0.062400102615356445s
use time(shell_sort):0.07799983024597168s
use time(half_find):0.0s

 


原文链接:https://www.cnblogs.com/pysir-blog/p/10345878.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:day21 02 包的进阶

下一篇:Flask信号