python常⽤8⼤算法
1-插⼊排序
描述
插⼊排序的基本操作就是将⼀个数据插⼊到已经排好序的有序数据中，从⽽得到⼀个新的、个数加⼀的有序数据，算法适⽤于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序⽅法。插⼊算法把要排序的数组分成两部分：
第⼀部分包含了这个数组的所有元素，但将最后⼀个元素除外（让数组多⼀个空间才有插⼊的位置），⽽第⼆部分就只包含这⼀个元素（即待插⼊元素）。在第⼀部分排序完成后，再将这个最后元素插⼊到已排好序的第⼀部分中。
def insert_sort(lists):
# 插⼊排序
count =len(lists)
for i in range(1, count):
key = lists[i]
j = i -1
while j >=0:
if lists[j]> key:
lists[j +1]= lists[j]
lists[j]= key
j -=1
return lists
2-希尔排序
描述
希尔排序(Shell Sort)是插⼊排序的⼀种。也称缩⼩增量排序，是直接插⼊排序算法的⼀种更⾼效的改进版本。希尔排序是⾮稳定排序算法。该⽅法因DL．Shell于1959年提出⽽得名。
希尔排序是把记录按下标的⼀定增量分组，对每组使⽤直接插⼊排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减⾄1时，整个⽂件恰被分成⼀组，算法便终⽌。
'''
遇到问题没⼈解答？⼩编创建了⼀个Python学习交流QQ：778463939
寻有志同道合的⼩伙伴，互帮互助，⾥还有不错的视频学习教程和PDF电⼦书！
'''
def shell_sort(lists):
# 希尔排序
count =len(lists)
step =2
group = count / step
while group >0:
for i in range(0, group):
j = i + group
while j < count:
k = j - group
key = lists[j]
while k >=0:
if lists[k]> key:
lists[k + group]= lists[k]
lists[k]= key
k -= group
j += group
group /= step
return lists
3-冒泡排序
它重复地⾛访过要排序的数列，⼀次⽐较两个元素，如果他们的顺序错误就把他们交换过来。⾛访数列的⼯作是重复地进⾏直到没有再需要交换，也就是说该数列已经排序完成。
def bubble_sort(lists):
# 冒泡排序
count =len(lists)
for i in range(0, count):
for j in range(i +1, count):
if lists[i]> lists[j]:
lists[i], lists[j]= lists[j], lists[i]
return lists
4-快速排序
描述
通过⼀趟排序将要排序的数据分割成独⽴的两部分，其中⼀部分的所有数据都⽐另外⼀部分的所有数据都要⼩，然后再按此⽅法对这两部分数据分别进⾏快速排序，整个排序过程可以递归进⾏，以此达到整个数据变成有序序列。
'''
遇到问题没⼈解答？⼩编创建了⼀个Python学习交流QQ：778463939
寻有志同道合的⼩伙伴，互帮互助，⾥还有不错的视频学习教程和PDF电⼦书！
'''
def quick_sort(lists, left, right):
# 快速排序
if left >= right:
return lists
key = lists[left]
low = left
high = right
while left < right:
while left < right and lists[right]>= key:
right -=1
lists[left]= lists[right]
while left < right and lists[left]<= key:
left +=1
lists[right]= lists[left]
lists[right]= key
quick_sort(lists, low, left -1)
quick_sort(lists, left +1, high)
return lists
5-直接选择排序
描述
基本思想：第1趟，在待排序记录r1 ~ r[n]中选出最⼩的记录，将它与r1交换；第2趟，在待排序记录r2 ~ r[n]中选出最⼩的记录，将它与r2交换；以此类推，第i趟在待排序记录r[i] ~ r[n]中选出最⼩的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。
def select_sort(lists):
# 选择排序
count =len(lists)
for i in range(0, count):
min= i
for j in range(i +1, count):
if lists[min]> lists[j]:
min= j
lists[min], lists[i]= lists[i], lists[min]
return lists
6-堆排序
堆排序(Heapsort)是指利⽤堆积树（堆）这种数据结构所设计的⼀种排序算法，它是选择排序的⼀种。可以利⽤数组的特点快速定位指定索引的元素。堆分为⼤根堆和⼩根堆，是完全⼆叉树。⼤根堆的要求是每个节点的值都不⼤于其⽗节点的值，即A[PARENT[i]] >= A[i]。在数组的⾮降序排序中，需
要使⽤的就是⼤根堆，因为根据⼤根堆的要求可知，最⼤的值⼀定在堆顶。
'''
遇到问题没⼈解答？⼩编创建了⼀个Python学习交流QQ：778463939
寻有志同道合的⼩伙伴，互帮互助，⾥还有不错的视频学习教程和PDF电⼦书！
'''
def adjust_heap(lists, i, size):
lchild =2* i +1
rchild =2* i +2
max= i
if i < size /2:
if lchild < size and lists[lchild]> lists[max]:
max= lchild
if rchild < size and lists[rchild]> lists[max]:
max= rchild
if max!= i:
lists[max], lists[i]= lists[i], lists[max]
adjust_heap(lists,max, size)
def build_heap(lists, size):
for i in range(0,(size/2))[::-1]:
adjust_heap(lists, i, size)
def heap_sort(lists):
size =len(lists)
build_heap(lists, size)
for i in range(0, size)[::-1]:
lists[0], lists[i]= lists[i], lists[0]
adjust_heap(lists,0, i)
7-归并排序
描述
归并排序是建⽴在归并操作上的⼀种有效的排序算法，该算法是采⽤分治法（Divide and Conquer）的⼀个⾮常典型的应⽤。将已有序的⼦序列合并，得到完全有序的序列；即先使每个⼦序列有序，再使⼦序列段间有序。若将两个有序表合并成⼀个有序表，称为⼆路归并。
归并过程为：⽐较a[i]和a[j]的⼤⼩，若a[i]≤a[j]，则将第⼀个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第⼆个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中⼀个有序表取完，然后再将另⼀个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常⽤递归实现，先把待排序区间[s,t]以中点⼆分，接着把左边⼦区间排序，再把右边⼦区间排序，最后把左区间和右区间⽤⼀次归并操作合并成有序的区间[s,t]。
'''
遇到问题没⼈解答？⼩编创建了⼀个Python学习交流QQ：778463939
寻有志同道合的⼩伙伴，互帮互助，⾥还有不错的视频学习教程和PDF电⼦书！
'''
def merge(left, right):
i, j =0,0
result =[]
while i <len(left)and j <len(right):
if left[i]<= right[j]:
result.append(left[i])
i +=1
else:
result.append(right[j])
j +=1
result += left[i:]
result += right[j:]
return result
def merge_sort(lists):
# 归并排序
if len(lists)<=1:
return lists
快速排序python实现num =len(lists)/2
left = merge_sort(lists[:num])
right = merge_sort(lists[num:])
return merge(left, right)
8-基数排序
描述
基数排序（radix sort）属于“分配式排序”（distribution sort），⼜称“桶⼦法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配⾄某些“桶”中，藉以达到排序的作⽤，基数排序法是属于稳定性的排序，其时间复杂度为O
(nlog®m)，其中r为所采取的基数，⽽m为堆数，在某些时候，基数排序法的效率⾼于其它的稳定性排序法。
import math
def radix_sort(lists, radix=10):
k =il(math.log(max(lists), radix)))
bucket =[[]for i in range(radix)]
for i in range(1, k+1):
for j in lists:
bucket[j/(radix**(i-1))%(radix**i)].append(j)
del lists[:]
for z in bucket:
lists += z
del z[:]
return lists

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。