算法概述
冒泡排序（Bubble Sort）
选择排序（Selection Sort）
插入排序（Insertion Sort）
希尔排序（Shell Sort）
归并排序（Merge Sort）
快速排序（Quick Sort）
堆排序（Heap Sort）
计数排序（Counting Sort）
桶排序（Bucket Sort）
基数排序（Radix Sort）

0、算法概述

0.1 算法分类

十种常见排序算法可以分为两大类：

比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。

非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

0.2 算法复杂度

【排序-01】十大排序算法（Python实现）
目录
0、算法概述
1、冒泡排序（Bubble Sort）
2、选择排序（Selection Sort）
3、插入排序（Insertion Sort）
4、希尔排序（Shell Sort）
5、归并排序（Merge Sort）
6、快速排序（Quick Sort）
7、堆排序（Heap Sort）
8、计数排序（Counting Sort）
9、桶排序（Bucket Sort）
10、基数排序（Radix Sort）
参考文献

0.3 相关概念

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机需要的内存空间。

内执行时所需存储空间的度量，它也是数据规模n的函数。

1、冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端而得名。每次一轮后最大的数会固定到最底下。

1.1 算法描述

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

1.2 动画

1.3 代码

def bubbleSort(arr):
    n = len(arr)
    for i in range(n-1):
        for j in range(n-i-1):
            if arr[j]>arr[j+1]:
                arr[j],arr[j+1] = arr[j+1],arr[j]
    return arr
 
list1=[2,8,7,1,3,5,6,4]
bubbleSort(list1)
print (list1)

2、选择排序（Selection Sort）

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。以此类推，直到所有元素均排序完毕。

2.1 算法描述

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

初始状态：无序区为R[1..n]，有序区为空；
第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
n-1趟结束，数组有序化了。

2.2 动图演示

2.3代码

def selectionSort(arr):
    n = len(arr)
    for i in range(n-1):
        varminIndex = i
        for j in range(i+1,n):
            if arr[j] < arr[varminIndex]:  #寻找最小的数
                varminIndex = j
        arr[i] , arr[varminIndex]=arr[varminIndex],arr[i]
    return arr
 
list1=[2,8,7,1,3,5,6,4]
selectionSort(list1)
print (list1)

2.4 算法分析

表现最稳定的排序算法之一，因为无论什么数据进去都是O(n2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。

3、插入排序（Insertion Sort）

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

3.1 算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

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

3.2 动图演示

3.3 代码

def insertionSort(arr):
    n = len(arr)
    for i in range(1,n):
        preIndex = i - 1
        current = arr[i]
        while preIndex >=0  and  arr[preIndex] > current:
            arr[preIndex + 1] = arr[preIndex]
            preIndex -= 1
        arr[preIndex + 1] = current
    return arr
 
list1=[2,8,7,1,3,5,6,4]
insertionSort(list1)
print (list1)

3.4 算法分析

插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

4、希尔排序（Shell Sort）

1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

4.1 算法描述

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

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

4.2 动图演示

4.3 代码实现

希尔排序的排序思想在先将原序列划分成若干个子序列，其中划分的依据为按照间隔gap的大小分开。至于gap的选法可以不一样，这里以gap初始值选为序列总长度的一半为例。在每个子序列之内，使用直接插入排序（插入一个数字，前一个跟后一个相比，如果后一个值比前一个值小则调换两者之间的位置）。进行完第一轮排序之后，减小gap的大小，重复上述操作。由于间隔gap的值在不断减小，也称为减小增量排序，直到gap=1的时候，也就完成了整个序列的排序。

def shellSort(arr):
    n = len(arr)
    gap = n//2
    while gap>=1:
        for i in range(n):
            j = i
            while j>=gap  and arr[j-gap] > arr[j]:
                arr[j],arr[j-gap] = arr[j-gap],arr[j]
        gap = gap//2
    return arr    
list1=[2,8,7,1,3,5,6,4]
shellSort(list1)
print (list1)

4.4 算法分析

时间排序突破了O(n^2)，最坏情况：T(n) = O(n^2)。希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。　

5、归并排序（Merge Sort）

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

5.1 算法描述

把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。

5.2 动图演示

5.3 代码实现

# 记录归并排序
def MergeSort(arr):
    if len(arr) <= 1:
        return arr
    middle = len(arr)//2
    left = MergeSort(arr[:middle])
    right = MergeSort(arr[middle:])
    return merge(left, right)

def merge(a, b):
    c = []
    h = j = 0
    while j < len(a) and h < len(b):
        if a[j] < b[h]:
            c.append(a[j])
            j += 1
        else:
            c.append(b[h])
            h += 1
    if j == len(a):
        for i in b[h:]:
            c.append(i)
    else:
        for i in a[j:]:
            c.append(i)
    return c
            
list1=[2,8,7,1,3,5,6,4]
aa=MergeSort(list1)
print (aa)

5.4 算法分析

归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。

6、快速排序（Quick Sort）

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，关键字值在中间位置，再分别对这两部分记录继续进行排序，以达到整个序列有序。

6.1 算法描述

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

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

6.2 动画演示

6.3 代码实现（递归）

def quicksort(list,p,r):
    if p<r:
        q=partion(list,p,r)
        quicksort(list,p,q)
        quicksort(list,q+1,r)
def partion(list,p,r):  # 分区操作
    i=p-1            # i 之前的数都小于基准（pivot）  list[r]；
    for j in range(p,r):
        if list[j]<=list[r]:  # 小于基准时，进行替换
            i+=1              #替换时一定带上下下标一起
            list[i],list[j]=list[j],list[i]
    list[i+1],list[r]=list[r],list[i+1]  #i+1开始大于基准
    return i

list1=[2,8,7,1,3,5,6,4]
quicksort(list1,0,len(list1)-1)
print (list1)

7、堆排序（Heap Sort）

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

7.1 算法描述

堆排序节点访问

在这里我们借用wiki的定义来说明：

通常堆是通过一维数组来实现的。在阵列起始位置为0的情况中

父节点i的左子节点在位置(2*i+1);

父节点i的右子节点在位置(2*i+2);

子节点i的父节点在位置(i-1)//2;

(1)大根堆调整(max_heapify)；

(2)建立大根堆(build_max_heap)

(3)堆排序(heap_sort)；

7.2 动画

7.3 代码

def max_heapify(heap,heapSize,root):  # 调整列表中的元素并保证以root为根的堆是一个大根堆
    '''
    给定某个节点的下标root，这个节点的父节点、左子节点、右子节点的下标都可以被计算出来。
    父节点：(root-1)//2
    左子节点：2*root + 1
    右子节点：2*root + 2  即：左子节点 + 1
    '''
    left = 2*root + 1
    right = left + 1
    larger = root
    if left < heapSize and heap[larger] < heap[left]:
        larger = left
    if right < heapSize and heap[larger] < heap[right]:
        larger = right
    if larger != root:  # 如果做了堆调整则larger的值等于左节点或者右节点的值，这个时候做堆调整操作
        heap[larger], heap[root] = heap[root], heap[larger]
        # 递归的对调整过的子树做调整
        max_heapify(heap, heapSize, larger)

def build_max_heap(heap):  # 构造一个堆，将堆中所有数据重新排序
    heapSize = len(heap)
    for i in range((heapSize -2)//2,-1,-1):  # 自底向上建堆  从(heapSize -2)//2处开始调整，一直调整到第一个根节点。
        max_heapify(heap, heapSize, i)

def heap_sort(heap):  # 将根节点取出与最后一位做对调，对前面len-1个节点继续进行堆调整过程。
    build_max_heap(heap)
    # 调整后列表的第一个元素就是这个列表中最大的元素，将其与最后一个元素交换，然后将剩余的列表再递归的调整为最大堆
    for i in range(len(heap)-1, -1, -1):
        heap[0], heap[i] = heap[i], heap[0]
        max_heapify(heap, i, 0)

# 测试
if __name__ == '__main__':
    a = [30, 50, 57, 77, 62, 78, 94, 80, 84]
    print(a)
    heap_sort(a)

8、计数排序（Counting Sort）

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

8.1 算法描述

找出待排序的数组中最大和最小的元素；
统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

8.2 动图演示

8.3 代码

def count_sort(s):
    """计数排序"""
    # 找到最大最小值
    min_num = min(s)
    max_num = max(s)
    # 计数列表
    count_list = [0]*(max_num-min_num+1)
    # 计数
    for i in s:
        count_list[i-min_num] += 1
    s.clear()
    # 填回
    for ind,i in enumerate(count_list):
        while i != 0:
            s.append(ind+min_num)
            i -= 1
            
a = [3,6,8,4,2,6,7,3]
count_sort(a)
print(a)

9、桶排序（Bucket Sort）

桶排序是计数排序的升级版（但可以解决非整数的排序）。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

9.1 算法描述

设置一个定量的数组当作空桶；
遍历输入数据，并且把数据一个一个放到对应的桶里去；
对每个不是空的桶进行排序；
从不是空的桶里把排好序的数据拼接起来。

9.2 图片演示

9.3代码

def bucket_sort(s):
    """桶排序"""
    min_num = min(s)
    max_num = max(s)
    # 桶的大小
    bucket_range = (max_num-min_num) / len(s)
    # 桶数组
    count_list = [ [] for i in range(len(s) + 1)]
    # 向桶数组填数
    for i in s:
        count_list[int((i-min_num)//bucket_range)].append(i)
    s.clear()
    # 回填，这里桶内部排序直接调用了sorted
    for i in count_list:
        for j in sorted(i):
            s.append(j)
            
a = [3.2,6,8,4,2,6,7,3]
bucket_sort(a) 
print(a) # [2, 3, 3.2, 4, 6, 6, 7, 8]

10、基数排序（Radix Sort）

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

10.1 算法描述

取得数组中的最大数，并取得位数；
arr为原始数组，从最低位开始取每个位组成radix数组；
对radix进行计数排序（利用计数排序适用于小范围数的特点）；

10.2 动图演示

10.3 代码实现

def getbit(num,i):          # 获取元素第i位的数
    return (num % (i * 10) - (num % i)) // i
def getMax(numList):        # 获取数组中的最大值
    if len(numList) == 1:
        return numList[0]
    maxNum = numList[0]
    for i in range(len(numList)):
        if numList[i] > maxNum:
            maxNum = numList[i]
    return maxNum
def radixSort(numList):
    if len(numList) == 0 or len(numList) == 1:
        return numList
    maxNum = getMax(numList)
    bitCount = 0
    index = 1
    while maxNum // index:
        bitCount += 1
        index *= 10
    currentBit = 1 
    # 统计一下最大值的bitCount（有多少位），因为比较多少次，是有最大值的位数决定的
    while currentBit <= 10**(bitCount-1):          # 开始循环的进行每一个位的比较
        res = []
        buckets = [[] for i in range(10)]    # 桶排序
        for i in numList:
            currentBitNum = getbit(i,currentBit)
            buckets[currentBitNum].append(i)
        for i in range(10):
            for j in range(len(buckets[i])):
                res.append(buckets[i][j])
        numList = res
        currentBit *= 10
    return numList
numlist = [12,3,45,3543,214,1,4553]
print(radixSort(numlist))

10.4 算法分析

基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2n) ，当然d要远远小于n，因此基本上还是线性级别的。

基数排序的空间复杂度为O(n+k)，其中k为桶的数量。一般来说n>>k，因此额外空间需要大概n个左右。

基数排序不仅仅只能排正整数，只要通过调整元素放入桶数组的方式就可以排序字符串，浮点数等

参考文献

【1】十大基本排序（C++）： https://www.cnblogs.com/onepixel/articles/7674659.html

【2】快排的图；