【编程学习】基本排序算法的python实现

冒泡排序（Bubble Sort)

冒泡排序是一种简单的比较排序算法，它重复地遍历要排序的列表，一次比较两个相邻的元素，并将它们按照顺序交换位置，直到整个列表按照所需顺序排序完成。在每一次遍历过程中，较大的元素会像气泡一样逐渐上浮到列表的顶端，故得名“冒泡排序”。

冒泡排序的时间复杂度为$O(n^2)$，其中n是要排序的元素个数。这是因为在最坏情况下，需要进行$\frac{n(n-1)}{2}$次比较和交换操作，以确保列表完全有序。在最好情况下，如果列表已经是有序的，只需要进行一次遍历。

冒泡排序的空间复杂度为$O(1)$，即不需要额外的存储空间，排序过程中只需要常量级别的额外空间用于临时变量的存储。

def bubble_sort(x):
    end_p = len(x)
    while end_p > 1:
        for i in range(1, end_p):
            if x[i-1] > x[i]:
                x[i], x[i-1] = x[i-1], x[i]
        end_p -= 1

选择排序 (Select Sort)

选择排序是一种简单的排序算法，它通过多次遍历待排序列表，每次选取最小（或最大）的元素，并将其与当前遍历范围内的第一个元素交换位置，以此将最小（或最大）的元素逐步放置到正确的位置上。这个过程重复进行直到所有元素都被排序完成。选择排序的核心思想是不断选择剩余元素中的最小（或最大）元素，依次放置到已排序部分的末尾，直至整个列表完全有序。

选择排序的时间复杂度为$O(n^2)$，其中n是要排序的元素个数。这是因为在每次遍历中，都需要进行n次比较，以找到最小（或最大）的元素，并且需要重复进行n次遍历来完成排序。

选择排序的空间复杂度为$O(1)$，即不需要额外的存储空间，排序过程中只需要常量级别的额外空间用于临时变量的存储。

def select_sort(x):
    end_p = len(x)
    while end_p > 1:
        target = x[0]
        target_p = 0
        for i in range(1, end_p):
            if x[i] > target:
                target = x[i]
                target_p = i
        x[target_p], x[end_p-1] = x[end_p-1], x[target_p]
        end_p -= 1

插入排序 (Insert Sort)

插入排序也是一种很简单的排序算法，它将待排序列表分为已排序部分和未排序部分。在每一次迭代中，插入排序从未排序部分取出一个元素（第一个元素），并将其插入到已排序部分的适当位置，以保持已排序部分仍然有序。这个过程会持续进行直到所有元素都被插入到已排序部分，完成整个列表的排序。插入排序的核心思想是将一个元素逐步地插入到已排序部分中的正确位置，直至所有元素都被插入完成。

插入排序的时间复杂度为$O(n^2)$，其中n是要排序的元素个数。在最坏情况下，即待排序列表为逆序时，每个元素都需要逐个比较和移动直至插入到正确位置，导致总的比较和移动次数为$\frac{n(n-1)}{2}$。

插入排序空间复杂度为$O(1)$​，即不需要额外的存储空间，排序过程中只需要常量级别的额外空间用于临时变量的存储。

def insert_sort(x):
    p = 1
    n = len(x)
    while p < n:
        target = x[p]
        target_pos = p
        for q in range(p-1, -2, -1):
            if target < x[q]:
                x[target_pos] = x[q] if q >= 0 else target
                target_pos -= 1
            else:
                x[target_pos] = target
                break
        p += 1

归并排序 (Merge Sort)

归并排序是一种高效的排序算法，它采用分治策略。在归并排序中，待排序的列表被递归地划分为较小的子列表，直到每个子列表只包含一个元素。然后，这些单元素子列表被合并并按照适当的顺序组合成较大的有序子列表。这个合并过程会持续进行，直到所有的子列表被合并成一个完整的、有序的列表为止。归并排序的核心思想是将列表不断划分为较小的子列表，直到可以直接比较和合并为止，从而实现整体的排序。

归并排序的时间复杂度为$O(n log n)$，其中 n 是要排序的元素个数。这是因为归并排序的主要操作是分治和合并两个有序列表，分治操作的时间复杂度为$O(log n)$，而合并操作的时间复杂度为$O(n)$。在每个层级上，需要将整个列表划分为两部分，并进行合并操作，因此总体的时间复杂度为$O(n log n)$。

归并排序空间复杂度为$O(n)$​，即需要额外的存储空间来存储临时的合并结果。这是因为在合并过程中需要创建一个与原始列表大小相同的临时数组来存储合并结果，所以空间复杂度与列表大小成正比。

def merge_sort(x):
    if len(x) < 2:
        return x
    else:
        mid = len(x) // 2
        left_x, right_x = x[0:mid], x[mid::]
        return merge(merge_sort(left_x), merge_sort(right_x))

def merge(x1, x2):
    result = []
    p = q = 0
    while p < len(x1) and q < len(x2):
        if x1[p] < x2[q]:
            result.append(x1[p])
            p += 1
        else:
            result.append(x2[q])
            q += 1
    if p == len(x1):
        result.extend(x2[q::])
    if q == len(x2):
        result.extend(x1[p::])
    return np.array(result)

快速排序 (Quick Sort)

快速排序是一种常用的、高效的排序算法，它采用分治策略。在快速排序中，选择一个基准值，然后将列表中的元素分为两个子列表，其中一个子列表中的所有元素小于基准值，而另一个子列表中的所有元素大于基准值。接着，对这两个子列表分别递归地应用相同的排序过程，直到子列表中只包含一个元素时停止。最后，将所有子列表合并起来，即可得到完整的排序结果。快速排序的关键在于选择合适的基准值以及如何将列表划分为两个子列表，它的平均时间复杂度为$O(n log n)$。

快速排序的时间复杂度取决于选取的基准值以及待排序数据的分布情况。在最好和平均情况下，时间复杂度为$O(n log n)$，其中n是要排序的元素个数。这是因为每次划分都能将列表大致平均地分成两部分，使得每个元素最多参与$O(log n)$次划分，因此整体时间复杂度为$O(n log n)$。但在最坏情况下，即列表已经有序或基本有序时，时间复杂度可达到$O(n^2)$，此时每次划分只能减少一个元素，使得划分的层数接近于n，导致总的时间复杂度为二次阶。

快速排序空间复杂度为$O(log n)$至$O(n)$，取决于递归调用的深度。快速排序是一个原地排序算法，不需要额外的存储空间，但递归调用会消耗栈空间。在理想情况下，递归调用的深度为$O(log n)$，因此空间复杂度为$O(log n)$。但在最坏情况下，递归调用的深度接近于n，空间复杂度可达到$O(n)$。

def quick_sort(x):
    _quick_sort(x, 0, len(x)-1)
def _quick_sort(x, left, right):
    if left < right:
        p = left
        for q in range(left+1, right+1):
            if x[q] < x[left]:
                p += 1
                x[p], x[q] = x[q], x[p]
        x[left], x[p] = x[p], x[left]
        _quick_sort(x, left, p-1)
        _quick_sort(x, p+1, right)

希尔排序 (Shell Sort)

希尔排序是一种改进自插入排序的排序算法，也称为缩小增量排序。它的核心思想是通过将待排序的列表分成若干个子序列来改变插入排序的性质，对每个子序列进行插入排序，从而使得整个列表在某种程度上变得部分有序。然后逐步缩小子序列的间隔，重复进行插入排序，直到最后将间隔缩小为1，完成最后一次插入排序，使得整个列表有序。希尔排序的关键在于选择合适的间隔序列，不同的间隔序列会影响到排序算法的性能。

希尔排序的平均时间复杂度取决于间隔序列的选择，最好的情况下可以达到接近$O(n log n)$ 的性能，而最坏情况下则会退化到$O(n^2)$。

希尔排序空间复杂度为$O(1)$，即只需要常数级别的额外空间。

def shell_sort(x):
    gap = len(x) // 2
    while gap > 0:
        for i in range(gap, len(x)):
            j, tmp = i - gap, x[i]
            while (j >= 0) and (x[j] > tmp):
                x[j + gap] = x[j]
                j -= gap
            x[j+gap] = tmp
        gap = gap // 2

堆排序 (Heap Sort)

堆排序是一种基于二叉堆数据结构的排序算法。它利用了堆的性质：对于每个节点i，其父节点位于位置$(i-1)//2$，左子节点位于位置$2i+1$，右子节点位于位置$2i+2$。在堆排序中，首先将待排序列表构建成一个最大堆或最小堆，然后依次从堆顶（即最大值或最小值）取出元素，并将其放置到已排序部分的末尾。这个过程会持续进行，直到整个列表完全有序。堆排序的时间复杂度为$O(n log n)$，空间复杂度为$O(1)$。

堆排序的时间复杂度为$O(n log n)$，其中 n 是要排序的元素个数。构建初始堆的时间复杂度为$O(n)$，而每次调整堆的时间复杂度为 $O(log n)$，共需要调整 n 次。因此总的时间复杂度为$O(n log n)$。

堆排序空间复杂度为$O(1)$，即不需要额外的存储空间，排序过程中只需要常量级别的额外空间用于临时变量的存储。

def build_max_heap(x, len_x):
    for i in range(len_x//2-1, -1, -1):
        heapify(x, i, len_x)
def heapify(x, i, len_x):
    left = 2 * i + 1
    right = 2 * i + 2
    largest_pos = i
    if (left < len_x) and (x[left] > x[largest_pos]):
        largest_pos = left
    if (right < len_x) and (x[right] > x[largest_pos]):
        largest_pos = right
    
    if largest_pos != i:
        x[largest_pos], x[i] = x[i], x[largest_pos]
        heapify(x, largest_pos, len_x)
def heap_sort(x):
    x = x.copy()
    build_max_heap(x, len(x))
    for i in range(len(x)-1, -1, -1):
        x[0], x[i] = x[i], x[0]
        heapify(x, 0, i)
    return x

其他算法

除了这些基本算法以外，还有三种比较特别的排序方法。这三种排序算法都不需要进行元素之间的比较，因此适用于某些特定场景下的排序问题，具有线性时间复杂度的潜力。

计数排序（Counting Sort）是一种非比较性的排序算法，适用于已知待排序元素范围的整数列表。它通过统计列表中每个元素出现的次数，然后根据统计结果将元素放置到正确的位置上。计数排序的时间复杂度为$O(n + k)$，其中 n 是待排序元素个数，k 是待排序元素的范围。

桶排序（Bucket Sort）是一种排序算法，它将待排序元素分散到多个桶中，然后对每个桶中的元素进行排序，最后将所有桶中的元素按照顺序合并起来。桶排序适用于均匀分布的元素，其时间复杂度取决于桶的数量和每个桶内元素的分布情况。

基数排序（Radix Sort）是一种多关键字排序算法，它按照元素的每一位数字进行排序。基数排序可以采用LSD（Least Significant Digit）和MSD（Most Significant Digit）两种方法。LSD基数排序从最低位开始进行排序，而MSD基数排序从最高位开始进行排序。基数排序的时间复杂度为$O(d * (n + k))$，其中 d 是元素的位数，n 是待排序元素个数，k 是待排序元素范围。