使用swap函数来交换列表中的两项的位置
1 def swap(lyst,i,j): 2 '''交换列表中两项的位置''' 3 temp = lyst[i] 4 lyst[i] = lyst[j] 5 lyst[j] = temp
① 选择排序
处于列表第一项，先找到最小项的位置，如果该位置不是列表的第一项，算法会交换这两个位置的项，然后算法回到第二项并重复上述过程，如果第二项比最小值要大，则交换位置，当算法到列表最后的位置时，列表排序好了
1 def swap(lyst,i,j): 2 '''交换列表中两项的位置''' 3 temp = lyst[i] 4 lyst[i] = lyst[j] 5 lyst[j] = temp 6 7 def selectionSort(lyst): 8 i = 0 9 while i < len(lyst): #Do n -1 searches 10 minIndex = i #for the smallest 11 j = i + 1 12 while j < len(lyst): #start a search 13 if lyst[j] < lyst[minIndex]: 14 minIndex = j 15 j = j + 1 16 if minIndex != i: 17 swap(lyst,minIndex,i) 18 19 i += 1
② 冒泡排序
从列表得开头处开始，比较相邻两项，每当左边的比右边的时，算法就交换其位置，这样效果就将最大项以冒泡的方式排到列表末尾，然后算法从列表开头到倒数第二项重复上述过程。
1 def swap(lyst,i,j): 2 '''交换列表中两项的位置''' 3 temp = lyst[i] 4 lyst[i] = lyst[j] 5 lyst[j] = temp 6 7 def bubbleSort(lyst): 8 n = len(lyst): 9 while n > 1: #Do n-1 bubble 10 i = 1 #start each bubble 11 while i < n : 12 if lyst[i] < lyst[i-1]: #exchange if needed 13 swap(lyst,i,i-1) 14 i += 1 15 n -= 1
在最好的情况下，第一轮发生已经排序好了
1 def swap(lyst,i,j): 2 '''交换列表中两项的位置''' 3 temp = lyst[i] 4 lyst[i] = lyst[j] 5 lyst[j] = temp 6 7 def bubbleSort(lyst): 8 n = len(lyst): 9 while n > 1: #Do n-1 bubble 10 swapped = False 11 i = 1 #start each bubble 12 while i < n : 13 if lyst[i] < lyst[i-1]: #exchange if needed 14 swap(lyst,i,i-1) 15 swapped = True 16 i += 1 17 if not swapped:return #return if no swaps 18 n -= 1
③ 插入排序
类似扑克牌的顺序，如果按照顺序放好了i-1张牌，对于抓取第i张牌，将其手中的这些牌进行比较，知道找到合适的位置
第i轮之后，前i项应该是排好序的
1 def insertionSort(lyst): 2 i = 1 3 while i < len(lyst): 4 itemToInsert = lyst[i] 5 j = i - 1 6 while j >= 0: 7 if itemToInsert < lyst[j]: 8 lyst[j + 1] = lyst[j] 9 j -= 1 10 else: 11 break 12 lyst[j + 1] = itemToInsert 13 i += 1
阶段总结：
1.冒泡排序在最好情况下（列表已经排好序）性能为O(n)，在最好的情况下是O(n^2)，平均情况下性能更接近于O(n^2)
2.插入排序在最好情况下（列表有序）性能为O(n)，最坏情况下复杂度为O(n^2)，平均情况下也是O(n^2)
3.选择排序在各种情况下的排序都为O(n^2)
④ 快速排序
1.找到基准点，将大于基准点的项放在一个子列表，小于基准点的项放在一个子列表
2.对上述子列表重复上述过程
在最坏的情况下，快速排序算法的性能是O(n^2) -->>>>>每一次基准值都取第一个
一般请款修改，快速排序算法的性能是O(nlog2^n) ->>>>>>>每一次都从中间取基准值
每次递归调用都需要固定大小的内存用于栈，并且在每一次分割之后都有两次递归调用，因此在最好的情况下，内存使用是O(log2^n)，最坏的情况下，内存是O(n)
实现：
1 def swap(lyst,i,j): 2 '''交换列表中两项的位置''' 3 temp = lyst[i] 4 lyst[i] = lyst[j] 5 lyst[j] = temp 6 7 def quicksort(lyst): 8 quicksortHelper(lyst, 0, len(lyst) - 1) 9 10 def quicksortHelper(lyst, left, right): 11 if left < right: 12 pivotLocation = partition(lyst, left, right) 13 quicksortHelper(lyst, left, pivotLocation - 1) 14 quicksortHelper(lyst, pivotLocation + 1, right) 15 16 def partition(lyst, left, right): 17 # 找到基准值，并与最后一项进行交换 18 middle = (left + right) // 2 19 pivot = lyst[middle] 20 lyst[middle] = lyst[right] 21 lyst[right] = pivot 22 # 将最左边的点设置边界 23 boundary = left 24 # 将小于基准值的项移到边界的左边 25 for index in range(left,right): 26 if lyst[index] < pivot: 27 swap(lyst, index, boundary) 28 boundary += 1 29 # 将边界点与基准值点进行交换 30 swap(lyst, right, boundary) 31 return boundary 32 33 import random 34 35 def main(size=20, sort=quicksort): 36 lyst = [] 37 for count in range(size): 38 while len(lyst) < 20: 39 num = random.randint(1,size + 1) 40 if num not in lyst: 41 lyst.append(num) 42 print(lyst) 43 sort(lyst) 44 print(lyst) 45 46 if __name__ == '__main__': 47 main()
④ 合并排序
合并排序利用了递归，分而治之的策略来突破O（n^2）的障碍
1 import random 2 import array 3 4 def mergeSort(lyst): 5 copyBuffer = array.array('b') 6 mergeSortHelper(lyst, copyBuffer, 0, len(lyst) - 1) 7 8 def mergeSortHelper(lyst, copyBuffer, low, high): 9 if low < high: 10 middle = (low + high) // 2 11 mergeSortHelper(lyst, copyBuffer, low, middle) 12 mergeSortHelper(lyst, copyBuffer, middle + 1, high) 13 merge(lyst, copyBuffer, low, middle, high) 14 15 def merge(lyst, copyBuffer, low, middle, high): 16 i1 = low 17 i2 = middle + 1 18 19 for i in range(low, high + 1): 20 if i1 > middle: 21 copyBuffer[i] = lyst[i2] #first sublist exhaust 22 i2 += 1 23 elif i2 > high: 24 copyBuffer[i] = lyst[i1] #second sublist exhaust 25 i1 += 1 26 elif lyst[i1] < lyst[i2]: 27 copyBuffer[i] = lyst[i1] # item in first sublist 28 i1 += 1 29 elif lyst[i1] > lyst[i2]: 30 copyBuffer[i] = lyst[i2] #item in second sublist 31 i2 += 1 32 else: 33 pass 34 35 for i in range(low, high + 1): #copy sorted items to lyst 36 lyst[i] = copyBuffer[i] 37 38 def main(size=10, sort=mergeSort): 39 lyst = [] 40 for count in range(size): 41 while len(lyst) < 8: 42 num = random.randint(1, size + 1) 43 if num not in lyst: 44 lyst.append(num) 45 print(lyst) 46 mergeSort(lyst) 47 print(lyst) 48 49 if __name__ == '__main__': 50 main()
根据列表的大小，合并排序有两个空间需求，首先是在支持递归调用的调用栈上需要O(log2^n)，其次在复制缓存需要使用O(n)的空间
因此合并排序算法的复杂度为O(nlog2^n)