「2019Python开发者日」全日程揭晓，请扫码咨询↑↑↑
0.导语
本节为手撕代码系列之第一弹，主要来手撕排序算法，主要包括以下几大排序算法：
1.直接插入排序
【算法思想】
每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。
【代码实现】
#直接插入排序definsert_sort(arr):length=len(arr)foriinrange(length):k=iforjinrange(k,0,-1):ifarr[j] 2.冒泡排序 对相邻的元素进行两两比较，顺序相反则进行交换，这样，每一趟会将最小或最大的元素“浮”到顶端，最终达到完全有序。 #冒泡排序defbubbleSort(arr):length=len(arr)foriinrange(length-1):flag=Trueforjinrange(length-i-1):ifarr[j]>arr[j+1]:t=arr[j]arr[j]=arr[j+1]arr[j+1]=tflag=Falseifflag:breakarr=[6,-2,0,9]bubbleSort(arr)print(arr) 每一趟从待排序的数据元素中选择最小（或最大）的一个元素作为首元素，直到所有元素排完为止，简单选择排序是不稳定排序。 defselectSort(arr):length=len(arr)foriinrange(length-1):min=iforjinrange(i+1,length):ifarr[min]>arr[j]:min=jifmin!=i:t=arr[i]arr[i]=arr[min]arr[min]=tarr=[6,-2,0,9]selectSort(arr)print(arr) 4.快速排序 快速排序思想----分治法。 每次划分得到，枢椎的左边比它小，右边比它大。 defquickSort(arr,left,right):#递归终止条件ifleft>right:returnpivot=arr[left]i=leftj=rightwhilei 5.希尔排序 该算法也被称为：缩小增量排序。 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。 #希尔排序defshellSort(arr):length=len(arr)#设置初始增量gap=length//2whilegap>0:#从第gap个元素，逐个对其所在组进行直接插入排序foriinrange(gap,length):j=iwhilej-gap>=0andarr[j] 6.堆排序 堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。 基本思路： a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆; b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;(升序方法) c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。 classHeapSort:defheapSort(self,nums):length=len(nums)#从后往前遍历，交换堆顶与最后叶子节点，并依次调整堆，重复操作forjinrange(length-1,0,-1):#获取堆顶元素(获取同时，调整堆)firstNum=self.adjustHeap(nums,j+1)#交换最后一个叶子节点与堆顶元素temp=nums[j]nums[j]=firstNumnums[0]=tempreturnnums#调整堆(最大堆)，每次返回最大堆顶元素defadjustHeap(self,nums,length):#最后一个非叶节点i=length//2-1#从最后一个非叶节点开始调整，构成最大堆whilei>=0:temp=nums[i]k=2*i+1whilek 7.归并排序 归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。 defmergeSort(nums):iflen(nums)<=1:returnnumsmid=len(nums)//2left=mergeSort(nums[:mid])right=mergeSort(nums[mid:])returnmerge(left,right)defmerge(left,right):result=[]i,j=0,0whilei