一、冒泡排序
https://www.cnblogs.com/heyuquan/p/bubble-quick-sort.html
一、思想
每次比较两个相邻的元素，如果他们之前的顺序不符就交换位置。
比如5个数从小到大排序，23，64，1，43，21
第一趟：
第一次比较：23，64，1，43，21
第二次比较：23，1，64，43，21
第三次比较：23，1，43，64，21
第四次比较：23，1，43，21，64
经过第一趟的比较后，最大的数字已经到最后面了，接下来只需要比较前四个数字，以此类推。
第二趟：1，23，21，43，64
第三趟：1，21，23，43，64
第四趟：1，21，23，43，64
冒泡排序每一趟只能对一个数进行归位，如果是n个数进行排序，则需要将n-1个数归位，即n-1趟操作
冒泡排序解决了桶排序浪费空间的问题，但是它效率很低。
时间复杂度：O(n^2)二、用Python实现
`
#!/usr/bin/env python
# coding:utf-8
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 = [5, 6, 3, 1, 6, 2, 5, 33, 3]
print(bubbleSort(nums))
`二、选择排序
一、思想
第1趟，在待排序记录r1 ~ r[n]中选出最小的记录，将它与r1交换；
第2趟，在待排序记录r2 ~ r[n]中选出最小的记录，将它与r2交换；
以此类推，第i趟在待排序记录r[i] ~ r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。
原始数据：[3,1,0,8,4,2]
第一趟：[0,1,3,8,4,2]
第二趟：[0,1,3,8,4,2]
第三趟：[0,1,2,8,4,3]
第四趟：[0,1,2,3,4,8]
第五趟：[0,1,2,3,4,8]二、用Python实现选择排序
`
def selectSort(nums):
for i in range(len(nums)-1):
print(i)
min = i
for j in range(i + 1, len(nums)):
if nums[min] > nums[j]:
min = j
nums[i], nums[min] = nums[min], nums[i]
return nums`三、插入排序
一、思想
插入排序原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
其基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，是稳定的排
序方法。
时间复杂度为O(n^2)。二、步骤
1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5二、用Python实现插入排序
`
#!/usr/bin/env python
# coding:utf-8
def insertSort(lists):
for i in range(1, len(lists)):
key = lists[i]
j = i - 1
while j >= 0:
if lists[j] > key:
lists[j + 1] = lists[j]
lists[j] = key
j -= 1
return lists
lists = [4, 6, 2, 4, 7, 3, 9, 2, 1]
print(insertSort(lists))`
四、快速排序
一、思想
快速排序是对冒泡排序的一种改进，其基本思想是通过一趟排序将待排序记录分割成独立的两部分，一种一部分记录的关键字均比另一部分记录的关键字小，最后再分别对这两部分记录继续进行排序，以达到整个序列有序。
一趟快读排序的具体做法是：附设两个指针low和high，初值分别为low和high，设枢轴记录关键字为pivotkey，则首先从high所指位置向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录相互交换，然后从low所指位置起向后搜索，找到第一个关键字大于pivotkey的记录和枢轴记录相互交换，重复这两步直到low=high为止，过程如图：
二、用Python实现快速排序
`
#!/usr/bin/env python
# coding:utf-8
def quickSort(lists, left, right):
if left >= right:
return lists
key = lists[left]
low = left
high = right
print("111")
while left < right:
while (left < right and lists[right] >= key):
right -= 1
lists[left] = lists[right]
while (left < right and lists[left] <= key):
left += 1
lists[right] = lists[left]
lists[left] = key
print("key")
quickSort(lists, low, left - 1)
quickSort(lists, left + 1, high)
return lists
lists = [59, 3, 6, 3, 46]
print(quickSort(x, 0, 4))`
def partition(arr, low, high):
i = low-1
pivot = arr[high]
for j in range(low,high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[high] = arr[high], arr[i+1]
return i+1
def quickSort(arr, low, high):
if low<high:
pi = partition(arr, low, high)
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)
return arr
arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
print(quickSort(arr,0,len(arr)-1))
五、归并排序
时间复杂度：O(nlogn)
空间复杂度：O(n)
https://www.cnblogs.com/JMWan233/p/11175006.html
大文件排序：https://www.cnblogs.com/dream-of-cambridge/articles/8042311.html
5.1 递归
def mergeSort(arr):
if len(arr) < 2:
return arr
mid = len(arr)//2
left, right = arr[0:mid], arr[mid:]
return merge(mergeSort(left), mergeSort(right))
def merge(left, right):
result = []
while left and right:
if left[0] < right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
while left:
result.append(left.pop(0))
while right:
result.append(right.pop(0))
return result
print(mergeSort([1, 7, 5, 6, 9, 0, 10, 20, ]))
5.3 多路归并
https://www.cnblogs.com/dream-of-cambridge/articles/8046031.html