def bubbleSort(myList): # 冒泡算法的反向递减 length = len(myList) for i in range(length - 1, 0, -1): # 冒泡是从最底下往上冒,越往后比的越少 tag = False # 打个标记False，判断有没有哪一次不需要交换值 for j in range(i): if myList[j] > myList[j+1]: myList[j], myList[j+1] = myList[j+1], myList[j] tag = True # 如果交换了值，就将标记打为True if not tag: # 如果存在一次不用交换位置，后面就不用循环了，肯定是有序的 break test_list = [8,9, 0, 1, 2, 3, 4] bubbleSort(test_list) print(test_list)
def insertSort(myList): for i in range(len(myList)): currentValue = myList[i] # 将要排序的值取出来，留个空位 pointer = i # 指针指向该空位 while pointer > 0 and myList[pointer - 1] > currentValue: #当前值与指正前的位置比较 myList[pointer] = myList[pointer - 1] # 大的值右移，腾出空格 pointer = pointer - 1 # 指针指向空格 myList[pointer] = currentValue # 将插入值放到指针的位置 test_list = [8, 7, 9, 5, 4, 3, 8, 2, 6, 1, 0] insertSort(test_list) print(test_list)
def mergeSort(myList): if len(myList) == 1: # 递归的终止条件，长度为1，不可再分 return myList mid = len(myList) // 2 left = mergeSort(myList[:mid]) # 左半部分 right = mergeSort(myList[mid:]) # 右半部分，奇数情况时，右多一个 # 接下来是merge的主要部分（合并） sortList = [] # 开辟一个新的内存地址 while left and right: if left[0] < right[0]: sortList.append(left.pop(0)) # 列表的扩充，不可以直接赋值，必须使用append或者extend else: sortList.append(right.pop(0)) # 列表的扩充，不可以直接赋值，必须使用append或者extend ''' sortList[count] = ss # 列表的扩充，不可以直接赋值，必须使用append或者extend count += 1 ''' sortList.extend(left if left else right) return sortList test_list = [8, 7, 9, 5, 4, 3, 2, 6, 1, 0] a = mergeSort(test_list) print(a)
# 快速排序 递归加找中值 def quickSort(myList): helpSort(myList, 0, len(myList) - 1) # 传列表和起始位置的下标 def helpSort(myList, first, last): if first < last: mid = partition(myList, first, last) helpSort(myList, first, mid - 1) helpSort(myList, mid + 1, last) def partition(myList, left, right): # 划分函数 midValue = myList[left] leftPointer = left + 1 # 这里加1 是因为将第一个元素设置为中值。 rightPointer = right tag = False while not tag: while leftPointer <= rightPointer and myList[leftPointer] <= midValue: # 左指针的操作 leftPointer += 1 while leftPointer <= rightPointer and myList[rightPointer] >= midValue: # 右指正的操作 rightPointer -= 1 if leftPointer > rightPointer: # 终止条件一定是左指针在右指针的右边 tag = True else: myList[leftPointer], myList[rightPointer] = myList[rightPointer], myList[leftPointer] # 交换左右的值 # 此时，左指正在右指针的右边 myList[left], myList[rightPointer] = myList[rightPointer], myList[left] return rightPointer # 这里是右指针的位置(下标) test_list = [8, 7, 9, 5, 4, 3, 8, 8, 2, 6, 1, 0] quickSort(test_list) print(test_list)
def selectSort(myList): for i in range(len(myList) - 1, 0, -1): maxpointer = 0 for j in range(i): if myList[j] > myList[maxpointer]: maxpointer = j myList[i], myList[maxpointer] = myList[maxpointer], myList[i] # 每次只做一次调换 test_list = [8, 9, 0, 1, 2, 3, 4] selectSort(test_list) print(test_list)
def shellSort(myList): # 希尔排序是基于插入排序衍生的 length = len(myList) step = length // 2 while step: for i in range(step): # 步长是几，就会产生几个子列表，这里是在循环子列表 insertSort(myList, i, step, length) # 调用排序算法 step = step // 2 def insertSort(myList, start, step, length): for j in range(start + step, length, step): # 起步是子列表的第2个数,(start是第一个数) currentValue = myList[j] position = j # position是定位最小值的 while position >0 and currentValue < myList[position - step]: # 移动position指针位置的条件 myList[position] = myList[position - step] position = position - step myList[position] = currentValue test_list = [8,7,9,5,4,3,2,6,1,0] shellSort(test_list) print(test_list)