python3怎么实现常见的排序算法(python,移动开发)

冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

defmao(lst):foriinrange(len(lst)):#由于每一轮结束后，总一定有一个大的数排在后面#而且后面的数已经排好了#即i轮之后，就有i个数字被排好#所以其len-1-i到len-1的位置是已经排好的了#只需要比较0到len-1-i的位置即可#flag用于标记是否刚开始就是排好的数据#只有当flag状态发生改变时（第一次循环就可以确定），继续排序，否则返回flag=Falseforjinrange(len(lst)-i-1):iflst[j]>lst[j+1]:lst[j],lst[j+1]=lst[j+1],lst[j]flag=True#非排好的数据，改变flagifnotflag:returnlstreturnlstprint(mao([1,5,55,4,5,1,3,4,5,8,62,7]))

选择排序

选择排序是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

#选择排序是从前开始排的#选择排序是从一个列表中找出一个最小的元素，然后放在第一位上。#冒泡排序类似#其0到i的位置是排好的，只需要排i+1到len(lst)-1即可defselect_sort(lst):foriinrange(len(lst)):min_index=i#用于记录最小的元素的索引forjinrange(i+1,len(lst)):iflst[j]<lst[min_index]:min_index=j#此时，已经确定，min_index为i+1到len(lst)-1这个区间最小值的索引lst[i],lst[min_index]=lst[min_index],lst[i]returnlstdefselect_sort2(lst):#第二种选择排序的方法#原理与第一种一样#不过不需要引用中间变量min_index#只需要找到索引i后面的i+1到len(lst)的元素即可foriinrange(len(lst)):forjinrange(len(lst)-i):#lst[i+j]是一个i到len(lst)-1的一个数#因为j<=len(lst)-i即j+i<=len(lst)iflst[i]>lst[i+j]:#说明后面的数更小，更换位置lst[i],lst[i+j]=lst[i+j],lst[i]returnlstprint(select_sort([1,5,55,4,5,1,3,4,5,8,62,7]))print(select_sort2([1,5,55,4,5,1,3,4,5,8,62,7]))

快速排序

快速排序是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

#原理#1.任取列表中的一个元素i#2.把列表中大于i的元素放于其右边，小于则放于其左边#3.如此重复#4.直到不能在分，即只剩1个元素了#5.然后将这些结果组合起来defquicksort(lst):iflen(lst)<2:#lst有可能为空returnlst#["pɪvət]中心点pivot=lst[0]less_lst=[iforiinlst[1:]ifi<=pivot]greater_lst=[iforiinlst[1:]ifi>pivot]#最后的结果就是#左边的结果+中间值+右边的结果#然后细分左+中+右+中间值+左+中+右#...........+中间值+............returnquicksort(less_lst)+[pivot]+quicksort(greater_lst)print(quicksort([1,5,55,4,5,1,3,4,5,8,62,7]))print(quicksort([1,5,8,62]))

插入排序

插入排序的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

#lst的[0,i)项是有序的，因为已经排过了#那么只需要比对第i项的lst[i]和lst[0:i]的元素大小即可#假如，lst[i]大，则不用改变位置#否则，lst[i]改变位置，插到j的位置，而lst[j]自然往后挪一位#然后再删除lst[i+1]即可（lst[i+1]是原来的lst[i]）##重复上面步骤即可，排序完成definsert_sort(lst:list):#外层开始的位置从1开始，因为从0开始都没得排#只有两个元素以上才能排序foriinrange(1,len(lst)):#内层需要从0开始，因为lst[0]的位置不一定是最小的forjinrange(i):iflst[i]<lst[j]:lst.insert(j,lst[i])#lst[i]已经插入到j的位置了，j之后的元素都往后+1位，所以删除lst[i+1]dellst[i+1]returnlstprint(insert_sort([1,5,55,4,5,1,3,4,5,8,62,7]))

希尔排序

希尔排序是1959年Shell发明的，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

希尔排序

#希尔排序是对直接插入排序的优化版本#1.分组：#每间隔一段距离取一个元素为一组#间隔自己确定，一般为lst的一半#2.根据插入排序，把每一组排序好#3.继续分组：#同样没间隔一段距离取一个元素为一组#间隔要求比之前的间隔少一半#4.再每组插入排序#5.直到间隔为1，则排序完成#defshell_sort(lst):lst_len=len(lst)gap=lst_len//2#整除2，取间隔whilegap>=1:#间隔为0时结束foriinrange(gap,lst_len):temp=lst[i]j=i#插入排序whilej-gap>=0andlst[j-gap]>temp:lst[j]=lst[j-gap]j-=gaplst[j]=tempgap//=2returnlstprint(shell_sort([1,5,55,4,5,1,3,4,5,8,62,7]))#奇数#gap=2#[5,2,4,3,1]#[5,4,1][2,3]#[1,4,5,2,3]#gap=1#[1,2,3,4,5]#偶数#gap=3#[5,2,4,3,1，6]#[5,3][2,1][4,6]#[3,5,1,2,4,6]#gap=1#[1,2,3,4,5,6]

并归排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

并归排序

#利用分治法#不断将lst分为左右两个分#直到不能再分#然后返回#将两边的列表的元素进行比对，排序然后返回#不断重复上面这一步骤#直到排序完成，即两个大的列表比对完成defmerge(left,right):#left可能为只有一个元素的列表，或已经排好序的多个元素列表（之前调用过merge）#right也一样res=[]whileleftandright:item=left.pop(0)ifleft[0]<right[0]elseright.pop(0)res.append(item)#此时，left或right已经有一个为空，直接extend插入#而且，left和right是之前已经排好序的列表，不需要再操作了res.extend(left)res.extend(right)returnresdefmerge_sort(lst):lst_len=len(lst)iflst_len<=1:returnlstmid=lst_len//2lst_right=merge_sort(lst[mid:len(lst)])#返回的时lst_len<=1时的lst或merge中进行排序后的列表lst_left=merge_sort(lst[:mid])#返回的是lst_len<=1时的lst或merge中进行排序后的列表returnmerge(lst_left,lst_right)#进行排序，lst_leftlst_right的元素会不断增加print(merge_sort([1,5,55,4,5,1,3,4,5,8,62,7]))

堆排序

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。然后进行排序。

堆排序

#把列表创成一个大根堆或小根堆#然后根据大（小）根堆的特点：根节点最大（小），逐一取值##升序----使用大顶堆##降序----使用小顶堆#本例以小根堆为例#列表lst=[1,22,11,8,12,4,9]#1.建成一个普通的堆：#1#/#2211#//#81249##2.进行调整，从子开始调整位置，要求：父节点<=字节点##111#/13和22调换位置/4和11调换位置/#2211==============>1311==============>134#//////#1314492214492214119##3.取出树上根节点，即最小值，把换上叶子节点的最大值##1#/#~~~~/#22#/#84#/#12119##4.按照同样的道理，继续形成小根堆，然后取出根节点，。。。。重复这个过程##111414148148#//////#~~~/~~~/~~~/~~~/~~~/~~~/#224228229#//////#8489891291291211#//////#12119121122121122111122##续上：#1489148914891114891114891112==>1489111222#/////#~~~/~~~/~~~/~~~/~~~/#2211221222#////#121112221222##代码实现defheapify(lst,lst_len,i):"""创建一个堆"""less=i#largest为最大元素的索引left_node_index=2*i+1#左子节点索引right_node_index=2*i+2#右子节点索引#lst[i]就是父节点(假如有子节点的话)：##lst[i]#/#lst[2*i+1]lst[2*i+2]##想要大根堆，即升序，将判断左右子节点大小的‘>"改为‘<"即可#ifleft_node_index<lst_lenandlst[less]>lst[left_node_index]:less=left_node_indexifright_node_index<lst_lenandlst[less]>lst[right_node_index]:#右边节点最小的时候less=right_node_indexifless!=i:#此时，是字节点大于父节点，所以相互交换位置lst[i],lst[less]=lst[less],lst[i]#交换heapify(lst,lst_len,less)#节点变动了，需要再检查一下defheap_sort(lst):res=[]i=len(lst)lst_len=len(lst)foriinrange(lst_len,-1,-1):#要从叶节点开始比较，所以倒着来heapify(lst,lst_len,i)#此时，已经建好了一个小根树#所以，交换元素，将根节点（最小值）放在后面，重复这个过程forjinrange(lst_len-1,0,-1):lst[0],lst[j]=lst[j],lst[0]#交换，最小的放在j的位置heapify(lst,j,0)#再次构建一个[0:j)小根堆[j:lst_len-1]已经倒序排好了returnlstarr=[1,5,55,4,5,1,3,4,5,8,62,7]print(heap_sort(arr))