内部排序

0.准备测试数据

import random def createL(n): #生成打乱序列 L = list(range(n)) random.shuffle(L) return L def swap(List, i, j): #传引用参数 List[i], List[j] = List[j], List[i]

1.选择排序

每次都在未排序部分选择最小的项跟这部分的第一项交换

def selectionSort(L): for i in range(len(L)-1): minIndex = i for j in range(i+1,len(L)): if L[minIndex] > L[j]: minIndex = j if minIndex != i: swap(L,i,minIndex)

2.插入排序

每次选择未排序部分的第一项，跟其前面已排序部分逐个比较，插入到保持已排序部分有序的位置

def insertionSort(L): for i in range(1,len(L)): for j in list(range(i,0,-1)): if L[j] < L[j-1]: swap(L, j-1, j) else: break

3.冒泡排序

每次比较相邻的两项，如果逆序，交换之，每轮能使一项“沉底”

def bubbleSort(L): for i in range(len(L)-1): flag = False #标记flag用来判断是否已经排序完成，提前停止排序 for j in range(1,len(L)-i): if L[j-1] > L[j]: swap(L, j-1, j) flag = True if not flag: return

4.快速排序

采用分而治之策略，每次将问题划分为两个子问题 保证基准点左边小于它，右边是大于它，分成两个子序列，子序列再进行划分，知道无法再分

def quickSort(L, left, right): if left < right: pivotIndex = getPivot(L, left, right) quickSort(L, left, pivotIndex-1) quickSort(L, pivotIndex+1, right) def getPivot(L, left, right): #进行一次快速排序，同时返回基准点的位置 index = (left+right)//2 pivot = L[index] swap(L, left, index) index = left for i in range(left+1,right+1): if L[i] < pivot: if i > index+1: swap(L, index+1, i) swap(L, index, index+1) index += 1 return index

5.归并排序

也是分而治之，不过是从下而上的，将短的有序序列合成长的有序序列

def mergeSort(L, copyL, left, right): if left < right: middle = (left + right)//2 mergeSort(L, copyL, left, middle) mergeSort(L, copyL, middle+1, right) merge(L, copyL, left, right, middle) print(cL) def merge(L, copyL, left, right, middle): i = left j = middle+1 k = left while i<=middle and j<=right: if L[i]<=L[j]: copyL[k] = L[i] i += 1 else: copyL[k] = L[j] j += 1 k += 1 if i <= middle: copyL[k:right+1] = L[i:middle+1] if j <= right: copyL[k:right+1] = L[j:right+1] L[left:right+1] = copyL[left:right+1]

注：代码不难看懂就不写注释了，主要需要理解排序的策略