一、排序算法分类
十大排序算法可以分为两大类：
非线性时间排序：通过比较元素来决定元素间的相对次序，其时间复杂度不能突破O(nlogn)
线性时间排序：不通过比较元素来决定元素间的相对次序，可以突破比较排序时间下界，以线性时间运行
其中：稳定是指如果a原本在b前面，而a=b，排序之后a仍然在b的前面，不稳定是a可能会出现在b的后面。
二、非线性时间排序算法
1. 冒泡排序（Bubble Sort）
· 遍历一遍，比较相邻元素大小，若元素顺序错误则交换位置，一遍结束后，一个元素的位置排好；
· 重复遍历列表中未排序元素，直至完成列表排序；(如果在一次遍历中，没有发生元素交换行为，则说明列表所有元素顺序正确，排序完成)
每轮只对相邻两个数比较与交换，每轮会将一个最值交换到数据列首或尾，像冒泡一样，n个数据会操作n-1轮。时间复杂度O(n^2)，额外空间开销在交换数据时那一个过渡空间，空间复杂度O(1)。
代码实现：
def bubble_sort(arr):
def swap(i, j):
arr[i], arr[j] = arr[j], arr[i]
n = len(arr)
swapped = True
x = -1
while swapped:
swapped = False
x = x + 1
for i in range(1, n - x):
if arr[i-1] > arr[i]:
swap(i-1, i)
swapped = True
return arr
2. 简单选择排序（Select Sort）
· 将输入列表/数组分为两部分：已经排序的子列表和剩余要排序的子列表；
· 在未排序的子列表中找到最小的元素，并将其按顺序放置在排序的子列表中，重复此过程，直至列表完全排序；
n个数操作n-1轮，每轮选一个最值，时间复杂度O(n^2)，额外空间开销在交换数据时那一个过渡空间，空间复杂度O(1)。
代码实现：
def select_sort(arr):
for i in range(len(arr)):
minvalue_idx = i
for j in range(i, len(arr)):
if arr[j] < arr[minvalue_idx]:
minvalue_idx = j
arr[i], arr[minvalue_idx] = arr[minvalue_idx], arr[i]
return arr
3. 快速排序（Quick Sort)
· 从数组中挑出一个元素，称为“基准”（pivot）;
· 分区：将所有比基准值小的元素摆放在基准值前，比基准值大的元素摆在基准后值，基准值位于数列的中间位置；
· 递归地把小于基准值的子数列和大于基准值的子数列排序；
递归到最底部的判断条件是数列的大小是0或者1，此时该数列显然已经有序。
选取基准值数种具体方法，其选取方法对排序的时间性能有关。常见会选取数组第一个数作为基准。
1）设置两个变量i、j，排序开始的时候：i=0, j=N-1；
2）以第一个数组元素作为基准，赋值给pivot，即key=A[0]；
3）从j开始向前搜索，即由后向前搜索(j--)，找到第一个小于pivot的A[j]，将A[j]和A[i]互换；
4）从i开始向后搜索，即由前向后搜索(i++)，找到第一个大于pivot的A[i]，将A[i]和A[j]互换；
5）重复3、4步，直到i=j;（3,4步中，没找到符合条件的值，即3中的A[j]不小于pivot，4中的A[i]不大于pivot时，改变i, j的值，j = j-1，i = i+1）
快排是原地排序，不需要辅助数组，但是递归调用需要辅助栈。快速排序最好的情况下是每次都正好将数组对半分，这样递归调用次数才是最少的，这种情况下比较次数为 Cn=2Cn/2+n，复杂度为 O(nlogn)。最坏的情况下，第一次从最小的元素切分，第二次从第二小的元素切分，如此这般。因此最坏的情况下需要比较n^2/2，为了防止数组从最开始就是有序的，在进行快排时需要随机打乱数组。
时间复杂度：快排涉及到递归调用，因此其时间复杂度与递归算法的复杂度相关，T[n] = aT[n/b] + f(n) 。
最优快排：每一次取到的元素都刚好平分整个数组，T[n] = 2T[n/2] + f(n)， T[n/2]为平分后的子数组的时间复杂度，f[n] 为平分这个数组时所花的时间。递归推算下来时间复杂度O( nlogn )。最差的情况就是每次取到的元素是数组中最大/或者最小的，此时时间复杂度O(n^2)。平均时间复杂度O(nlogn)。
空间复杂度：就地快速排序使用的空间O(1)，是常数级，而真正消耗空间的就是递归调用，因为每次递归就要保持一些数据。额外空间开销出在暂存基准值,最优情况下空间复杂度为O(logn)，每次都平分数组，最差情况下空间复杂度为O(n)，每次取到的元素是最值。
代码实现：
def partition(arr, low, high):
pivot = arr[low]
while low < high:
while low < high and arr[high] >= pivot:
high = high -1
arr[low] = arr[high]
while low < high and arr[low] <= pivot:
low = low + 1
arr[high] = arr[low]
arr[low] = pivot
return low
def QucikSort(arr, low, high):
if low >= high:
return
pivot_idx = partition(arr, low, high)
QucikSort(arr, low, pivot_idx-1)
QucikSort(arr, pivot_idx+1, high)
return arr
4. 简单插入排序（Insert Sort）
· 从第一个元素开始，该元素可被认为已经被排序；
· 取出下一个元素，在已经排序的元素列表中从后向前扫描；
· 如果该已排序元素大于新元素，将新元素向前移动至下一位置；
· 重复上一步骤，直到找到已排序的元素小于或等于新元素的位置；
· 将新元素插入到该位置后；
简单插入排序需要操作n-1轮，每轮将一个未排序元素插入排好序列，开始时默认第一个元素有序，将剩余n-1个数逐个插入。插入操作具体包括：比较确定插入位置，数据移位腾出合适空位。
每轮操作O(n)次，共O(n)轮，时间复杂度O(n^2)；
额外空间开销是数据移位时产生的一个过渡空间，空间复杂度为O(1)。
def InsertSort(arr):
n = len(arr)
if n<=1: return arr
for i in range(1,n):
j = i
target = arr[i]
while j>0 and target<arr[j-1]:
arr[j]=arr[j-1]
j=j-1
arr[j] = target
return arr
5. 堆排序（Heap Sort）
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序。堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
对堆中的结点按层进行编号，将这种逻辑结构映射到数组中如下:
该数组从逻辑上讲就是一个堆结构，用公式来描述堆的定义就是：
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
堆排序的基本思想：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样就会得到n个元素的次小值。如此反复执行，便能得到一个有序序列。
步骤一、构造初始堆：将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆）
- 假设给定无序序列结构如下：
- 此时从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子节点len(arr)/2-1 = 5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。
- 找到第二个非叶子节点4，其中4,9,8中9最大，4和9交换。
此时，交换导致了子根4,5,6结构混乱，继续调整，4,5,6中6最大，4和6交换位置，将无序序列构造成了一个大顶堆。
步骤二、将堆顶元素与末尾元素进行交换，使末尾元素最大，然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素，如此反复进行交换、重建、交换，直到整个序列有序。
- 将堆顶元素9与末尾元素4进行交换
- 重新调整结构，使其继续满足堆定义
- 再将堆顶元素8与末尾元素5进行交换，得到第二大元素8
后续过程，继续进行调整、交换，如此反复进行，最终使得整个序列有序。
总结：
· 将无序序列构建成一个堆，根据升序、降序需求选择大顶堆或小顶堆；
· 将堆顶元素与末尾元素交换，将最大元素“沉”到数组末端；
· 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序；
def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i +2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] #exchange
heapify(arr, n, largest)
def heapSort(arr):
n = len(arr)
# Build a maxheap
for i in range(n, -1, -1):
heapify(arr, n, i)
# exchange the max to the end
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
6. 希尔排序（Shell Sort）
7. 归并排序（Merge Sort）
归并排序是建立在归并操作上的一种有效的排序方法，该算法是分治法（Divide and Conquer）的一个非常典型的应用。先使每个子序列有序，再将两个有序子序列合并成一个有序序列称为2-路归并。
· 把长度为n的输入序列分成为两个长度为n/2的子序列；
· 对这两个子序列分别采用归并排序；
· 将两个排好序的子序列合并成一个最终的排序序列；
归并排序包括了Sort和Merge两部分。当有n个待排序元素时，需要进行logn轮归并排序，每一轮归并，其比较元素不超过n个，因此归并排序时间复杂度为nlogn；而在排序时需记录的中间元素个数与待排序元素个数相等，因此空间复杂度为O(n)。
def merge_sort(arr, low, high):
if low >= high: return
mid = (low + high) // 2
merge_sort(arr, low, mid)
merge_sort(arr, mid+1, high)
merge(arr, low, mid, high)
def merge(arr, low, mid, high):
container = []
i, j = low, mid + 1
while i<=mid and j<=high:
if arr[i] <= arr[j]:
container.append(arr[i])
i = i + 1
else:
container.append(arr[j])
j = j + 1
if i<=mid:
container.extend(arr[i:mid+1])
elif j<=high:
container.extend(arr[j:high+1])
arr[low:high+1] = container
