一、冒泡排序
一、思想
每次比较两个相邻的元素，如果他们之前的顺序不符就交换位置。
比如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))`