排序算法基本内容

算法分类

比较分类

非线性时间比较类排序：通过比较来决定元素间的相对次序，

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

它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序

以是否访问内存分类

内部排序是数据记录在内存中进行排序，
而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。

算法复杂度分析

主要从：过程图解、算法思想、代码实现、算法分析这四个方面讲解

关于时间复杂度

1.平方阶 (O(n2)) 排序各类简单排序：直接插入、直接选择和冒泡排序。
2.线性对数阶 (O(nlog2n)) 排序快速排序、堆排序和归并排序。
3.O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。希尔排序。
4.线性阶 (O(n)) 排序基数排序，此外还有桶、箱排序。

关于稳定性

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。
不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

排序算法分析与实现

常用的十大排序算法中最简单的五种（冒泡、选择、插入、希尔、归并）

1. 交换排序

1、冒泡排序（Bubble Sort）【前后比较-交换】

冒泡排序是最简单也是最容易理解的排序方法，其原理就是重复地走访过要排序的数列，

一次比较两个元素，如果他们的顺序错误就把他们交换过来。

走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），

就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名冒泡排序。

1.过程图解

2.算法思想

从第一个和第二个开始比较，如果第一个比第二个大，则交换位置，然后比较第二个和第三个，逐渐往后
经过第一轮后最大的元素已经排在最后，所以重复上述操作的话第二大的则会排在倒数第二的位置。
那重复上述操作n-1次即可完成排序，因为最后一次只有一个元素所以不需要比较

3.代码实现

# 冒泡排序
def bubbleSort(arr):
    """冒泡排序"""
    # 第一层for表示循环的遍数
    for i in range(len(arr) - 1):
        # 第二层for表示具体比较哪两个元素
        for j in range(len(arr) - 1 - i):
            if arr[j] > arr[j + 1]:
                # 如果前面的大于后面的，则交换这两个元素的位置
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr
if __name__ == '__main__':
    li = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]
    print(bubbleSort(li))

4.算法分析

冒泡排序是一种简单直接暴力的排序算法。

为什么说它暴力？因为每一轮比较可能多个元素移动位置，而元素位置的互换是需要消耗资源的，

所以这是一种偏慢的排序算法，仅适用于对于含有较少元素的数列进行排序。

稳定性：我们从代码中可以看出只有前一个元素大于后一个元素才可能交换位置，所以相同元素的相对顺序不可能改变，所以它是稳定排序
比较性：因为排序时元素之间需要比较，所以是比较排序
时间复杂度：因为它需要双层循环n*(n-1))，所以平均时间复杂度为O(n^2)
空间复杂度：只需要常数个辅助单元，所以空间复杂度为O(1)，我们把空间复杂度为O(1)的排序成为原地排序（in-place）
记忆方法：想象成气泡，一层一层的往上变大

2、快速排序（Quick Sort）【选取一个基准值，小数在左大数在在右】

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。

在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。

事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。

虽然 Worst Case 的时间复杂度达到了 O(n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好，

可是这是为什么呢，我也不知道。好在我的强迫症又犯了，查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案：

快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，

比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

1.过程图解

2.算法思想

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

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。

虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

3.代码实现

# 快速排序：最快的n*logN
def quickSort(lst):
    if len(lst)<2:
        return lst
    pivot = lst[0]
    left = [i for i in lst[1:] if i <= pivot]
    right = [i for i in lst[1:] if i > pivot]
    arr = quickSort(left)+[pivot] + quickSort(right)
    return arr

4.算法分析

1.比较性：排序时元素之间需要比较，所以为比较排序
2.稳定性：我们从代码中可以看到当剩余数列中元素小于等于基准元素的，就把他们放到基准元素前面重新排列，

剩余数列中元素大于基准元素的，就把他们放到基准元素后面面重新排列，故为不稳定排序
3.时间复杂度：复杂度为O(n*logN)
4.空间复杂度：复杂度为O(n)
5.记忆方法：比我大的往前站，比我小的往后站，你们自己再按照我的规矩重新排一下，有点像军训排队

2. 插入排序

3、插入排序(Insert Sort)【逐个插入到前面的有序数中】

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要联想到打扑克时的排序就好了

1.过程图解

2.算法思想

1.从第二个元素开始和前面的元素进行比较，如果前面的元素比当前元素大，则将前面元素后移，当前元素依次往前，直到找到比它小或等于它的元素插入在其后面然后
2.选择第三个元素，重复上述操作，进行插入
3.依次选择到最后一个元素，插入后即完成所有排序

3.代码实现

def insert_sort(arr):
    """插入排序"""
    # 第一层for表示循环插入的遍数
    for i in range(1, len(arr)):
        for j in range(i, 0, -1):  ## 倒序取从下标i的元素开始到下标0
                if arr[j] < arr[j - 1]:
                    arr[j], arr[j - 1] = arr[j - 1], arr[j]
                else: ## 如果当前数值大于前一个数值，退出
                    break
    return arr

4.算法分析

插入排序的适用场景：一个新元素需要插入到一组已经是有序的数组中，或者是一组基本有序的数组排序.

1. 比较性：排序时元素之间需要比较，所以为比较排序
1. 稳定性：从代码我们可以看出只有比较元素大于当前元素，比较元素才会往后移动，所以相同元素是不会改变相对顺序
1. 时间复杂度：插入排序同样需要两次循坏一个一个比较，故时间复杂度也为O(n^2)
1. 空间复杂度：只需要常数个辅助单元，所以空间复杂度也为O(1)
1. 记忆方法：想象成在书架中插书：先找到相应位置，将后面的书往后推，再将书插入

4、希尔排序（Shell Sort）【从大范围到小范围进行比较-交换】类似冒泡和插入的联合

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量(间隔)排序”（Diminishing Increment Sort），

是插入排序算法的一种更高效的改进版本，基于·插入排序·的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

它与插入排序的不同之处在于，它会优先比较距离较远的元素，该方法因D.L.Shell于1959年提出而得名。

希尔排序的基本思想是：

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，

待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

1.过程图解

2.算法思想

希尔排序的整体思想是将固定间隔的几个元素之间排序，然后再缩小这个间隔。这样到最后数列就成为了基本有序数列，

而前面我们讲过插入排序对基本有序数列排序效果较好。

1. 计算一个增量（间隔）值
1. 对元素进行增量元素进行比较，比如增量值为7，那么就对0,7,14,21…个元素进行插入排序
1. 然后对1,8,15…进行排序，依次递增进行排序
1. 所有元素排序完后，缩小增量比如为3，然后又重复上述第2，3步
1. 最后缩小增量至1时，数列已经基本有序，最后一遍普通插入即可

已知的最增量式是由 Sedgewick 提出的 (1, 5, 19, 41, 109,…)，

该步长的项来自 9 * 4^i - 9 * 2^i + 1 和 4^i - 3 * 2^i + 1 这两个算式。

这项研究也表明 比较 在希尔排序中是最主要的操作，而不是交换。

用这样增量式的希尔排序比插入排序和堆排序都要快，甚至在小数组中比快速排序还快，

但是在涉及大量数据时希尔排序还是比快速排序慢。

3.代码实现

def shell_sort(arr):
    """希尔排序"""
    # 取整计算增量（间隔）值
    gap = len(arr) // 2
    while gap > 0:
        # 从增量值开始遍历比较
        for i in range(gap, len(arr)):
            j = i
            current = arr[i]
            # 元素与他同列的前面的每个元素比较，如果比前面的小则互换
            while j - gap >= 0 and current < arr[j - gap]:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = current
        # 缩小增量（间隔）值
        gap //= 2
    return arr

4.算法分析

1.比较性：排序时元素之间需要比较，所以为比较排序
2.稳定性：因为希尔排序是间隔的插入，所以存在相同元素相对顺序被打乱，所以是不稳定排序
3.时间复杂度：最坏时间复杂度O(n^2)平均复杂度为O(n^1.3)
4.空间复杂度：只需要常数个辅助单元，所以空间复杂度也为O(1)
5.记忆方法：插入排序是每轮都是一小步，希尔排序是先大步后小步，它第一个突破O(n2)的排序算法。

联想起阿姆斯特朗登月之后说：这是我个人一小步，却是人类迈出的一大步。

3. 选择排序

5、选择排序（Selection sort）【选择最小的数据放在前面】

选择排序（Selection sort）是一种简单直观的排序算法。

无论什么数据进去都是 O(n²) 的时间复杂度。

所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，

存放在序列的起始位置，所以称为：选择排序

1.过程图解

2.算法思想

设第一个元素为比较元素，依次和后面的元素比较，比较完所有元素找到最小（大）的元素，将它和第一个元素互换
重复上述操作，我们找出第二小（大）的元素和第二个位置的元素互换，以此类推找出剩余最小元素将它换到前面，即完成排序

3.代码实现

def selection_sort(arr):
    """选择排序"""
    # 第一层for表示循环选择的遍数
    for i in range(len(arr) - 1):
        # 将起始元素设为最小元素
        min_index = i
        # 第二层for表示最小元素和后面的元素逐个比较
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_index]:
                # 如果当前元素比最小元素小，则把当前元素角标记为最小元素角标
                min_index = j
        # 查找一遍后将最小元素与起始元素互换
        arr[min_index], arr[i] = arr[i], arr[min_index]
    return arr
if __name__ == '__main__':
    li = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]
    selection_sort(li)
    print(li)

另外一种写法,它和冒泡法类似

# 选择排序
def selectSort(nums):
    for i in range(len(nums)):
        for j in range(i,len(nums)):
            if nums[i] > nums[j]:
                nums[i], nums[j] = nums[j], nums[i]

if __name__ == '__main__':
    nums = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]
    selectSort(nums)
    print(nums)

4.算法分析

选择排序和冒泡排序很类似，但是选择排序每轮比较只会有一次交换，

而冒泡排序会有多次交换，交换次数比冒泡排序少，就减少cpu的消耗，

所以在数据量小的时候可以用选择排序，实际适用的场合非常少。

比较性：因为排序时元素之间需要比较，所以是比较排序
稳定性：因为存在任意位置的两个元素交换，比如[5, 8, 5, 2]，
第一个5会和2交换位置，所以改变了两个5原来的相对顺序，所以为不稳定排序。
时间复杂度：我们看到选择排序同样是双层循环n*(n-1))，所以时间复杂度也为：O(n^2)
空间复杂度：只需要常数个辅助单元，所以空间复杂度也为O(1)
记忆方法：选择对象要先选最小的

6、堆排序(Heap Sort)【利用最大堆和最小堆的特性】

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。

堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

1.过程图解

2.算法思想

将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；

将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；

由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，

然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。

不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

3.代码实现

def  HeapSort(lst):
    def heap_adjust(arr, start,end):  #将以start为根节点的堆调整为大顶堆
        temp=arr[start]
        son=2*start+1
        while son<=end:
            if son<end and arr[son]<arr[son+1]:  #找出左右孩子节点较大的
                son+=1
            if temp>=arr[son]:       #判断是否为大顶堆
                break
            arr[start]=arr[son]     #子节点上移
            start=son                     #继续向下比较
            son=2*son+1
        arr[start]=temp             #将原堆顶插入正确位置

    n=len(lst)
    if n<=1:
        return lst
    #建立大顶堆
    root=n//2-1    #最后一个非叶节点（完全二叉树中）
    while(root >= 0):
        heap_adjust(lst, root,n-1)
        root-=1
    #掐掉堆顶后调整堆
    i=n-1
    while(i>=0):
        (lst[0],lst[i])=(lst[i],lst[0])  #将大顶堆堆顶数放到最后
        heap_adjust(lst,0,i-1)    #调整剩余数组成的堆
        i-=1
    return lst

算法分析

堆排序的初始建堆过程比价复杂，对O(n)级别个非叶子节点进行堆调整操作O(logn)，时间复杂度O(nlogn)；

之后每一次堆调整操作确定一个数的次序，时间复杂度O(nlogn)。合起来时间复杂度O(nlogn)

额外空间开销出在调整堆过程，根节点下移交换时一个暂存空间，空间复杂度O(1)

比较性：因为排序时元素之间需要比较，所以是比较排序
稳定性：因为存在任意位置的两个元素交换，所以为不稳定排序。
时间复杂度：时间复杂度为：O(nlogn)
空间复杂度：空间复杂度也为O(1)
记忆方法：

4. 归并排序

7、归并排序 (Merge Sort)【分治法-2-4-8插入排序】

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,

该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

归并排序适用于子序列有序的数据排序。

1.过程图解

2.算法思想

从上图看分解后的数列很像一个二叉树。

使用递归将源数列使用二分法分成多个子列
申请空间将两个子列排序合并然后返回
将所有子列一步一步合并最后完成排序

3.代码实现

def merge_sort(arr):
    """归并排序"""
    if len(arr) == 1:
        return arr
    # 使用二分法将数列分两个
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    # 使用递归运算
    return marge(merge_sort(left), merge_sort(right))


def marge(left, right):
    """排序合并两个数列"""
    result = []
    # 两个数列都有值
    while len(left) > 0 and len(right) > 0:
        # 左右两个数列第一个最小放前面
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    # 只有一个数列中还有值，直接添加
    result += left
    result += right
    return result

4.算法分析

归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，

但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。

1.比较性：排序时元素之间需要比较，所以为比较排序
2.稳定性：我们从代码中可以看到当左边的元素小于等于右边的元素就把左边的排前面，

而原本左边的就是在前面，所以相同元素的相对顺序不变，故为稳定排序
3.时间复杂度：复杂度为O(nlog^n)
4.空间复杂度：在合并子列时需要申请临时空间，而且空间大小随数列的大小而变化，所以空间复杂度为O(n)
5.记忆方法：所谓归并肯定是要先分解，再合并

5. 线性时间非比较类排序

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

基数排序：根据键值的每位数字来分配桶；
计数排序：每个桶只存储单一键值；
桶排序：每个桶存储一定范围的数值；

8、计数排序（Counting Sort）【字典计数-还原】

计数排序用待排序的数值作为计数数组（列表）的下标，统计每个数值的个数，然后依次输出即可。

计数数组的大小取决于待排数据取值范围，所以对数据有一定要求，否则空间开销无法承受。

1.过程图解

2.算法思想

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

3.代码实现

def CountSort(lst):
    n=len(lst)
    num=max(lst)
    count=[0]*(num+1)
    for i in range(0,n):
        count[lst[i]]+=1
    arr=[]
    for i in range(0,num+1):
        for j in range(0,count[i]):
            arr.append(i)
    return arr

4. 算法分析

计数排序是一个稳定的排序算法。
当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。
当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

时间复杂度:计数排序只需遍历一次数据，在计数数组中记录，输出计数数组中有记录的下标，时间复杂度为O(n+k)。
空间复杂度:空间复杂度O(n+k)。

9、桶排序（Bucket Sort）【链表】

桶排序实际上是计数排序的推广，但实现上要复杂许多。

桶排序先用一定的函数关系将数据划分到不同有序的区域（桶）内，然后子数据分别在桶内排序，之后顺次输出。

当每一个不同数据分配一个桶时，也就相当于计数排序。

假设n个数据，划分为k个桶，桶内采用快速排序，时间复杂度为O(n)+O(k * n/klog(n/k))=O(n)+O(n(log(n)-log(k))),

显然，k越大，时间复杂度越接近O(n)，当然空间复杂度O(n+k)会越大，这是空间与时间的平衡。

2.算法分析

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

3.代码实现

def BucketSort(lst):
    # 桶内使用快速排序
    def QuickSort(lst):
        def partition(arr,left,right):
            key=left         #划分参考数索引,默认为第一个数，可优化
            while left<right:
                while left<right and arr[right]>=arr[key]:
                    right-=1
                while left<right and arr[left]<=arr[key]:
                    left+=1
                (arr[left],arr[right])=(arr[right],arr[left])
            (arr[left],arr[key])=(arr[key],arr[left])
            return left
 
        def quicksort(arr,left,right):   #递归调用
            if left>=right:
                return
            mid=partition(arr,left,right)
            quicksort(arr,left,mid-1)
            quicksort(arr,mid+1,right)
        #主函数
        n=len(lst)
        if n<=1:
            return lst
        quicksort(lst,0,n-1)
        return lst

    n=len(lst)
    big=max(lst)
    num=big//10+1
    bucket=[]
    buckets=[[] for i in range(0,num)]
    for i in lst:
        buckets[i//10].append(i)     #划分桶
    for i in buckets:                       #桶内排序
        bucket=QuickSort(i)
    arr=[]
    for i in buckets:
        if isinstance(i, list):
            for j in i:
                arr.append(j)
        else:
            arr.append(i)
    for i in range(0,n):
        lst[i]=arr[i]
    return lst

4.算法分析

桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，

取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。

很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

10、基数排序（Radix Sort）

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，

然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，

所以基数排序也不是只能使用于整数。

1.过程图解

2.算法分析

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

3、代码实现

import math
def RadixSort(lst):
    def getbit(x,i):       #返回x的第i位（从右向左，个位为0）数值
        y=x//pow(10,i)
        z=y%10
        return z
    def CountSort(lst):
        n=len(lst)
        num=max(lst)
        count=[0]*(num+1)
        for i in range(0,n):
            count[lst[i]]+=1
        arr=[]
        for i in range(0,num+1):
            for j in range(0,count[i]):
                arr.append(i)
        return arr
    Max=max(lst)
    for k in range(0,int(math.log10(Max))+1):             #对k位数排k次,每次按某一位来排
        arr=[[] for i in range(0,10)]
        for i in lst:                 #将ls（待排数列）中每个数按某一位分类（0-9共10类）存到arr[][]二维数组（列表）中
            arr[getbit(i,k)].append(i)
        for i in range(0,10):         #对arr[]中每一类（一个列表）  按计数排序排好
            if len(arr[i])>0:
                arr[i]=CountSort(arr[i])
        j=9
        n=len(lst)
        for i in range(0,n):     #顺序输出arr[][]中数到ls中，即按第k位排好
            while len(arr[j])==0:
                j-=1
            else:
                lst[n-1-i]=arr[j].pop()   
    return lst

4 算法分析

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

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

补充：外部排序

外部排序是指大文件排序，即待排序的数据记录以文件的形式存储在外存储器上。

由于文件中的记录很多、信息容量庞大，所以整个文件所占据的存储单元往往会超过了计算机的内存量，

因此，无法将整个文件调入内存中进行排序。于是，在排序过程中需进行多次的内外存之间的交换。

在实际应用中，由于使用的外设不一致，通常可以分为磁盘文件排序和磁带文件排序两大类。

外部排序基本上由两个相对独立的阶段组成。

首先，按可用内存大小，将外存上含 N 个记录的文件分成若干长度为 L(<N) 的子文件，

依次读入内存，利用内部排序算法进行排序。然后，将排序后的文件写入外存，

通常将这些文件称为归并段（Run）或“顺串”；对这些归并段进行逐步归并，

最终得到整个有序文件。可见外部排序的基本方法是归并排序法，下面的例子给出了一个简单的外部排序解决过程。

【例子】给定磁盘上有6大块记录需要排序，而计算机内存最多只能对3个记录块进行内排序，则外部排序的过程如下图所示。

【解析】首先将连续的3大块记录读入内存，用任何一种内部排序算法完成排序，再写回磁盘。

经过2次3大块记录的内部排序，得到上图（a）的结果。然后另用一个可容纳6大块记录的周转盘，辅助最后的归并。

方法是将内存分成3块，其中2块用于输入，1块用于输出，指定一个输入块只负责读取一个归并段中的记录，如上图（b）所示。
归并步骤为：

当任一输入块为空时，归并暂停，将相应归并段中的一块信息写入内存
将内存中2个输入块中的记录逐一归并入输出块
当输出块写满时，归并暂停，将输出块中的记录写入周转盘
如此可将2个归并段在周转盘上归并成一个有序的归并段。

上例的解决方法是最简单的归并法，事实上外部排序的效率还可以进一步提高。要提高外排的效率，关键要解决以下4个问题：

如何减少归并轮数
如何有效安排内存中的输入、输出块，使得机器的并行处理能力被最大限度利用
如何有效生成归并段
如何将归并段进行有效归并

针对这四大问题，人们设计了多种解决方案，例如釆用多路归并取代简单的二路归并，就可以减少归并轮数；

例如在内存中划分出2个输出块，而不是只用一个，就可以设计算法使得归并排序不会因为磁盘的写操作而暂停，

达到归并和写周转盘同时并行的效果；例如通过一种“败者树”的数据结构，可以一次生成2倍于内存容量的归并段；

例如利用哈夫曼树的贪心策略选择归并次序，可以耗费最少的磁盘读写时间等

小结

各种算法重要的时理解&记住它们的算法原理，因为代码是永远记不住的，只要记住原理你就能用伪代码实现。

排序算法基本内容

算法分类

比较分类

以是否访问内存分类

算法复杂度分析

相关概念

关于时间复杂度

关于稳定性

排序算法分析与实现

1. 交换排序

1、冒泡排序（Bubble Sort）【前后比较-交换】

1.过程图解

2.算法思想

3.代码实现

4.算法分析

2、快速排序（Quick Sort）【选取一个基准值，小数在左大数在在右】

1.过程图解

2.算法思想

3.代码实现

4.算法分析

2. 插入排序

3、插入排序(Insert Sort)【逐个插入到前面的有序数中】

1.过程图解

2.算法思想

3.代码实现

4.算法分析

4、希尔排序（Shell Sort）【从大范围到小范围进行比较-交换】类似冒泡和插入的联合

1.过程图解

2.算法思想

3.代码实现

4.算法分析

3. 选择排序

5、选择排序（Selection sort）【选择最小的数据放在前面】

1.过程图解

2.算法思想

3.代码实现

4.算法分析

6、堆排序(Heap Sort)【利用最大堆和最小堆的特性】

1.过程图解

2.算法思想

3.代码实现

算法分析

4. 归并排序

7、归并排序 (Merge Sort)【分治法-2-4-8插入排序】

1.过程图解

2.算法思想

3.代码实现

4.算法分析

5. 线性时间非比较类排序

8、计数排序（Counting Sort）【字典计数-还原】

1.过程图解

2.算法思想

3.代码实现

4. 算法分析

9、桶排序（Bucket Sort）【链表】

2.算法分析

3.代码实现

4.算法分析

10、基数排序（Radix Sort）

1.过程图解

2.算法分析

3、代码实现

4 算法分析

补充：外部排序

小结

你的赏识是我前进的动力