Definition, implementation and time consumption efficiency analysis of eight common sorting algorithms in Python

This article mainly introduces the definition, implementation and time consumption efficiency analysis of eight common sorting algorithms in Python. It also compares bubble sort, direct insertion sort, selection sort, merge sort, Hill sort, and bucket sort with specific examples. For the use and execution efficiency of sorting algorithms such as , heap sort, etc., friends in need can refer to

This article describes the definition, implementation and time consumption efficiency analysis of eight common sorting algorithms in Python. I share it with you for your reference. The details are as follows:

Last night I started to summarize several common sorting algorithms. Since I have written several related blog posts about sorting algorithms before, I can summarize it now. It is very convenient to say that the purpose here is to summarize these sorting algorithms more completely and in detail, in order to review the basic things, from bubble sort, direct insertion sort, selection sort, merge sort, Hill sort, bucket sort, heap sort Sort. Let’s start with quick sorting to analyze and implement. At the end, we also give simple time statistics. The emphasis is on the principles and algorithm foundations, followed by others. Proficiency in these things is not important for future work or preparation for interviews. Very helpful. The algorithm focuses on understanding the inner meaning and theoretical basis. Only when implementing it can you avoid pitfalls and make fewer mistakes. This does not mean that it is bad to make mistakes during practice, but it means that there should be as few mistakes as possible that should not occur. Well done. After all, good programming habits are inseparable from strict constraints. Well, I won’t go into details here. Let’s review the basic knowledge and study together. The following is the specific implementation. The comments should be very detailed. Explained:

#!usr/bin/env python
#encoding:utf-8
'''''
__Author__:沂水寒城
功能：八大排序算法
'''
import time
import random
time_dict={}
def time_deco(sort_func):
  '''''
  时间计算的装饰器函数,可用于计算函数执行时间
  '''
  def wrapper(num_list):
    start_time=time.time()
    res=sort_func(num_list)
    end_time=time.time()
    time_dict[str(sort_func)]=(end_time-start_time)*1000
    print '耗时为：',(end_time-start_time)*1000
    print '结果为：', res
  return wrapper
def random_nums_generator(max_value=1000, total_nums=20):
  '''''
  随机数列表生成器
  一些常用函数：
  random随机数生成
  random.random()用于生成一个0到1之间的随机数:0 <= n < 1.0；
  random.uniform(a, b)，用于生成一个指定范围内的随机符点数，两个参数其中一个是上限，一个是下限。min(a,b) <= n <= max(a,b)；
  randdom.randint(a, b), 用于生成一个指定范围内的整数，其中a是下限，b是上限： a<= n <= b；
  random.randrange(start, stop, step), 从指定范围内，按指定基数递增的集合获取一个随机数；
  random.choice(sequence), 从序列中获取一个随机元素；
  random.shuffle(x), 用于将一个列表中的元素打乱；
  random.sample(sequence, k), 从指定序列中随机获取指定长度的片断；
  &#39;&#39;&#39;
  num_list=[]
  for i in range(total_nums):
    num_list.append(random.randint(0,max_value))
  return num_list
#@time_deco
def Bubble_sort(num_list):
  &#39;&#39;&#39;&#39;&#39;
  冒泡排序，时间复杂度O(n^2)，空间复杂度O(1)，是稳定排序
  &#39;&#39;&#39;
  for i in range(len(num_list)):
    for j in range(i,len(num_list)):
      if num_list[i]>num_list[j]: #这里是升序排序
        num_list[i], num_list[j]=num_list[j], num_list[i]
  return num_list
#@time_deco
def Insert_sort(num_list):
  &#39;&#39;&#39;&#39;&#39;
  直接插入排序，时间复杂度O(n^2)，空间复杂度O(1)，是稳定排序
  &#39;&#39;&#39;
  for i in range(len(num_list)):
    for j in range(0,i):
      if num_list[i]<num_list[j]: #这里是升序排序,跟冒泡排序差别在于，冒泡是向后遍历，这个是向前遍历
        num_list[i], num_list[j]=num_list[j], num_list[i]
  return num_list
#@time_deco
def Select_sort(num_list):
  &#39;&#39;&#39;&#39;&#39;
  选择排序，时间复杂度O(n^2)，空间复杂度O(1)，不是稳定排序
  &#39;&#39;&#39;
  for i in range(len(num_list)):
    min_value_index=i
    for j in range(i, len(num_list)):
      if num_list[j]<num_list[min_value_index]:
        min_value_index=j #乍一看，感觉冒泡，选择，插入都很像，选择跟冒泡的区别在于：冒泡是发现大
                 #小数目顺序不对就交换，而选择排序是一轮遍历结束后选出最小值才交换，效率更高
    num_list[i], num_list[min_value_index]=num_list[min_value_index], num_list[i]
  return num_list
#@time_deco
def Merge_sort(num_list):
  &#39;&#39;&#39;&#39;&#39;
  归并排序，时间复杂度O(nlog₂n)，空间复杂度：O(1)，是稳定排序
  &#39;&#39;&#39;
  if len(num_list)==1:
    return num_list
  length=len(num_list)/2
  list1=num_list[:length]
  list2=num_list[length:]
  result_list=[]
  while len(list1) and len(list2):
    if list1[0]<=list2[0]:
      result_list.append(list1[0])
      del list1[0] #这里需要删除列表中已经被加入到加过列表中的元素，否则最后比较完后列表
    else:       #中剩余元素无法添加
      result_list.append(list2[0])
      del list1[0]
  if len(list1): #遍历比较完毕后列表中剩余元素的添加
    result_list+=list1
  else:
    result_list+=list2
  return result_list
#@time_deco
def Shell_sort(num_list):
  &#39;&#39;&#39;&#39;&#39;
  希尔排序，时间复杂度：O(n)，空间复杂度：O(n^2),不是稳定排序算法
  &#39;&#39;&#39;
  new_list = []
  for one_num in num_list:
    new_list.append(one_num)
  count=len(new_list)
  step=count/2;
  while step>0:
    i=0
    while i<count:
      j=i+step
      while j<count:
        t=new_list.pop(j)
        k=j-step
        while k>=0:
          if t>=new_list[k]:
            new_list.insert(k+1, t)
            break
          k=k-step
        if k<0:
          new_list.insert(0, t)
        #print &#39;---------本轮结果为：--------&#39;
        #print new_list
        j=j+step
        #print j
      i=i+1
      #print i
    step=step/2   #希尔排序是一个更新步长的算法
  return new_list
#@time_deco
def Tong_sort(num_list):
  &#39;&#39;&#39;&#39;&#39;
  桶排序，时间复杂度O(1)，空间复杂度与最大数字有关，可以认为是O(n)，典型的空间换时间的做法
  &#39;&#39;&#39;
  original_list = []
  total_num=max(num_list) #获取桶的个数
  for i in range(total_num+1): #要注意这里需要的数组元素个数总数比total_num数多一个因为下标从0开始
    original_list.append(0)
  for num in num_list:
    original_list[num] += 1
  result_list = []
  for j in range(len(original_list)):
    if original_list[j] != 0:
      for h in range(0,original_list[j]):
        result_list.append(j)
  return result_list
def Quick_sort(num_list):
  &#39;&#39;&#39;&#39;&#39;
  快速排序，时间复杂度：O(nlog₂n)，空间复杂度：O(nlog₂n)，不是稳定排序
  &#39;&#39;&#39;
  if len(num_list)<2:
    return num_list
  left_list = [] #存放比基准结点小的元素
  right_list = [] #存放比基准元素大的元素
  base_node = num_list.pop(0) #在这里采用pop()方法的原因就是需要移除这个基准结点，并且赋值给base_node这个变量
                #在这里不能使用del()方法，因为删除之后无法再赋值给其他变量使用，导致最终数据缺失
                #快排每轮可以确定一个元素的位置，之后递归地对两边的元素进行排序
  for one_num in num_list:
    if one_num < base_node:
      left_list.append(one_num)
    else:
      right_list.append(one_num)
  return Quick_sort(left_list) + [base_node] + Quick_sort(right_list)
def Heap_adjust(num_list, i, size):
  left_child = 2*i+1
  right_child = 2*i+2
  max_temp = i
  #print left_child, right_child, max_temp
  if left_child<size and num_list[left_child]>num_list[max_temp]:
    max_temp = left_child
  if right_child<size and num_list[right_child]>num_list[max_temp]:
    max_temp = right_child
  if max_temp != i:
    num_list[i], num_list[max_temp] = num_list[max_temp], num_list[i]
    Heap_adjust(num_list, max_temp, size) #避免调整之后以max为父节点的子树不是堆
def Create_heap(num_list, size):
  a = size/2-1
  for i in range(a, -1, -1):
    #print &#39;**********&#39;, i
    Heap_adjust(num_list, i, size)
#@time_deco
def Heap_sort(num_list):
  &#39;&#39;&#39;&#39;&#39;
  堆排序，时间复杂度：O(nlog₂n)，空间复杂度：O(1)，不是稳定排序
  &#39;&#39;&#39;
  size=len(num_list)
  Create_heap(num_list, size)
  i = size-1
  while i > 0:
    num_list[0], num_list[i] = num_list[i], num_list[0]
    size -= 1
    i -= 1
    Heap_adjust(num_list, 0, size)
  return num_list
if __name__ == &#39;__main__&#39;:
  num_list=random_nums_generator(max_value=100, total_nums=50)
  print &#39;Bubble_sort&#39;, Bubble_sort(num_list)
  print &#39;Insert_sort&#39;, Insert_sort(num_list)
  print &#39;Select_sort&#39;, Select_sort(num_list)
  print &#39;Merge_sort&#39;, Merge_sort(num_list)
  print &#39;Shell_sort&#39;, Shell_sort(num_list)
  print &#39;Tong_sort&#39;, Tong_sort(num_list)
  print &#39;Heap_sort&#39;, Heap_sort(num_list)
  print &#39;Quick_sort&#39;, Quick_sort(num_list)
  # print &#39;-----------------------------------------------------------------------------&#39;
  # for k,v in time_dict.items():
  #   print k, v

The results are as follows:

Bubble_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570 , 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 998]
Insert_sort [34, 49, 63, 67, 71 , 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 259, 259, 260, 293, 295, 304, 326, 396, 401, 423, 456 , 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 998]
Select_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 998]
Merge_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362 , 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 9 98 ]
Shell_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918 , 954, 976, 998]
Tong_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293 , 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 8 94 , 900, 918, 954, 976, 998]
Heap_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816 , 845, 885, 894, 900, 918, 954, 976, 998]
Quick_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241 , 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 7 74 , 813, 816, 845, 885, 894, 900, 918, 954, 976, 998]

No decorator is used here, mainly because I don’t know much about this decorator. In quick sort An error was reported, but there was no solution. Here is a simple test example of the result of using the decorator:

Bubble_sort takes time: 0.0290870666504
The result is: [5, 45, 46, 63, 81, 83, 89, 89, 89, 90]
None
Insert_sort takes time: : 0.0209808349609
The result is: [5, 45, 46, 63, 81, 83, 89, 89, 89, 90]
None
Select_sort takes time: 0.0259876251221
The result is: [5 , 45, 46, 63, 81, 83, 89, 89, 89, 90]
None
Merge_sort takes time: 0.0138282775879
The result is: [5, 45, 46, 63, 81, 83 , 89, 89, 89, 90]
None
Shell_sort takes time: 0.113964080811
The result is: [5, 45, 46, 63, 81, 83, 89, 89, 89, 90]
None
Tong_sort takes time: 0.0460147857666
The result is: [5, 45, 46, 63, 81, 83, 89, 89, 89, 90]
None
Heap_sort takes time: : 0.046968460083
The result is: [5, 45, 46, 63, 81, 83, 89, 89, 89, 90]
None
Quick_sort [5, 45, 46, 63, 81, 83, 89, 89, 89, 90]
--------------------------------------------- -------------------------------------
0.113964080811
0.0259876251221 046968460083
0.0138282775879
0.0460147857666
0.0290870666504

If I have time, I want to learn about decorators. I feel that decorators are simply an artifact for patterned things. , but you have to know how to use and write it!

The above is the detailed content of Definition, implementation and time consumption efficiency analysis of eight common sorting algorithms in Python. For more information, please follow other related articles on the PHP Chinese website!