排序算法-python - 图1
参考：
https://www.cnblogs.com/onepixel/p/7674659.html

交换排序

  • 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
  • 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
  • 针对所有的元素重复以上的步骤，除了最后一个；

  • 重复步骤1~3，直到排序完成。
    1.1 冒泡排序(Bubble Sort)


冒泡排序对n个数据操作n-1轮，每轮找出一个最大（小）值。
操作只对相邻两个数比较与交换，每轮会将一个最值交换到数据列首（尾），像冒泡一样。
每轮操作O(n)次，共O（n）轮，时间复杂度O(n^2)。
额外空间开销出在交换数据时那一个过渡空间，空间复杂度O(1)
排序算法-python - 图2

  1. def BubbleSort(lst):
  2.     n=len(lst)
  3.     if n<=1:
  4.         return lst
  5.     for i in range (0,n):
  6.         for j in range(0,n-i-1):
  7.             if lst[j]>lst[j+1]:
  8.                 (lst[j],lst[j+1])=(lst[j+1],lst[j])
  9.     return lst
  10. x=input("请输入待排序数列：\n")
  11. y=x.split()
  12. arr=[]
  13. for i in  y:
  14.     arr.append(int(i))
  15. arr=BubbleSort(arr)
  16. #print(arr)
  17. print("数列按序排列如下：")
  18. for i in arr:
  19.     print(i,end=' ')

1.2 快速排序(Quick Sort)

从数列中挑出一个元素，称为 “基准”（pivot）；重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

快速排序基于选择划分，是简单选择排序的优化。
每次划分将数据选到基准值两边，循环对两边的数据进行划分，类似于二分法。
算法的整体性能取决于划分的平均程度，即基准值的选择，此处衍生出快速排序的许多优化方案，甚至可以划分为多块。
基准值若能把数据分为平均的两块，划分次数O(logn)，每次划分遍历比较一遍O(n)，时间复杂度O(nlogn)。
额外空间开销出在暂存基准值，O(logn)次划分需要O(logn)个，空间复杂度O(logn)

  1. def QuickSort(lst):
  2.     # 此函数完成分区操作
  3.     def partition(arr, left, right):
  4.         key = left  # 划分参考数索引,默认为第一个数为基准数，可优化
  5.         while left < right:
  6.             # 如果列表后边的数,比基准数大或相等,则前移一位直到有比基准数小的数出现
  7.             while left < right and arr[right] >= arr[key]:
  8.                 right -= 1
  9.             # 如果列表前边的数,比基准数小或相等,则后移一位直到有比基准数大的数出现
  10.             while left < right and arr[left] <= arr[key]:
  11.                 left += 1
  12.             # 此时已找到一个比基准大的书，和一个比基准小的数，将他们互换位置
  13.             (arr[left], arr[right]) = (arr[right], arr[left])
  15.         # 当从两边分别逼近，直到两个位置相等时结束，将左边小的同基准进行交换
  16.         (arr[left], arr[key]) = (arr[key], arr[left])
  17.         # 返回目前基准所在位置的索引
  18.         return left
  20.     def quicksort(arr, left, right):  
  21.         if left >= right:
  22.             return
  23.         # 从基准开始分区
  24.         mid = partition(arr, left, right)
  25.         # 递归调用
  26.         # print(arr)
  27.         quicksort(arr, left, mid - 1)
  28.         quicksort(arr, mid + 1, right)
  30.     # 主函数
  31.     n = len(lst)
  32.     if n <= 1:
  33.         return lst
  34.     quicksort(lst, 0, n - 1)
  35.     return lst
  37. print("<<< Quick Sort >>>")
  38. x = input("请输入待排序数列：\n")
  39. y = x.split()
  40. arr = []
  41. for i in y:
  42.     arr.append(int(i))
  43. arr = QuickSort(arr)
  44. # print(arr)
  45. print("数列按序排列如下：")
  46. for i in arr:
  47.     print(i, end=' ')

2. 插入排序

2.1 简单插入排序(Insert Sort)

从第一个元素开始，该元素可以认为已经被排序；取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5。

简单插入排序同样操作n-1轮，每轮将一个未排序树插入排好序列。
开始时默认第一个数有序，将剩余n-1个数逐个插入。插入操作具体包括：比较确定插入位置，数据移位腾出合适空位
每轮操作O(n)次，共O（n）轮，时间复杂度O(n^2)。
额外空间开销出在数据移位时那一个过渡空间，空间复杂度O(1)。
排序算法-python - 图3

  1. def InsertSort(lst):
  2.     n=len(lst)
  3.     if n<=1:
  4.         return lst
  5.     for i in range(1,n):
  6.         j=i
  7.         target=lst[i]            #每次循环的一个待插入的数
  8.         while j>0 and target<lst[j-1]:       #比较、后移，给target腾位置
  9.             lst[j]=lst[j-1]
  10.             j=j-1
  11.         lst[j]=target            #把target插到空位
  12.     return lst
  14. x=input("请输入待排序数列：\n")
  15. y=x.split()
  16. arr=[]
  17. for i in  y:
  18.     arr.append(int(i))
  19. arr=InsertSort(arr)
  20. #print(arr)
  21. print("数列按序排列如下：")
  22. for i in arr:
  23.     print(i,end=' ')

2.2 希尔排序(Shell Sort)

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列个数k，对序列进行k 趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

希尔排序是插入排序的高效实现（大家可以比对一下插入排序和希尔排序的代码），对简单插入排序减少移动次数优化而来。
简单插入排序每次插入都要移动大量数据，前后插入时的许多移动都是重复操作，若一步到位移动效率会高很多。
若序列基本有序，简单插入排序不必做很多移动操作，效率很高。
希尔排序将序列按固定间隔划分为多个子序列，在子序列中简单插入排序，先做远距离移动使序列基本有序；逐渐缩小间隔重复操作，最后间隔为1时即简单插入排序。
希尔排序对序列划分O(n)次，每次简单插入排序O(logn)，时间复杂度O(nlogn)
额外空间开销出在插入过程数据移动需要的一个暂存，空间复杂度O(1)
排序算法-python - 图4

  1. def ShellSort(lst):
  2.     def shellinsert(arr,d):
  3.         n=len(arr)
  4.         for i in range(d,n):
  5.             j=i-d
  6.             temp=arr[i]             #记录要出入的数
  7.             while(j>=0 and arr[j]>temp):    #从后向前，找打比其小的数的位置
  8.                 arr[j+d]=arr[j]                 #向后挪动
  9.                 j-=d
  10.             if j!=i-d:
  11.                 arr[j+d]=temp
  12.     n=len(lst)
  13.     if n<=1:
  14.         return lst
  15.     d=n//2
  16.     while d>=1:
  17.         shellinsert(lst,d)
  18.         d=d//2
  19.     return lst
  22. x=input("请输入待排序数列：\n")
  23. y=x.split()
  24. arr=[]
  25. for i in  y:
  26.     arr.append(int(i))
  27. arr=ShellSort(arr)
  28. #print(arr)
  29. print("数列按序排列如下：")
  30. for i in arr:
  31.     print(i,end=' ')

3.选择排序

3.1 简单选择排序(Select Sort)

简单选择排序同样对数据操作n-1轮，每轮找出一个最大（小）值。
操作指选择，即未排序数逐个比较交换，争夺最值位置，每轮将一个未排序位置上的数交换成已排序数，即每轮选一个最值。

每轮操作O(n)次，共O（n）轮，时间复杂度O(n^2)。

额外空间开销出在交换数据时那一个过渡空间，空间复杂度O(1)。
排序算法-python - 图5

  1. def SelectSort(lst):
  2.     n=len(lst)
  3.     if n<=1:
  4.         return lst
  5.     for i in range(0,n-1):
  6.         minIndex=i
  7.         for j in range(i+1,n):          #比较一遍，记录索引不交换
  8.             if lst[j]<lst[minIndex]:
  9.                 minIndex=j
  10.         if minIndex!=i:                     #按索引交换
  11.             (lst[minIndex],lst[i])=(lst[i],lst[minIndex])
  12.     return lst
  14. x=input("请输入待排序数列：\n")
  15. y=x.split()
  16. arr=[]
  17. for i in  y:
  18.     arr.append(int(i))
  19. arr=SelectSort(arr)
  20. #print(arr)
  21. print("数列按序排列如下：")
  22. for i in arr:
  23.     print(i,end=' ')

3.2 堆排序(Heap Sort)

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
堆排序的初始建堆过程比价复杂，对O(n)级别个非叶子节点进行堆调整操作O(logn)，时间复杂度O(nlogn)；之后每一次堆调整操作确定一个数的次序，时间复杂度O(nlogn)。合起来时间复杂度O(nlogn)
额外空间开销出在调整堆过程，根节点下移交换时一个暂存空间，空间复杂度O(1)
排序算法-python - 图6

  1. def  HeapSort(lst):
  2.     def heapadjust(arr,start,end):  #将以start为根节点的堆调整为大顶堆
  3.         temp=arr[start]
  4.         son=2*start+1
  5.         while son<=end:
  6.             if son<end and arr[son]<arr[son+1]:  #找出左右孩子节点较大的
  7.                 son+=1
  8.             if temp>=arr[son]:       #判断是否为大顶堆
  9.                 break
  10.             arr[start]=arr[son]     #子节点上移
  11.             start=son                     #继续向下比较
  12.             son=2*son+1
  13.         arr[start]=temp             #将原堆顶插入正确位置
  14. #######
  15.     n=len(lst)
  16.     if n<=1:
  17.         return lst
  18.     #建立大顶堆
  19.     root=n//2-1    #最后一个非叶节点（完全二叉树中）
  20.     while(root>=0):
  21.         heapadjust(ls,root,n-1)
  22.         root-=1
  23.     #掐掉堆顶后调整堆
  24.     i=n-1
  25.     while(i>=0):
  26.         (lst[0],lst[i])=(lst[i],lst[0])  #将大顶堆堆顶数放到最后
  27.         heapadjust(lst,0,i-1)    #调整剩余数组成的堆
  28.         i-=1
  29.     return lst
  30. #########
  31. x=input("请输入待排序数列：\n")
  32. y=x.split()
  33. arr=[]
  34. for i in  y:
  35.     arr.append(int(i))
  36. arr=HeapSort(arr)
  37. #print(arr)
  38. print("数列按序排列如下：")
  39. for i in arr:
  40.     print(i,end=' ')