今天要讲的排序算法分别有以下几种
冒泡排序，选择排序，插入排序，快速排序，归并排序，希尔排序。
今天通过Python来介绍这几个算法,每个我都会添加相应的动图以助理解。
冒泡排序—O(n^2)( Bubble Sort)
1.比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3.针对所有的元素重复以上的步骤，除了最后一个；
4.重复步骤1~3，直到排序完成。
冒泡排序
def bubbleSort(nums):
#先确定要排列的长度
l = len(nums)
while l > 0:
#如果是空列表则不进行下一步
for i in range(l - 1):
if nums[i] > nums[i+1]:
#从第0位开始，例如第一位数大于第二位，则两个调换位置，直到排出重小到大
nums[i], nums[i+1] = nums[i+1], nums[i]
l -= 1
return nums
选择排序——O(n^2)(Selection Sort)
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序
def SelectionSort(nums):
for i in range(len(nums)):
min1 = i
for j in range(i+1, len(nums)):
if nums[min1] > nums[j]:
min1 = j
nums[i], nums[min1] = nums[min1], nums[i]
return nums
插入排序—O(n^2)(Insertion Sort)
插入算法把要排序的[数组]分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
插入排序，简单来说就是从中选择一个数去和其他数对比
1.从第一个元素开始，该元素可以认为已经被排序；
2.取出下一个元素，在已经排序的元素序列中从后向前扫描；
3.如果该元素（已排序）大于新元素，将该元素移到下一位置；
4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5.将新元素插入到该位置后；
6.重复步骤2~5。
插入排序
def insertsort(nums):
for i in range(1,len(nums)):
t = nums[i]
j = i - 1
while j >= 0 and t < nums[j]:
nums[j + 1] = nums[j]
j = j - 1
nums[j + 1] = t
return nums
快速排序—O(nlogn)(Quick Sort)
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
快速排序.gif
def quicksort(nums):
if len(nums)<=1:
return nums
p = nums[0]
#p设置为基准值，用于和后面对比
left_list, right_list = [], []
#创建2个列表分别去存储大于和小于的数
for l in nums[1:]:
if l<p:
left_list.append(l)
else:
right_list.append(l)
return quicksort(left_list) + [p] + quicksort(right_list)
归并排序——O(nlogn)（Merge Sort）
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
归并排序
def MergeSort(lists):
if len(lists) <= 1:
return lists
num = int( len(lists) / 2 )
left = MergeSort(lists[:num])
right = MergeSort(lists[num:])
return Merge(left, right)
def Merge(left,right):
r, l=0, 0
result=[]
while l<len(left) and r<len(right):
if left[l] <= right[r]:
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
result += list(left[l:])
result += list(right[r:])
return result
希尔排序—O(nlogn)(Shell's Sort)
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列个数k，对序列进行k 趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插>入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
希尔排序
def shellSort(arr):
n = len(arr)
gap = int(n/2)
while gap > 0:
for i in range(gap,n):
temp = arr[i]
j = i
while j >= gap and arr[j-gap] >temp:
arr[j] = arr[j-gap]
j -= gap
arr[j] = temp
gap = int(gap/2)
