大佬教程收集整理的这篇文章主要介绍了数据结构之排序算法(python),大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
数据结构中的十大经典算法:冒泡排序、快速排序、简单插入排序、希尔排序、简单选择排序、堆排序、归并排序、计数排序、桶排序、基数排序
十大经典算法的复杂度和稳定性(如果a原本在b前面c;而A=bc;排序之后a仍然在b的前面):
它重复地走访过要排序的数列c;一次比较两个元素c;如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换c;也就是说该数列已经排序完成
def bubble_sort(blist):
count = len(blist)
for i in range(0, count):
for j in range(i + 1, count):
if blist[i] > blist[j]:
blist[i], blist[j] = blist[j], blist[i]
return blist
找基准数c;通过一趟排序将要排序的数据分割成独立的两部分c;其中一部分的所有数据都比另外一部分的所有数据都要小c;然后再按此方法对这两部分数据分别进行快速排序c;整个排序过程可以递归进行c;以此达到整个数据变成有序序列
def quick_sort(qlist):
if qlist == []:
return []
else:
qfirst = qlist[0]
qless = quick_sort([l for l in qlist[1:] if l < qfirst])
qmore = quick_sort([m for m in qlist[1:] if m >= qfirst])
return qless + [qfirst] + qmore
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中c;从而得到一个新的、个数加一的有序数据c;算法适用于少量数据的排序;首先将第一个作为已经排好序的c;然后每次从后的取出插入到前面并排序
def insert_sort(ilist):
for i in range(len(ilist)):
for j in range(i):
if ilist[i] < ilist[j]:
ilist.insert(j, ilist.pop(i))
break
return ilist
先取一个正整数 d1c;以 d1 间隔分组c;先对每个分组内的元素使用插入排序操作c;重复上述分组和直接插入排序操作;直至 di = 1c;即所有记录放进一个组中排序为止。
def sHell_sort(slist):
gap = len(slist)
while gap > 1:
gap = gap // 2
for i in range(gap, len(slist)):
for j in range(i % gap, i, gap):
if slist[i] < slist[j]:
slist[i], slist[j] = slist[j], slist[i]
return slist
第1趟c;在待排序记录r1 ~ r[n]中选出最小的记录c;将它与r1交换;第2趟c;在待排序记录r2 ~ r[n]中选出最小的记录c;将它与r2交换;以此类推c;第i趟在待排序记录r[i] ~ r[n]中选出最小的记录c;将它与r[i]交换c;使有序序列不断增长直到全部排序完毕
def SELEct_sort(slist):
for i in range(len(slist) - 1):
x = i
for j in range(i, len(slist)):
if slist[j] < slist[x]:
x = j
slist[i], slist[x] = slist[x], slist[i]
return slist
它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆c;是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值。在数组的非降序排序中c;需要使用的就是大根堆c;因为根据大根堆的要求可知c;最大的值一定在堆顶
@H_944_124@
import math
def heap_sort(a):
al = len(a)
def heapify(a, i):
left = 2 * i + 1
right = 2 * i + 2
largest = i
if left < al and a[left] > a[largest]:
largest = left
if right < al and a[right] > a[largest]:
largest = right
if largest != i:
a[i], a[largest] = a[largest], a[i]
heapify(a, largest)
# 建堆
for i in range(math.floor(len(a) / 2), -1, -1):
heapify(a, i)
# 不断调整堆:根与最后一个元素
for i in range(len(a) - 1, 0, -1):
a[0], a[i] = a[i], a[0]
al -= 1
heapify(a, 0)
return a
采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并c;得到完全有序的序列;即先使每个子序列有序c;再使子序列段间有序。若将两个有序表合并成一个有序表c;称为二路归并
def merge_sort(a):
if(len(a)<2):
return a
middle = len(a)//2
left, right = a[0:middle], a[middle:]
return merge(merge_sort(left), merge_sort(right))
def merge(left,right):
result = []
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0));
else:
result.append(right.pop(0));
while left:
result.append(left.pop(0));
while right:
result.append(right.pop(0));
return result
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序c;计数排序要求输入的数据必须是有确定范围的整数。
def counTingSort(arr, maxvalue):
bucketLen = maxValue+1
bucket = [0]*bucketLen
sortedIndex =0
arrLen = len(arr)
for i in range(arrLen):
if not bucket[arr[i]]:
bucket[arr[i]]=0
bucket[arr[i]]+=1
for j in range(bucketLen):
while bucket[j]>0:
arr[sortedIndex] = j
sortedIndex+=1
bucket[j]-=1
return arr
为了节省空间和时间c;我们需要指定要排序的数据中最小以及最大的数字的值。将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)
def bucketSort(nums):
bucket=[0]*(max(nums)-min(nums)+1)
for i in range(len(nums)):
bucket[nums[i]-min(nums)]+=1
tmp=[]
for i in range(len(bucket)):
if bucket[i]!=0:
tmp+=[min(nums)+i]*bucket[i]
return tmp
基数排序将数据按位进行分桶c;然后将桶中的数据合并。每次分桶只关注其中一位数据c;其他位的数据不管c;最大的数据有多少位c;就进行多少次分桶和合并。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数c;所以基数排序也不是只能使用于整数。
def radix_sort(array):
bucket, digit = [[]], 0
while len(bucket[0]) != len(array):
bucket = [[], [], [], [], [], [], [], [], [], []]
for i in range(len(array)):
num = (arraY[i] // 10 ** digit) % 10
bucket[num].append(arraY[i])
array.clear()
for i in range(len(bucket)):
array += bucket[i]
digit += 1
return array
以上是大佬教程为你收集整理的数据结构之排序算法(python)全部内容,希望文章能够帮你解决数据结构之排序算法(python)所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。