以下排序算法均按照从小到大排序N个元素：
1、冒泡排序
基本思想：
遍历元素列表，比较相邻的元素，如果第一个比第二个大，则交换其位置，经过第一轮比较，最大的元素将恰好被放置到最后一个；
第二轮不再比较最后的元素，只比较前面的N-1个元素，则经过第二轮比较之后，我们可以确定第二大的元素；
依次类推，第i轮比较能够确定第i大的元素，可知经过N-1轮比较后我们能够确定所有元素的位置（为什么不是N轮比较?——因为前N-1个大的元素确定了，还剩最后一个，自然就是最小的，无需再比较）
def bubble_sort(nums):
if nums is not None: # 注意判空,不要用=或者!=判空
for i in range(1, len(nums)): # 一共进行1到N-1轮比较，N即列表长度len(nums)
is_sorted = True # 用来判断是否已经排好序
for j in range(len(nums) - i): # 第i轮比较中需要比较第0,1,…,(N-i-1)个元素与其后面一个位置上的元素的大小
if nums[j] > nums[j + 1]:
is_sorted = False # 如果没有发生交换，则说明已经排好序，无需进行下一轮比较
nums[j], nums[j + 1] = nums[j + 1], nums[j]
if is_sorted:
break
return nuts
2、选择排序
基本思想：
遍历元素，记录下最小的元素所在的位置，然后把最小的元素和位置0上的元素互换；
一共进行N-1轮遍历：
第一轮确定第1小的元素，放在位置0；
第二轮确定第2小的元素，放在位置1；x
…
第i轮确定第i小的元素，放在位置i；
N-1轮遍历之后可以确定所有元素的正确位置。
def select_sort(nums):
if nums is not None: # 注意判空
for i in range(0, len(nums) - 1): # 一共进行0到N-2共N-1轮选择，N即列表长度len(nums)
min_index = i # 先初始化每轮选择中最小的元素的位置为每轮遍历的第一个元素
for j in range(i + 1, len(nums)): # 从第一个元素的下一个位置开始与记录的最小元素做比较
if nums[j] < nums[min_index]:
min_index = j
if i != min_index:
nums[i], nums[min_index] = nums[min_index], nums[i]
3、快速排序
基本思想：采用分而治之的思想，选取nums中的一个数作为基准点，把要排序的数据分成两部分，一部分比基准点小，一部分比基准点大；
然后再对这两部分数据分别采用分而治之的方法进行排序；
最后再把这几部分数据连接到一起。
def quick_sort(nums):
if len(nums) <= 1:
return nums
pivot = nums[len(nums) // 2]
left = [x for x in nums if x < pivot]
middle = [x for x in nums if x == pivot]
right = [x for x in nums if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
4、插入排序
基本思想：插入排序的原理类似于打扑克牌，把待排序数据分成两部分，一部分是已排好序的有序数据，一部分是乱序数据，
开始时默认第一个数有序，然后再将后面的数逐个插入，插入操作具体包括：
1、与有序数据比较，确定插入位置，
2、在每次比较中将比待插入数据大的数据后移，给待插入数据腾位置
def insert_sort(nums):
for i in range(len(nums)):
preIndex = i-1 # 0到i-1的数据为已经排好序的有序数据
curnum = nums[i] # 记录下一个要插入到有序数据中的数
# 遍历有序数据，找到curnum应插入的位置
while preIndex >= 0 and nums[preIndex] > curnum: # 注意不要漏掉preIndex等于0
nums[preIndex+1] = nums[preIndex] # 比curnum大的数往后挪
preIndex -= 1
nums[preIndex+1] = curnum
return nums
5、希尔排序
基本思想：希尔排序是直接插入排序的升级版，减少插入排序的移动次数
插入排序在每次插入一个数据的过程中，凑要大量移动数据，
希尔排序将序列按固定间隔划分为多个子序列，在子序列中简单插入排序，先做远距离移动使序列基本有序；
逐渐缩小间隔重复操作，最后间隔为1时即简单插入排序。
def shell_insert(nums, d):
n = len(nums)
for i in range(d, n):
j = i - d
temp = nums[i] # 记录要插入的数
while j >= 0 and nums[j] > temp: # 从后向前，找到比其小的数的位置
nums[j + d] = nums[j] # 向后挪动
j -= d
if j != i - d:
nums[j + d] = temp
def shell_sort(nums):
n = len(nums)
if n <= 1:
return nums
d = n//2
while d >= 1:
shell_insert(nums, d)
d = d//2
return nums
6、归并排序
基本思想：归并排序运用分治递归思想：将大问题分为较小的子问题，分而治之；递归调用同样的方法解决子问题。
最终将序列的排序问题分治为一个数的排序问题，关键在于如何将子问题答案合并为问题答案。
两个有序序列合并为一个有序序列，借助一个暂存数组（列表），两个序列元素依次比较填入暂存列表，形成一个有序序列。
归并排序划分子问题采用二分法，共需O(logn)次划分，当然需要相当次合并；每次合并遍历比较O(n)。时间复杂度O(nlogn)。
def merge_sort(nums):
import math
if len(nums) < 2:
return nums
middle = math.floor(len(nums)/2)
left, right = nums[0:middle], nums[middle:]
return merge(merge_sort(left), merge_sort(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
