演算法 - 排序

1，插入排序（Insertion-Sort）

直接插入排序

视频素材 - bilibili
工作原理

代码实现

def Insertion_Sort(a):
    for i in range(len(a)):
        key = a[i]
        j = i - 1
        while i > 0 and a[i - 1] > key:
            a[i] = a[i - 1]
            i -= 1
        a[i] = key
    return a

a = [2, 3, 5, 2, 1, 9, 7, 5, 2]
b = Insertion_Sort(a)
print(b)
>>>[1, 2, 2, 2, 3, 5, 5, 7, 9]

算法分析

时间复杂度为

最佳的情况：已经由小到大排好序
第5行 则只会被执行 n-1 次
第6,7行 则不会被执行

最差情况：列表为逆序
第5行 对任何一个 a[i] 进行排序时 都会被执行 i 次（共有n个a[i]）
第6,7行 随同 行5，每一次排序会被执行 i-1 次（进行n次排序）

时间复杂度【最好情况–最坏情况–平均情况】–空间复杂度–稳定性

折半插入排序

视频素材 - bilibili
工作原理

代码实现

def BinaryInsertSort(list):
    for i in range(2, len(list)):
        list[0] = list[i]
        low = 1
        high = i - 1
        while low <= high:
            m = int((low + high) / 2)  # 折半
            if list[0] < list[m]:  # 插入点在低半区
                high = m - 1
            else:  # 插入点在高半区
                low = m + 1

        j = i - 1  # 记录后移
        while j >= high + 1:
            list[j + 1] = list[j]
            j -= 1
        list[high + 1] = list[0]

**其中[0]=-1这一位置是暂存单元，不会参与排序 **

a = [-1, 2, 3, 5, 2, 1, 9, 7, 5, 2]
BinaryInsertSort(a)
print(a)

>>>[2, 1, 2, 2, 2, 3, 5, 5, 7, 9]

算法分析

与直接插入排序法相比：
折半插入减少了比较次数，但没有减少移动次数（平均性能更优）
当数据量 n 较大时，且数据越乱，越适合用折半排序
而在最佳情况下时，直接排序（只用比较一次）反而优于折半排序

2，归并排序（Merge Sort）

视频素材 - bilibili
工作原理
将两个有序或两个以上有序的子序列，归并为一个有序序列
通常采用 2-路归并排序
即：将两个相邻的有序子序列 L[ 1 … n1+1 ] & R[ 1 … n2+1 ]，归并为一个序列



代码实现
参考文献 — 讲的很详细

def merge(arr, l, m, r):
    n1 = m - l + 1
    n2 = r - m

    # 创建临时数组
    L = [0] * (n1)
    R = [0] * (n2)

    # 拷贝数据到临时数组 arrays L[] 和 R[]
    for i in range(0, n1):
        L[i] = arr[l + i]

    for j in range(0, n2):
        R[j] = arr[m + 1 + j]

        # 归并临时数组到 arr[l..r]
    i = 0  # 初始化第一个子数组的索引
    j = 0  # 初始化第二个子数组的索引
    k = l  # 初始归并子数组的索引

    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1

    # 拷贝 L[] 的保留元素
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1

    # 拷贝 R[] 的保留元素
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1

# 进行递归
def mergeSort(arr, start_index, end_index):
    if start_index < end_index:
        mid = int((start_index + (end_index - 1)) / 2)

        mergeSort(arr, start_index, mid)
        mergeSort(arr, mid + 1, end_index)
        
        merge(arr, start_index, mid, end_index)

arr = [12, 11, 13, 5, 6, 7]
n = len(arr)
print("给定的数组", arr)

mergeSort(arr, 0, n - 1)
print("排序后的数组", arr)
>>>给定的数组 [12, 11, 13, 5, 6, 7]
   排序后的数组 [5, 6, 7, 11, 12, 13]

算法分析


缺点：需要一个与原序列同样大小的辅助序列（L，R）

详细分析
分治算法（Divide-and-Conquer Algorithm）

也可以写作

3，选择排序（Selection Sort）

–（演算法 2，Sorting.pdf ）

简单选择排序

视频素材 - bilibili
算法原理

精髓在于：找最小值（要注意每一次找最小值的范围）

代码实现

def Normal_Select_Sort(a):
    for i in range(len(a)):
        # 找最小值的位置（index）
        key = i
        for j in range(i, len(a)):
            if a[key] > a[j]:
                key = j
        # 将最小值与a[i]进行交换
        if key != i:
            key_value = a[key]
            a[key] = a[i]
            a[i] = key_value

Normal_Select_Sort(list)
print(list)
>>>[0, 1, 2, 2, 5, 5, 10, 33, 44, 52, 66, 77, 99]

算法分析

时间复杂度【最好情况–最坏情况–平均情况】–空间复杂度–稳定性

什么是堆排序

堆的定义

视频素材 - bilibili

（堆实质是满足如下性质的完全二叉树：二叉树中任意非叶子节点均小于（大于）它的孩子节点）

光看定义肯定会比较晕，那么来看一下下边的例子吧~

再来看两个错误的例子

堆排序的原理

实现堆排序需要解决的两个问题：
1，如何由一个无序序列建成一个堆。
2，如何在输出堆顶元素后，调整剩余元素为新的堆。

堆的调整

视频素材 - bilibili
下边不理解的话，上边视频从3:50开始看一下

（大根堆 交换大者）

堆的建立

视频素材 - bilibili
通过反复的筛选，将一个无序的序列建成一个堆

具体的操作：

如果还是一脸懵逼就来看一下这个例子吧~

堆排序的代码实现

视频素材 - bilibili
还没学二叉树，所以下边的代码我自己看也是云里雾里，补完二叉树会回来进行更改和补充的（希望早日给这两行加上删除线）

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1  # left = 2*i + 1
    r = 2 * i + 2  # right = 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]  # 交换

        heapify(arr, n, largest)


def heapSort(arr):
    n = len(arr)

    # 建立一个最大堆
    for i in range(n, -1, -1):
        heapify(arr, n, i)

    # 一个个交换元素
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 交换
        heapify(arr, i, 0)

heapSort(list)
print(list)
>>>[0, 1, 2, 2, 5, 5, 10, 33, 44, 52, 66, 77, 99]

算法分析

堆排序的时间主要耗费在建初始堆和调整建新堆时的反复及筛选上。
对排序的最大优点即是：最坏和最好的情况下，时间复杂度均为↓

无论待排序列中的记录是正序还是逆序，都不会使得堆排序处于“最好”或“最坏”的状态。
另外，堆排序仅需一个记录大小供交换用的辅助存储空间。
然而，堆排序是一种不稳定的排序方法，不适用于排序记录个数 n 较小的情况，但对于 n 较大的文件还是很有效的。