排序算法概览

复杂度分析

排序算法大的分类有两类：

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

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

稳定的排序算法：冒泡排序，插入排序，桶排序，归并排序，计数排序和基数排序（两只鸡将木棍插入水中捅正在吐泡泡的乌龟）。

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

冒泡排序

假定讨论升序排序，得名于最小的元素会慢慢上浮到序列的头部，而每一轮排序都会选出未排序序列中最大的元素置于未排序序列的队尾。

具体步骤是从左往右依次地比较相邻两个元素，如果前数大于后数，则交换两者，否则不予变动（因此冒泡排序是稳定的），这样第一轮结束，最大元素会被置于队尾，下一轮只需要比较前N-1个元素即可，以此类推，直至排序完成，时间复杂度为

1.比较相邻的两个元素，如果第一个比第二个大，就交换这两个数；
2.从左往右对每一对相邻的元素做比较，这样队尾的元素应该会是最大元素
3.除了最后一个元素，重复以上步骤
4.重复1～3，直到排序完成

def Bubble_Sort(arr):
    print("Bubble Sort:")
    print(rf"Initial Array: {arr}")
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
        print("Pass", i + 1, ":", arr)
    return arr

#output
Bubble Sort:
Initial Array: [64, 34, 25, 12, 22, 11, 90]
Pass 1 : [34, 25, 12, 22, 11, 64, 90]
Pass 2 : [25, 12, 22, 11, 34, 64, 90]
Pass 3 : [12, 22, 11, 25, 34, 64, 90]
Pass 4 : [12, 11, 22, 25, 34, 64, 90]
Pass 5 : [11, 12, 22, 25, 34, 64, 90]
Pass 6 : [11, 12, 22, 25, 34, 64, 90]
Pass 7 : [11, 12, 22, 25, 34, 64, 90]

选择排序

算法得名于每次都从未排序序列中选择最小（降序为最大）的元素，放到已排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕，时间复杂度。

初始状态，已排序序列为空，待排序序列为
第一趟排序，找到整个序列的最小值，将之与第一个元素交换位置，第趟排序，已排序序列为，待排序序列为，找到待排序序列的最小值，将之与待排序序列的第一个元素交换位置（因为需要交换位置，所以是不稳定的），然后将其加入已排序序列，得到已排序序列，待排序序列
以此类推，趟排序结束，数组已经有序

def Selection_Sort(arr):
    print("Selection Sort:")
    print(rf"Initial Array: {arr}")
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[min_idx] > arr[j]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
        print("Pass", i + 1, ":", arr)
    return arr

#output
Selection Sort:
Initial Array: [64, 34, 25, 12, 22, 11, 90]
Pass 1 : [11, 34, 25, 12, 22, 64, 90]
Pass 2 : [11, 12, 25, 34, 22, 64, 90]
Pass 3 : [11, 12, 22, 34, 25, 64, 90]
Pass 4 : [11, 12, 22, 25, 34, 64, 90]
Pass 5 : [11, 12, 22, 25, 34, 64, 90]
Pass 6 : [11, 12, 22, 25, 34, 64, 90]
Pass 7 : [11, 12, 22, 25, 34, 64, 90]

插入排序

对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入(当已排序元素小于等于待排序元素时，插在已排序元素之后，由此可见插入排序是稳定的)，就像打扑克牌抓牌一样，时间复杂度为

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

def Insertion_Sort(arr):
    print("Insertion Sort:")
    print(rf"Initial Array: {arr}")
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
        print("Pass", i, ":", arr)
    return arr

#output
Insertion Sort:
Initial Array: [64, 34, 25, 12, 22, 11, 90]
Pass 1 : [34, 64, 25, 12, 22, 11, 90]
Pass 2 : [25, 34, 64, 12, 22, 11, 90]
Pass 3 : [12, 25, 34, 64, 22, 11, 90]
Pass 4 : [12, 22, 25, 34, 64, 11, 90]
Pass 5 : [11, 12, 22, 25, 34, 64, 90]
Pass 6 : [11, 12, 22, 25, 34, 64, 90]

希尔排序

1959年Shell发明，第一个突破的排序算法，是简单插入排序的改进版，因为需要交换位置，因此也不稳定。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。首先将数组按照一定的间隔分组，比如长度为8的数组第一次设置的间隔就为4，然后这四组单独排序（使用的是插入排序），排序完成后重新设置间隔设为2（减半），采取同样的方法，再次分组、排序。直到最后分组间隔为1，再最后一次排序之后就完成整个数组的排序工作了（此时已经相对有序）。希尔排序的核心在于间隔序列的设定，一般时间复杂度为

def Shell_Sort(arr):
    print("Shell Sort:")
    print(rf"Initial Array: {arr}")
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        print("Gap", gap, ":", arr)
        gap //= 2
    return arr

#output
Shell Sort:
Initial Array: [64, 34, 25, 12, 22, 11, 90]
Gap 3 : [12, 22, 11, 64, 34, 25, 90]
Gap 1 : [11, 12, 22, 25, 34, 64, 90]

归并排序

采用分治法（Divide and Conquer），将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
首先将待排序的数组拆分成两数组，两个拆四个，直到最后每个数组都只由一个元素组成的（这样的每个数组都是有序的），然后合并两个有序数组（这是比较容易的），最后得到完整的已排序数据，时间复杂度为，归并排序是是稳定的。

归并排序

def Merge_Sort(arr):
    print("Merge Sort:")
    print(rf"Initial Array: {arr}")
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]
        Merge_Sort(L)
        Merge_Sort(R)
        i = j = k = 0
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1
        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1
    print("Sorted Array:", arr)
    return arr

#output
Merge Sort:
Initial Array: [64, 34, 25, 12, 22, 11, 90]
Merge Sort:
Initial Array: [64, 34, 25]
Merge Sort:
Initial Array: [64]
Sorted Array: [64]
Merge Sort:
Initial Array: [34, 25]
Merge Sort:
Initial Array: [34]
Sorted Array: [34]
Merge Sort:
Initial Array: [25]
Sorted Array: [25]
Sorted Array: [25, 34]
Sorted Array: [25, 34, 64]
Merge Sort:
Initial Array: [12, 22, 11, 90]
Merge Sort:
Initial Array: [12, 22]
Merge Sort:
Initial Array: [12]
Sorted Array: [12]
Merge Sort:
Initial Array: [22]
Sorted Array: [22]
Sorted Array: [12, 22]
Merge Sort:
Initial Array: [11, 90]
Merge Sort:
Initial Array: [11]
Sorted Array: [11]
Merge Sort:
Initial Array: [90]
Sorted Array: [90]
Sorted Array: [11, 90]
Sorted Array: [11, 12, 22, 90]
Sorted Array: [11, 12, 22, 25, 34, 64, 90]

快速排序

采用分治法。首先从待排序数组中任意挑选一个元素作为基准值，然后将所有比该基准值小的数都放在其左边，大的放在右边；这样就将原来待排序的数分成了两组，但每组数据量减半；再对这两组数采取以上同样的方法，直到最后每一小组数都排好序时，全部排序完成。

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

def Quick_Sort(arr):
    print("Quick Sort:")
    print(rf"Initial Array: {arr}")
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return Quick_Sort(left) + middle + Quick_Sort(right)

#output
uick Sort:
Initial Array: [64, 34, 25, 12, 22, 11, 90]
Quick Sort:
Initial Array: [11]
Quick Sort:
Initial Array: [64, 34, 25, 22, 90]
Quick Sort:
Initial Array: [22]
Quick Sort:
Initial Array: [64, 34, 90]
Quick Sort:
Initial Array: []
Quick Sort:
Initial Array: [64, 90]
Quick Sort:
Initial Array: [64]
Quick Sort:
Initial Array: []
# [11, 12, 22, 25, 34, 64, 90]

堆排序

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

堆是一种完全二叉树
特性：堆中每个节点的值都不小于（或不大于）其子树中任何节点的值
分类：大顶堆（上大下小）、小顶堆（上小下大）。除此之外的堆是“不成熟”的堆，即还在堆化的路上
堆化：顺着节点所在路径，向下或向上比较，然后交换节点

首先将n个元素的数组构造成一个大顶堆，然后将堆顶元素（0号元素）与最后一个元素交换，这样就将最大值放在了数组最后（n-1的位置），然后把数组长度减1，再将这n-1长度的数组重新构造成大顶堆，再把堆顶元素与新长度的数组最后的元素进行交换（n-2的位置）元素交换位置，如此往复最后就能将原数组从后向前的排序完成。时间复杂度为，不稳定。

def Heap_Sort(arr):
    print("Heap Sort:")
    print(rf"Initial Array: {arr}")
    def heapify(arr, n, i):
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2
        if left < n and arr[i] < arr[left]:
            largest = left
        if right < n and arr[largest] < arr[right]:
            largest = right
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            heapify(arr, n, largest)
    # Convert the array into a heap
    for i in range(len(arr) // 2 - 1, -1, -1):
        heapify(arr, len(arr), i)
    # Extract elements from the heap one by one
    for i in range(len(arr) - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)
    print("Sorted Array:", arr)
    return arr

计数排序

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
创建一个长度为数组中最大值+1的新数组，先初始化每一个元素，将其赋0，然后遍历待排序数组，将其对应下标的元素值+1，这样一直将每一个数出现的次数都统计好。因为下标是天然有序的，然后我们从头到尾访问这个统计数字出现次数的数组，将其下标对应的数输出小标对应元素值那么多次，至此排序完成。
计数排序是一个稳定的排序算法。当输入的元素是n个0到k之间的整数时，时间复杂度是，空间复杂度也是，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

def Counting_Sort(arr):
    print("Counting Sort:")
    print(rf"Initial Array: {arr}")
    # Find the maximum element in the array
    max_val = max(arr)
    # Create a count array to store the frequency of each element
    count = [0] * (max_val + 1)
    # Count the frequency of each element in the array
    for num in arr:
        count[num] += 1
    # Create a sorted array
    sorted_arr = []
    # Traverse the count array and append the elements to the sorted array
    for i in range(len(count)):
        sorted_arr.extend([i] * count[i])
    print("Sorted Array:", sorted_arr)
    return sorted_arr

#output
Counting Sort:
Initial Array: [4, 2, 2, 8, 3, 3, 1]
Sorted Array: [1, 2, 2, 3, 3, 4, 8]

桶排序

假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

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

def Bucket_Sort(arr):
    print("Bucket Sort:")
    print(rf"Initial Array: {arr}")
    max_val = max(arr)
    min_val = min(arr)
    bucket_size = (max_val - min_val) // len(arr) + 1
    print(bucket_size)
    buckets = [[] for _ in range(len(arr))]
    for i in range(len(arr)):
        index = (arr[i] - min_val) // bucket_size
        buckets[index].append(arr[i])
    for i in range(len(buckets)):
        buckets[i] = sorted(buckets[i])
    k = 0
    for i in range(len(buckets)):
        for j in range(len(buckets[i])):
            arr[k] = buckets[i][j]
            k += 1
    print("Sorted Array:", arr)
    return arr

#outputs
Bucket Sort:
Initial Array: [64, 34, 25, 12, 22, 11, 90]
12
Sorted Array: [11, 12, 22, 25, 34, 64, 90]

基数排序

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。
基数排序基于分别排序，分别收集，所以是稳定的。每一次关键字的桶分配都需要O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2n) ，当然d要远远小于n，因此基本上还是线性级别的。基数排序的空间复杂度为O(n+k)，其中k为桶的数量。

def Radix_Sort(arr):
    print("Radix Sort:")
    print(rf"Initial Array: {arr}")
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        count = [0] * 10
        output = [0] * len(arr)
        for i in range(len(arr)):
            index = arr[i] // exp
            count[index % 10] += 1
        for i in range(1, 10):
            count[i] += count[i - 1]
        # print(count)
        i = len(arr) - 1
        while i >= 0:
            index = arr[i] // exp
            output[count[index % 10] - 1] = arr[i]
            count[index % 10] -= 1
            i -= 1
        # print(count)
        for i in range(len(arr)):
            arr[i] = output[i]
        exp *= 10

        print("Sorted Array:", arr)
    return arr

#output
Radix Sort:
Initial Array: [170, 45, 75, 90, 802, 24, 2, 66]
Sorted Array: [170, 90, 802, 2, 24, 45, 75, 66]
Sorted Array: [802, 2, 24, 45, 66, 170, 75, 90]
Sorted Array: [2, 24, 45, 66, 75, 90, 170, 802]