一系列巩固一个知识点——python实现十大排序算法

写在前面排序和搜索是算法中最重要的两个概念，我们大多数情况下都是搜索和排序。科学家们竭尽全力加快分类和搜索速度。本文使用Python实现十大排序算法。干货排序算法从不同的维度可以分为很多类。从其排序思路（排序思路一般决定其时间复杂度的大小）来看，主要分为四类：双层循环比较排序：方级排序分治策略比较排序：对数排序是非比较排序的另一种方式：线性水平排序另一种笑话人命的排序：它具有不受约束的时间复杂度，难以描述。方块级排序冒泡排序从数组的第一个元素开始，比较当前元素和下一个元素，如果当前元素大于下一个元素，则交换两个元素的位置。然后从第二个元素开始，重复第一步，直到当前元素为最后一个元素。此时最后一个元素是最大的元素。未排序的数组包含除最后一个元素以外的元素。对未排序数组重复上述步骤，直到未排序数组为空。defbubble_sort(arr):length=len(arr)foriinrange(length):forjinrange(length-i-1):ifarr[j]>arr[j+1]:arr[j],arr[j+1]=arr[j+1],arr[j]returnarrselectionandsorting选择数组中的最小元素，与数组中的第一个元素交换位置，选择数组中除第一个元素之外的其余元素第一个元素的最小元素，与数组中的第二个元素交换位置。重复以上步骤，直到当前选中的元素是数组中的最后一个元素。defselect_sort(arr):length=len(arr)foriinrange(length):min_ix=iforjinrange(i,length):ifarr[j]0:foriinrange(gap,n):temp=arr[i]j=iwhilej>=gapandarr[j-gap]>temp:arr[j]=arr[j-gap]j-=gaparr[j]=tempgap=int(gap/2)返回arr合并排序以中间元素为界数组，并将数组分成两个等长的数组（也可以不等长，与数组长度的奇偶性有关）。对所有数组执行步骤1，重复上述步骤，直到数组被拆分为多个包含单个元素的数组。将上述数组成对合并并排序。这时候有多个数组包含有序的两个元素（可能包含单个元素，这与数组长度的奇偶性有关）。重复步骤4，直到所有数组合并为一个数组defmerge(left,right):i=j=0res=[]whileipivot]returnfast_sort(left)+[pivot]+fast_sort(right)上述算法需要额外的空间，如果我们保持小于或等于pivot的元素放在pivot元素之前，将大于pivot的元素放在pivot元素中，就可以实现不需要额外空间的原地排序。deffast_sort_on_extra_spacing(arr):l=0h=len(arr)-1defpartition(arr,l,h):pivot=arr[h]foriinrange(l,h):ifarr[i]<=pivot:arr[l],arr[i]=arr[i],arr[l]l+=1arr[h],arr[l]=arr[l],arr[h]返回ldeffast_sort(arr,l,h):如果l