python---算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了python---算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4768字，纯文字阅读大概需要7分钟。

内容图文

一、冒泡排序。

核心思想：通过双层循环遍历，每次比较两个数，如果他们顺序错误（大于或者小于），那么就把他们位置交换。

冒泡排序算法利用了双层循环，时间复杂度为O(n^2)

稳定性为：稳定

1 li=[10,2,3,5,110,55,99,88,66]
2 def bubble_sort(li):
3     count=len(li)
4     for i in range(0,count):
5         for j in range(i+1,count):
6             if li[i]>li[j]:
7                 li[i],li[j]=li[j],li[i]
8     return li
9 print(bubble_sort(li))

二、插入排序。

核心思想：它把一个无序数列看成两个数列，假如第一个元素构成了第一个数列，那么余下的元素构成了第二个数列，很显然，第一个数列是有序的（因为只有一个元素嘛，肯定有序哦），那么我们把第二个数列的第一个元素拿出来插入到第一个数列，使它依然构成一个有序数列，直到第二个数列中的所有元素全部插入到第一个数列，这时候就排好序了。

插入排序的复杂度是O(n^2)

 1 def insert_sort(l):
 2     for i in range(1,len(l)):  #无序的
 3         num=l[i]
 4         j=i-1
 5         while j>=0 and l[j]>num:   #有序的
 6             
 7             l[j+1]=l[j]
 8             j-=1
 9             
10         l[j+1]=num
11     return l
12 l=[1,2,4,22,5,3,66,9]
13 insert_sort(l)
14 print(l)
15         

三、选择排序 

每次从列表中找最小的数放前，之后从剩余列表中再找最小的数，直到把所有的数找完为止。

详解：1、把第一个数作为基准数（base）

      2、把剩余的数作为一个列表和基准数进行比较，小于基准数，和base交换位置，直到把剩余所有数遍历完，找到最小的数放到i的位置。

      3、然后重复步骤2

时间复杂度：n^2

 1 def select_sort(l):
 2     min_num=0
 3     for i in range(len(l)-1):
 4         min_num=i
 5         for j in range(i+1,len(l)):
 6             if l[min_num]>l[j]:
 7                 min_num=j
 8         l[min_num],l[i]=l[i],l[min_num]
 9     return l
10 l=[1,4,2,3,9,5,7,6,8,10]
11 print(select_sort(l))

四、快速排序

快速排序基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

[2,4,6,1,3,9,7,8]

详解：1、把第一个数2作为基准数，从右到左找比基准数小的数，找到之后和low数换位置，然后从做到找比基准数大的数，找到后和high数换位置（基准数固定，这个数字一定），当low 和 high相等的时候，就分成两组，基准数左边的数列全都小于基准数右边的数列。

      2、然后把左边的数列和右边的数列分开，继续重复步骤一，找最左边的为基准数，直到所有数都排完为止。

快排复杂度：最坏的：0（n^2）

            平均复杂度 ：0（nlog2n）

 1 def quick_sort(array,start,last):
 2     while start > last:
 3         return array
 4     low=start
 5     high=last
 6     base_num=array[low]
 7     while low < high:
 8         while low < high and array[high] > base_num:
 9             high-=1
10         array[high]=array[low]
11         while low < high and array[low] < base_num:
12             low+=1
13         array[low]=array[high]
14     array[low]=base_num
15     quick_sort(array,start,low)
16     quick_sort(array,low+1,last)
17     return array
18 l=[1,4,6,2,9,7,3,0]
19 v=quick_sort(l,0,7)
20 print(v)
21 

 五、堆排序

核心思想：堆是一种数据结构，可以看作一棵树完全二叉树，这棵二叉树满足，任何一个非叶子的值都大于左右孩子节点的值。将一个无序序列调整为一个堆，就可以找出这个序列的最大值（或最小值），然后将找出的这个值交换序列最后一个值，这样有序序列元素就增加一个，无序序列就减少一个，对新的无序序列重复这样的操作，就实现了排序。

复杂度：o(nlgn)

 1 def adjust_heap(array,i,size):
 2     lchild=2*i+1
 3     rchild=2*i+2
 4     maxa=i
 5     if i < size//2:
 6         if lchild < size and array[lchild] > array[maxa]:
 7             maxa=lchild
 8         if rchild < size and array[rchild] > array[maxa]:
 9             maxa=rchild
10         if maxa != i:
11             array[maxa],array[i]=array[i],array[maxa]
12             adjust_heap(array,maxa,size)
13 
14 def build_heap(array,size):
15     for i in range(0,size//2)[::-1]:
16         adjust_heap(array,i,size)
17 
18 def heap_sort(array):
19     size=len(array)
20     build_heap(array,size)
21     for i in range(0,size)[::-1]:
22         array[0],array[i]=array[i],array[0]
23         adjust_heap(array,0,i)
24     return array
25 array=[4,2,5,7,1,8]
26 print(heap_sort(array))

六、二分查找（针对有序序列）

思想：折半思想，取这列数的中间值，如果要查找的这个数大于中间数，可以从中间数到最后作为一个数列去查找，再取此时数列的中间数，重复这样的操作，直到找到或者取完没找到为止；小于中间数，则把开头到中间数之前作为一个数列，然后折半。--采用递归

时间复杂度：o（log2n）

 1 # _*_ encoding:utf-8 _*_
 2 L=[2,5,8,11,33,66,77,88]
 3 num=6
 4 def binary_search(L,num):
 5     if len(L)>1:
 6         mid=len(L)//2
 7         if L[mid]==num:
 8             print('找到结果')
 9         if L[mid]>num:
10             return binary_search(L[:mid],num)
11         else:
12             return binary_search(L[mid:],num)
13             
14     else:
15         if L[0]==num:
16             print('找到数字了')
17         else:
18             print('此结果不在列表中')
19         
20     
21 binary_search(L,num)

 

 

内容总结

以上是互联网集市为您收集整理的python---算法全部内容，希望文章能够帮你解决python---算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---