排序算法（比较类算法）

冒泡排序（Bubble Sort）

算法步骤

1. 比较相邻元素，如果前一个比后一个大，就交换他们位置。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

动态演示

Python实现

def BubbleSort(arr):
    for i in range(1,len(arr)):#比较len(arr)-1次
        for j in range(0,len(arr)-i):#已经冒泡个数
            if arr[j]>arr[j+1]:
                arr[j],arr[j+1]=arr[j+1],arr[j]
    return arr

选择排序（Selection Sort）

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。

算法步骤

1. 首先在未排序序列中找到最小（大）元素，将其放到未排序序列首部。
2. 再从剩余未排序元素中寻找最小（大）元素，放到未排序序列首部（已排序序列尾部）
3. 不断重复步骤2，直至所有元素排序完毕

动图演示

Python实现

def selectSort(arr):
    for i in range(0,len(arr)-1):
        min_index = i #记录最小数的索引
        for j in range(i+1,len(arr)):
            if arr[j]<arr[min_index]:
                min_index = j
        if i!=min_index:
            arr[i],arr[min_index]=arr[min_index],arr[i]
    return arr            

插入排序（insert sort）

算法步骤

1. 将第一待排序序列的第一个元素看做有序序列，把第二个元素到最后一个元素当做无序序列
2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。

动图演示

Python实现

def insertSort(arr):
    for i in range(0,len(arr):
        preIndex = i-1
        current = arr[i]
        while preIndex>=0 and arr[preIndex]>current:
               arr[preIndex + 1] = arr[preIndex]
                preIndex -=1
        arr[preIndex] = current
    return arr

希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

算法步骤

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

动态演示

Python实现

import math
def shellSort(arr):
    gap = 1
    while (gap<len(arr)/3):
        gap = gap*3 + 1
    while gap>0:
        for i in range(gap,len(arr)):
            temp = arr[i]
            j = i-gap
            while j >=0 and arr[j] > temp:
                arr[j+gap]=arr[j]
                j-=gap
            arr[j+gap] = temp
        gap = math.floor(gap/3)
    return arr

归并排序（MergeSort）

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

• 自上而下递归
• 自下而上迭代

算法步骤

1. 申请空间，使其大小为2个已经排序序列之和，该空间用来存放合并后的序列；
2. 设定两个指针，最初位置分别为两个已排序序列的起始位置；
3. 比较两个指针所指向的元素，选择相对小的元素放到合并空间，并移动指针到下一位置；
4. 重复步骤3直到某一指针到达序列对位；
5. 将另一序列剩下的所有元素直接复制到合并序列尾。

动态展示

Python代码实现

import math
def mergeSort(arr):
    if (len(arr)<2):
        return arr
    middle = math.floor(len(arr)/2)
    left,right = arr[0:middle],arr[middle:]
    return merge(mergeSort(left),mergeSort(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

快速排序

快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好。

算法步骤

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

动图演示

Python代码实现

def quickSort(arr,left=None,right=None):
    left = 0 if not isinstance(left,(int,float)) else left
    right = len(arr)-1 if not isinstance(right,(int,float)) else right
    if left<right:
        partitionIndex = partition(arr,left,right)
        quickSort(arr,left,partitionIndex-1)
        quickSort(arr,partitionIndex+1,right)
    return arr

def partition(arr,left,right):
    pivot = left
    index = pivot + 1 #index负责作为小于基准值的指针
    i = index 
    while i<= right:
        if arr[i] < arr[pivot]:
            swap(arr,i,index)
            index+=1
        i+=1
    swap(arr,pivot,index-1)#pivot和小于他的数末端的数字交换，将pivot放到比较队列中部
    return index-1#返回pivot位置

def swap(arr,i,j):
    arr[i],arr[j]=arr[j],arr[i]

def quick_sort(data):#另一种实现（便于理解）
    d = [[], [], []]
    d_pivot = data[-1]  # 因为是乱序数组，所以第几个都是可以的，理论上是一样的
    for i in data:
        if i < d_pivot:  # 小于基准值的放在前
            d[0].append(i)
        elif i > d_pivot:  # 大于基准值的放在后
            d[2].append(i)
        else:  # 等于基准值的放在中间
            d[1].append(i)
    if len(d[0]) > 1:  # 大于基准值的子数组，递归
        d[0] = quick_sort(d[0])
    if len(d[2]) > 1:  # 小于基准值的子数组，递归
        d[2] = quick_sort(d[2])
    d[0].extend(d[1])
    d[0].extend(d[2])
    return d[0]

堆排序（Heapsort）

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序的平均时间复杂度为O(nlogn)

算法步骤

1. 创建一个堆H[0....n-1];
2. 把堆首（最大值）和堆尾互换；
3. 把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置；
4. 重复步骤2，直到堆的尺寸为1。

动图演示

python代码实现

import math
def buildMaxHeap(arr):
    for i in range(math.floor(len(arr)/2),-1,-1):
        heapify(arr,i)

def heapify(arr,i):
    left = 2*i + 1
    right = 2*i +2
    largest = i
    if left < arrLen and arr[left]>arr[largest]:
        largest = left
    if right<arrLen and arr[right]>arr[largest]:
        largest = right
    if largest != i:
        swap(arr,i,largest)
        heapify(arr,largest)

def swap(arr,i,j):
    arr[i],arr[j] = arr[j],arr[i]

def heapSort(arr):
    global arrLen
    arrLen = len(arr)
    buildMaxHeap(arr)
    for i in range(len(arr)-1,0,-1):
        swap(arr,0,i)
        heapify(arr,0)
    return arr

引用内容
https://www.cnblogs.com/wuxinyan/p/8615127.html
https://www.cnblogs.com/Mufasa/p/10527387.html