排序

基本思想：各类排序的共同点，个人认为可以把原始的数据序列，划分为有序序列与无序序列。有序序列开始可能为0，在每一次操作（循环或者递归）后，有序序列数目会加1，无序序列数目会减一，代码走完后，原本的数据序列完全变成有序序列。

在学校常写的简单排序，确实是简单粗暴。

def sort(lyst):for i in range(len(lyst)):for j in range(i+1, len(lyst)):if lyst[j] < lyst[i]:lyst[i], lyst[j] = lyst[j], lyst[i]print("Sorted list:{}".format(lyst))

额。。这个在学校时一直把它理解为冒泡排序。。实际上应该不是吧，都没有一个冒泡上升的过程。像是选择排序的一种变体。

选择排序

关于选择排序，例如初始序列是5,3,1,2,4.

1.搜索整个列表，找到最小项的位置，如果该位置不是列表第一项。则交换两项位置。

2.从第二项开始一次往后搜索与替换。

def selectionSort(lyst):for i in range (len(lyst)):minIndex =ifor j in range (i+1,len(lyst)):if (lyst[j]<lyst[minIndex]):minIndex=jif minIndex != i:lyst[i],lyst[minIndex]=lyst[minIndex],lyst[i]print("selectionSort:",lyst)

冒泡排序

这个就不多说了吧，比较交换，小头冒泡或者大头冒泡

def bubbleSort(lyst):for i in range(len(lyst)-1):for j in range(i + 1, 0, -1):if lyst[j] < lyst[j - 1]:lyst[j], lyst[j - 1] = lyst[j - 1], lyst[j]return lystif __name__ == '__main__':a = [7, 5, 9, 8, 1, 4]print(bubbleSort(a))

优化：如果原本要排序的列表即为有序列表，则添加一个bool变量用做判断，如无交换则直接return

#冒泡排序的优化在于加上flag bool变量后，如果为有序序列，则在def bubbleSort_improved(lyst):swapped=Falsefor i in range (len(lyst))[::-1]:for j in range (i):if lyst[j]>lyst[j+1]:lyst[j+1],lyst[j]=lyst[j],lyst[j+1]swapped = True#两层循环，在内层循环比较完后，交换变量swapped仍未发生改变，则直接输出后returnif not swapped:print("bubbleSort_improved:", lyst)returnprint("bubbleSort_improved:",lyst)

插入排序

def insertionSort(arr: [int]) -> [int]:n = len(arr)for i in range(1, n):for j in range(i, -1, -1):if j > 1 and arr[j] < arr[j - 1]:arr[j], arr[j - 1] = arr[j - 1], arr[j]return arr

快速排序

lyst=[8,7,3,1,2,3,6,0,12,7]a=deepcopy(lyst)#快速排序的基本思想为："""两个哨兵变量，一个pivot，j--，i++，，lyst[j]<pivot停，lyst[i]>pivot停，ij相碰时将lyst[i]与pivot进行对调""""""需要把list作为一个接口参数，不然deecopy的引用参数无法传入，直接传入lyst的引用，会修改原始的lyst变量"""def quickSort(lyst,left,right):#需要加上left和right的判断，不然会超过最大迭代次数，导致栈内存溢出if left>right:returntemp=lyst[left]i,j=left,rightwhile(i<j):while (lyst[j]>=temp and i<j):j -=1while (lyst[i]<=temp and i<j):i +=1if (i<j):lyst[j],lyst[i]=lyst[i],lyst[j]lyst[i],lyst[left]=lyst[left],lyst[i]quickSort(lyst,left,i-1)quickSort(lyst,i+1,right)def print_quicksort(lyst):quickSort(lyst,0,len(lyst)-1)print("quickSort:",lyst)print_quicksort(a)print("initial list:",lyst)

归并排序

"""快排与合并排序的基础思想都是递归。对于合并排序每一次都拆成了两个子序列，直到最后两个子序列的长度均为1，"""def mergeSort(lyst):if len(lyst)==1:return lyst#取拆分的中间位置，拆分成左右两个子串mid = len(lyst)//2left=lyst[:mid]right=lyst[mid:]ll = mergeSort(left)rl = mergeSort(right)return merge(ll,rl)#每次取小数放入新开辟的列表空间#左右子序列进行比较，比较完成后会留下对应的需要加合的left和right序列def merge(left,right):res=[]while len(left)>0 and len(right)>0:if left[0] <= right[0]:res.append(left.pop(0))else:res.append(right.pop(0))res += leftres += rightreturn resprint("mergeSort:",mergeSort(lyst))

堆排序

/weixin_42348333/article/details/80991081

'''堆排序''''''1.从下至上，从右至左，对每个节点进行调整，以得到一个大顶堆''''''2.首尾互换，尾部元素已是有序序列，堆元素个数减1，此部分仍为无序序列，继续调整'''def big_endian(lyst,start,end):root = startwhile True:child = root * 2 + 1if child > end:breakif child+1 <= end and lyst[child] < lyst[child+1]:child += 1if lyst[root] < lyst[child]:lyst[root], lyst[child] = lyst[child], lyst[root]root = childelse:breakdef heap_sort(lyst):first=len(lyst) // 2 - 1for start in range (first, -1, -1):big_endian(lyst, start, len(lyst)-1)for end in range (len(lyst)-1, 0, -1):lyst[0], lyst[end] = lyst[end], lyst[0]big_endian(lyst, 0, end-1)l = [3, 1, 4, 9, 6, 7, 5, 8, 2, 10]print (l)heap_sort(l)print (l)

如果觉得《Python实现常用排序（选择 冒泡 插入 快排 合并排序 堆排序）》对你有帮助，请点赞、收藏，并留下你的观点哦！