>  기사  >  백엔드 개발  >  Python의 8가지 일반적인 정렬 알고리즘에 대한 정의, 구현 및 시간 소비 효율성 분석

Python의 8가지 일반적인 정렬 알고리즘에 대한 정의, 구현 및 시간 소비 효율성 분석

不言
不言원래의
2018-04-27 11:05:221206검색

이 글에서는 주로 Python의 8가지 정렬 알고리즘에 대한 정의, 구현 및 시간 소모 효율성 분석을 소개하며, 또한 버블 정렬, 직접 삽입 정렬, 선택 정렬, 병합 정렬, 힐 정렬, 버킷 정렬, 힙을 구체적인 예와 비교합니다. 정렬 등 정렬 알고리즘의 사용 및 실행 효율성에 대해서는 도움이 필요한 친구들이 참고할 수 있습니다

이 기사에서는 Python에서 흔히 사용되는 8가지 정렬 알고리즘에 대한 정의, 구현 및 시간 소비 효율성 분석에 대해 설명합니다. 참고하실 수 있도록 자세한 내용은 다음과 같습니다.

어젯밤에 몇 가지 일반적인 정렬 알고리즘을 요약하기 시작했습니다. 이전에 정렬 알고리즘에 관한 여러 관련 블로그 게시물을 작성했기 때문에 매우 편리하다고 할 수 있습니다. 여기서의 목적은 이러한 정렬 알고리즘에 대해 보다 완전하고 자세한 요약을 제공하고 버블 정렬, 직접 삽입 정렬, 선택 정렬, 병합 정렬, 힐 정렬, 버킷 정렬 및 힙의 기본 사항을 검토하는 것입니다. 종류. 분석하고 구현하기 위한 빠른 정렬부터 시작하겠습니다. 마지막에는 원리와 알고리즘 기초에 중점을 두고 있으며, 그 다음에는 이러한 분야의 숙련도가 향후 작업이나 인터뷰 준비에 중요하지 않습니다. 알고리즘은 내부 의미와 이론적 근거를 이해하는 데 중점을 둡니다. 이를 구현해야만 함정을 피하고 실수를 줄일 수 있습니다. 이는 연습 중에 실수하는 것이 나쁘다는 의미는 아니지만, 가능한 한 실수는 적습니다. 좋은 프로그래밍 습관은 엄격한 제약과 불가분의 관계입니다. 여기서는 자세한 내용을 검토하지 않고 구체적인 구현을 살펴보겠습니다. 설명은 매우 자세해야 합니다. 설명:

#!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

결과는 다음과 같습니다:

bubble_sort 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419 , 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 81 3, 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, 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]
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, 71 8, 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, 954 , 976, 998]
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, 00 , 918, 954, 976, 998]
통_정렬 [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, 8 85, 894, 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, 57 0, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 998]
빠른 정렬 [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, 5 25, 570, 618, 651, 701, 711, 717, 718, 752, , 813, 816, 845, 885, 894, 900, 918, 954, 976, 998]

여기에서는 데코레이터를 사용하지 않습니다. 주로 이 데코레이터에 대해 잘 모릅니다. 빠른 정렬 중에 오류를 보고했지만 보고하지 않았습니다. 다음은 데코레이터 사용 결과에 대한 간단한 테스트 예입니다.

Bubble_sort에 소요되는 시간: 0.0290870666504
결과는 다음과 같습니다: [5, 45, 46, 63, 81, 83, 89, 89, 89, 90]
None
Insert_sort에 소요되는 시간: 0.0209808349609
결과는 다음과 같습니다. 5 , 45 , 46, 63, 81, 83, 89, 89, 89, 90]
없음
Select_sort에 소요되는 시간: 0.0259876251221
결과는 다음과 같습니다: [5, 45, 46, 63, 81, 83, 89, 89, 89, 90 ]
Nonegmerge_sort에는 시간이 걸립니다: 0.0138282775879
결과는 다음과 같습니다: [5, 45, 46, 63, 81, 89, 89, 89, 90]
Sone
shell_sort에는 시간이 걸립니다: 0.11396408080811
결과는: [5 , 4 5, 46 , 63, 81, 83, 89, 89, 89, 90]
없음
Tong_sort에 소요되는 시간: 0.0460147857666
결과는 다음과 같습니다: [5, 45, 46, 63, 81, 83, 89, 89, 89 , 90]
None
Heap_sort에는 시간이 걸립니다: 0.046968460083
결과는 다음과 같습니다: [5, 45, 46, 63, 81, 83, 89, 89, 89, 90]
None
Quick_sort [5, 45, 46, 63, 81, 83, 89, 89, 89, 90]
----------------------------- --------------------------
9ea51c619c334b7056c3db049e0c14df 0.113964080811
< ;function Select_sort at 0.0259876251221
0.0209808349609
. 68460083
0.0138282775879
0.0460147857666

시간이 있으면 데코레이터에 대해 배우고 싶습니다. 데코레이터는 단순히 패턴화된 것들을 위한 인공물이라고 생각하지만, 데코레이터를 사용하는 방법과 작성하는 방법을 알아야 합니다!


위 내용은 Python의 8가지 일반적인 정렬 알고리즘에 대한 정의, 구현 및 시간 소비 효율성 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명:
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.