线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。
排序复杂度 类别 名称 时间复杂度 稳定性插入排序 插入排序（insertion sort） O(n2) 稳定
插入排序 希尔排序 （shell sort） O(nlogn) 不稳定
选择排序 选择排序（selection sort） O(n2) 不稳定
选择排序 堆排序 （heapsort） O(nlogn) 不稳定
交换排序 冒泡排序（bubble sort） O(n2) 稳定
交换排序 快速排序（quicksort） O(nlogn) 不稳定
归并排序 归并排序 （merge sort） O(nlogn) 稳定
基数排序 基数排序（radix sort） O(n+k) 稳定
冒泡排序
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。
def bubbleSort(nums): for i in range(len(nums) - 1): for j in range(len(nums) - i - 1): if nums[j] > nums[j + 1]: nums[j], nums[j + 1] = nums[j + 1], nums[j] return nums nums = [2, 1, 34, 4, 6, 3, 6] result = bubbleSort(nums) print(result) [1, 2, 3, 4, 6, 6, 34] 选择排序每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，
然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 def selectSort(nums): for i in range(len(nums) - 1): index = i for j in range(i + 1, len(nums)): if nums[j] < nums[index]: index = j if index != i: nums[i], nums[index] = nums[index], nums[i] return nums nums = [2, 1, 34, 4, 6, 3, 6] result = selectSort(nums) print(result) [1, 2, 3, 4, 6, 6, 34] 插入排序每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
时间复杂度：O（n^2）.
def insertSort1(nums): for i in range(1, len(nums)): index = nums[i] j = i - 1 while j >= 0 and nums[j] > index: nums[j+1] = nums[j] j-=1 nums[j+1] = index return nums nums = [2, 4, 1 ,0, 4, 3, 2, 5] result = insertSort1(nums) print(result) [0, 1, 2, 2, 3, 4, 4, 5]下面方法会遍历到nums[-1]，如果nums[-1] > index则进行交换，但是循环结束，nums[0]仍会赋值为index
def insertSort(nums): for i in range(1, len(nums)): index = nums[i] for j in range(i, -1, -1): if index < nums[j - 1]: #该方法会遍历到nums[-1]，如果nums[-1] > index则进行交换，但是循环结束，nums[0]仍会赋值为index nums[j]= nums[j - 1] else: break nums[j] = index return nums nums = [2, 4, 1 ,0, 4, 3, 2, 5] result = insertSort(nums) print(result) [0, 1, 2, 2, 3, 4, 4, 5] 持续更新中..,