经常忘，每次都要从网上查一下，每次查的都不一样，还是记录一下吧
1、选择排序
从一堆数中选择最小的，往前放
def selectSort(arr): for i in range(len(arr)-1): key = i for j in range(i+1,len(arr)): if(arr[j] < arr[key]): key = j if key != i: arr[key],arr[i] = arr[i],arr[key] return arr
2、冒泡排序
最小的浮起来，放到最后；重点：相邻元素比较，交换
def bubSort(arr): for i in range(len(arr)-1): for j in range(1,len(arr)-i): if arr[j-1] > arr[j]: arr[j-1],arr[j] = arr[j],arr[j-1] return arr
3、插入排序
后面的数据按照顺序往前插入
def insertSort(arr): for i in range(1,len(arr)): temp = arr[i] j = i - 1 while (j >= 0 and arr[j] > temp): arr[j + 1] = arr[j] j -= 1 arr[j + 1] = temp return arr
4、快速排序（面试重点）
找一个基准值，二分，比它大的放后面，比它小的放前面，重复多次，直到不能二分为止
def partition(arr,left,right): pivot = arr[left] i = left + 1 j = right while(1): while i <= j and arr[i] <= pivot: i += 1 while i <= j and arr[j] >= pivot: j -= 1 if (i >= j): break arr[i],arr[j] = arr[j],arr[i] arr[left] = arr[j] arr[j] = pivot return j def quickSort(arr,left,right): if left < right: mid = partition(arr,left,right) arr = quickSort(arr,left,mid - 1) arr = quickSort(arr,mid + 1,right) return arr
5、归并排序（面试重点）
先切，切到一个数为一组，再合并，合并过程按大小排序
def mergeSort(arr): if len(arr) < 2: return arr mid = len(arr) // 2 left = mergeSort(arr[:mid]) right = mergeSort(arr[mid:]) return merge(left,right) def merge(a,b): c = [] i = j = 0 while i < len(a) and j < len(b): if a[i] < b[j]: c.append(a[i]) i += 1 else: c.append(b[j]) j += 1 c.extend(a[i:]) c.extend(b[j:]) return c print(mergeSort(arr))
原文：https://www.cnblogs.com/zrdm/p/12929014.html