手机网站关于我们,汕头网页设计公司,宜昌优化网站建设,泰安建网站目录
一、冒泡排序
二、选择排序 三、插入排序
四、希尔排序
五、归并排序
六、快速排序 排序是指将集合中的元素按照某种顺序排序的过程。
一、冒泡排序
冒泡排序多次遍历列表。它比较相邻的元素#xff0c;将不合顺序的交换。每一轮遍历都将下一个最大值放到正确的位…目录
一、冒泡排序
二、选择排序 三、插入排序
四、希尔排序
五、归并排序
六、快速排序 排序是指将集合中的元素按照某种顺序排序的过程。
一、冒泡排序
冒泡排序多次遍历列表。它比较相邻的元素将不合顺序的交换。每一轮遍历都将下一个最大值放到正确的位置上。本质上每个元素通过“冒泡”找到自己所属的位置。
冒泡排序需要遍历的轮数是n-1完成n-1轮后最小的元素必然在正确的位置上因此不必再做处理。
冒泡排序函数bubbleSort
def bubbleSort(alist):for passnum in range(len(alist)-1,0,-1):for i in range(passnum):if alist[i]alist[i1]:tempalist[i]alist[i]alist[i1]alist[i1]temp
Python允许同时赋值执行语句a,bb,a相当于同时执行两条赋值语句。
冒泡排序算法中给含有n个元素的列表排序总需要遍历n-1轮总的比较次数是前n-1个整数之和因此前n-1个整数之和就是。这表明该算法的时间复杂度是。在最好的情况下列表是已经有序的不需要执行交换操作。在最坏情况下每一次比较都将导致一次交换。
冒泡排序通常被认为是效率最低的排序算法因为在确定最终的位置前必须交换元素。“多余”的交换操作代价很大。不过由于冒泡排序要遍历列表中未排序的部分因此它具有其他排序算法没有的用途。特别是如果在一轮遍历中没有发生元素交换就可以确定列表已经有序。可以修改冒泡排序函数使其在遇到这种情况时提前终止。对于只需要遍历几次的列表冒泡排序可能有优势因此它能判断出有序列表并终止排序过程。这种排序通常被称为短冒泡。
修改后的冒泡排序函数
def shortBubbleSort(alist):exchangesTruepassnumlen(alist)-1while passnum0 and exchanges:exchangesFalsefor i in range(passnum):if alist[i]alist[i1]:exchangesTruetempalist[i]alist[i]alist[i1]alist[i1]temppassnumpassnum-1
二、选择排序
选择排序在冒泡排序的基础上做了改进每次遍历列表时只做一次交换。要实现这一点选择排序在每次遍历时寻找最大值并在遍历完之后将它放到正确位置上。和冒泡排序一样第一次遍历后最大的元素就位第二次遍历后第二大的元素就位依此类推。若给n个元素排序需要遍历n-1轮。
选择排序函数selectionSort
def selectionSort(alist):for fillslot in range(len(alist)-1,0,-1):positionOfMax0for location in range(1,fillslot1):if alist[location]alist[positionOfMax]:positionOfMaxlocationtempalist[fillslot]alist[fillslot]alist[positionOfMax]alist[positionOfMax]temp
可以看出选择排序算法和冒泡排序算法的比较次数相同所以时间复杂度也是。但是由于减少了交换次数因此选择排序算法通常更快。 三、插入排序
插入排序的时间复杂度也是但原理稍有不同。它在列表较低的一端维护一个有序的子列表并逐个将每个新元素“插入”这个子列表。
首先假设位置0处的元素是只含单个元素的有序子列表。从元素1到元素n-1每一轮都将当前元素与有序子列表中的元素进行比较。在有序子列表中将比它大的元素右移当遇到一个比他小的元素或抵达子列表终点时就可以插入当前元素。
在给n个元素排序时插入排序算法需要遍历n-1轮。循环从位置1开始直到位置n-1结束这些元素都需要被插入到有序子列表中。
插入排序函数insertionSort
def insertionSort(alist):for index in range(1,len(alist)):currentvaluealist[index]positionindexwhile position0 and alist[position-1]currentvalue:alist[position]alist[position-1]positionposition-1alist[position]currentvalue 在最坏的情况下插入排序算法的比较次数是前n-1个整数之和对应的时间复杂度是。在最好的情况下列表已经是有序的每一轮只需比较一次。
移动操作和交换操作有一个重要的不同点。总体来说交换操作的处理时间大约是移动操作的3倍因为后者只需进行一次赋值。在基准测试中插入排序算法的性能很不错。
四、希尔排序
希尔排序也称“递减增量排序”它对插入排序做了改进将列表分成数个子列表并对每一个列表应用插入排序。如何切分列表是希尔排序的关键——并不是连续切分而是使用增量i有时称作步长选取所有间隔为i的元素组成子列表。
希尔排序函数shellSort
def shellSort(alist):sublistcountlen(alist)//2while sublistcount0:for startposition in range(sublistcount):gapInsertionSort(alist,startposition,sublistcount)print(After increments of size,sublistcount,The list is,alist)sublistcountsublistcount//2def gapInsertionSort(alist,start,gap):for i in range(startgap,len(alist),gap):currentvaluealist[i]positioniwhile positiongap and alist[position-gap]currentvalue:alist[position]alist[position-gap]positionposition-gapalist[position]currentvalueif __name____main__:alist[54,26,93,17,77,31,44,55,20]print(shellSort(alist)) 希尔排序的时间复杂度大概介于和之间。希尔排序的时间复杂度可以达到。
五、归并排序
归并排序是递归算法使用了分治策略每次将一个列表一分为二如果列表为空或只有一个元素那么从定义上来说它就是有序的基本情况。如果列表不止一个元素就将列表一分为二并对两部分都递归调用并归并排序。当两部分都有序后就进行归并这一基本操作。归并是指将两个较小的有序列表归并为一个有序列表的过程。
归并排序函数mergeSort
def mergeSort(alist):print(Spiltting ,alist)if len(alist)1:midlen(alist)//2lefthalfalist[:mid]rightleftalist[mid:]mergeSort(lefthalf)mergeSort(rightleft)i0j0k0while ilen(lefthalf) and jlen(rightleft):if lefthalf[i]rightleft[j]:alist[k]lefthalf[i]ii1else:alist[k]rightleft[j]jj1kk1while ilen(lefthalf):alist[k]lefthalf[i]ii1kk1while jlen(rightleft):alist[k]rightleft[j]jj1kk1print(Merging ,alist)if __name____main__:b[54,26,93,17,77,31,44,55,20]print(mergeSort(b)) 运行结果如下
Spiltting [54, 26, 93, 17, 77, 31, 44, 55, 20]
Spiltting [54, 26, 93, 17]
Spiltting [54, 26]
Spiltting [54]
Merging [54]
Spiltting [26]
Merging [26]
Merging [26, 54]
Spiltting [93, 17]
Spiltting [93]
Merging [93]
Spiltting [17]
Merging [17]
Merging [17, 93]
Merging [17, 26, 54, 93]
Spiltting [77, 31, 44, 55, 20]
Spiltting [77, 31]
Spiltting [77]
Merging [77]
Spiltting [31]
Merging [31]
Merging [31, 77]
Spiltting [44, 55, 20]
Spiltting [44]
Merging [44]
Spiltting [55, 20]
Spiltting [55]
Merging [55]
Spiltting [20]
Merging [20]
Merging [20, 55]
Merging [20, 44, 55]
Merging [20, 31, 44, 55, 77]
Merging [17, 20, 26, 31, 44, 54, 55, 77, 93]
None归并操作每次从有序列表中取出最小值放回初始列表。
归并排序算法的时间复杂度是。
六、快速排序
和归并排序一样快速排序也采用分治策略但不使用额外的存储空间。不过代价是列表可能不会被一分为二。出现这种情况算法的效率会有所下降。
快速排序算法首先选出一个基准值。基准值的作用是帮助切分列表。在最终的有序列表中基准值的位置通常被称作分割点算法在分割点切分列表以继续对快速排序的子调用。
找到基准值后下一步是分区操作。它会找到分割点同时将其他元素放到正确的一边——要么大于基准值要么小于基准值。
分区操作首先找到两个坐标——leftmark和rightmark——它们分别位于列表剩余元素的开头和结尾。分区的目的是根据排序元素与基准值的相对大小将它们放到正确的一边同时逐渐逼近分割点。
首先加大leftmark直到遇到一个大于基准值的元素。然后减小rightmark直到遇到一个小于基准值的元素。这样一来就找到两个与最终的分割点错序的元素。互换这两个元素然后重复上述过程。
当rightmark小于leftmark时过程终止。此时rightmark的位置就是分割点。将基准值与当前位于分割点的元素互换即可使基准值位于正确的位置。分割点左边的所有元素都小于基准值右边的所有元素都大于基准值。因此可以在分割点处将列表一分为二并针对左右两部分递归调用快速排序函数。
快速排序函数quickSort
def quickSort(alist):quickSortHelper(alist,0,len(alist)-1)def quickSortHelper(alist,first,last):if firstlast:splitpointpartition(alist,first,last)quickSortHelper(alist,first,splitpoint-1)quickSortHelper(alist,splitpoint1,last)def partition(alist,first,last):pivotvaluealist[first]leftmarkfirst1rightmarklastdoneFalsewhile not done:while leftmarkrightmark and alist[leftmark]pivotvalue:leftmarkleftmark1while alist[rightmark]pivotvalue and rightmarkleftmark:rightmarkrightmark-1if rightmarkleftmark:doneTrueelse:tempalist[leftmark]alist[leftmark]alist[rightmark]alist[rightmark]temptempalist[first]alist[first]alist[rightmark]alist[rightmark]tempreturn rightmark
快速排序的时间复杂度是。另外快速排序算法不需要像归并排序算法那样使用额外的存储空间。
