常见6种排序算法的python实现.doc

常用排序算法的Python实现相关代码如下（直接拷贝就可以用了）：import randomimport math冒泡排序多次比较相邻的两个元素若第一个比第二个大则交换持续进行比较直到没有需要交换的元素为止def bubbleSort(num):length = len(num)while length 0:for i in range(length-1):if numi numi+1:numi,numi+1 = numi+1,numilength = length - 1passprint(num)return num选择排序每一次从待排序的数据元素中选出最小（或最大）的一个元素存放在序列的起始位置直到全部待排序的数据元素排完def selectSort(num):length = len(num)for i in range(length):tmpNum = ifor j in range(i,length):if numtmpNum numj:numtmpNum,numj = numj,numtmpNumprint(num)return num插入排序将一个数据插入到已经排好序的有序数据中从而得到一个新的、个数加一的有序数据实现方法一def insertSort(num):length = len(num)for i in range(1,length):tmp = numifor j in range(i,-1,-1):if numj tmp:numj+1,numj = numj,numj+1print(num)return num实现方法二def insertSort2(num):length = len(num)for i in range(1,length):tmp = numitmpi = i -1while tmpi = 0 and numtmpi tmp:numtmpi,numtmpi+1 = numtmpi+1,numtmpitmpi = tmpi - 1passprint(num)return num快速排序通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序def quickSort(num):length = len(num)if length tmp:right.append(numi)else:left.append(numi)return quickSort(left) + quickSort(right) 归并排序归并排序采用的分治法，将有序的序列合成一个序列，反之，将当前序列分成多个序列分别排序，依此方法类推，直到序列中只有一个元素为止，常用的归并排序为二路归并，即分成两个序列def mergerSort(num):result = length = len(num)if length 0 and len(right) 0:if left0 0:result.extend(left)else:result.extend(right)return result堆排序堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。主要的过程分为建立堆、堆调整和堆排序。建立堆：建堆是不断调整堆的过程，从len/2处开始调整，一直到第一个节点，此处len是堆中元素的个数。def createHeap(num):length = len(num)flag = 1for i in range(math.floor(length/2)-1,-1,-1):if num2*i+2 numi and num2*i+2 num2*i+1:num2*i+2,numi = numi,num2*i+2num = handHeap(num,2*i+2)else:if num2*i+1 numi and num2*i+1 num2*i+2:num2*i+1,numi = numi,num2*i+1num = handHeap(num,2*i+1)else:numi = numireturn num调整堆：利用的思想是比较节点i和它的孩子节点left(i),right(i)，选出三者最大(或者最小)者，如果最大（小）值不是节点i而是它的一个孩子节点，那边交互节点i和该节点，然后再调用调整堆过程，这是一个递归的过程。def handHeap(num,head):temp = 2*head + 1tempHead = headlength = len(num)while temp length:if numtempHead numtemp:numtempHead,numtemp = numtemp,numtempHeadif temp+1 length and numtempHead numtemp+1 :numtempHead,numtemp+1 = numtemp+1,numtempHeadtempHead = temptemp = tempHead*2+1return num堆排序：堆排序是利用上面的两个过程来进行的。首先是根据元素构建堆。然后将堆的根节点取出(一般是与最后一个节点进行交换)，将前面len-1个节点继续进行堆调整的过程，然后再将根节点取出，这样一直到所有节点都取出。def headSort(num):length = len(num)if length 0:numtempLength,num0 = num0,numtempLengthnum:tempLength = handHeap(num:tempLength,0)tem