算法Python实现与解析

什么是算法

算法（Algorithm）是解决问题的一种明确而有条理的步骤集合，它对输入进行处理后产生所需的输出结果。算法在计算机科学中占据核心地位，因为它提供了系统化解决问题的方法。算法的优劣主要通过时间复杂度和空间复杂度来衡量，这两者分别反映了算法在运行时所耗费的时间和内存资源。

算法的设计旨在从初始状态开始，通过一系列明确的步骤，最终在合理的时间内获得输出。有些算法也可能包含随机输入，这在随机化算法中尤为常见。

算法概念图

算法的主要特征

算法应具备五大特征：有穷性、确切性、输入项、输出项和可行性。

有穷性：算法必须在有限步骤内结束。
确切性：每一步骤必须有明确的定义。
输入项：算法可以有零个或多个输入。
输出项：算法至少有一个输出。
可行性：算法的每一步都必须在有限时间内完成。

这些特征确保算法是能够在现实中被有效执行的。

算法的基本要素

数据对象的运算和操作

计算机的基本操作分为四类：

算术运算：加、减、乘、除。
逻辑运算：或、且、非。
关系运算：大于、小于、等于、不等于。
数据传输：输入、输出、赋值。

算法的控制结构

算法的功能不仅依赖于操作本身，还与操作的执行顺序密切相关。良好的控制结构可以提高算法的效率。

算法的评价标准

算法的质量通常通过以下标准来评估：

时间复杂度：算法执行所需时间，通常表示为问题规模n的函数。
空间复杂度：算法执行所需的内存空间。
正确性：算法正确解决问题的能力。
可读性：算法易于被人理解的程度。
健壮性：算法处理错误输入的能力。

评价标准图

十种经典排序算法

冒泡排序（Bubble Sort）

冒泡排序通过重复地遍历待排序列，比较相邻元素并交换错误顺序的元素来进行排序。它的时间复杂度为O(n^2)，在输入数据已经有序时效率最高。

    def bubbleSort(nums):
        for i in range(len(nums) - 1):
            for j in range(len(nums) - i - 1):
                if nums[j] > nums[j+1]:
                    nums[j], nums[j+1] = nums[j+1], nums[j]
        return nums

冒泡排序动图

选择排序（Selection Sort）

选择排序在每次遍历中选择最小的元素，放到已排序的序列末尾。其时间复杂度为O(n^2)，不受输入数据影响。

    def selectionSort(nums):
        for i in range(len(nums) - 1):
            minIndex = i
            for j in range(i + 1, len(nums)):
                if nums[j] < nums[minIndex]:
                    minIndex = j
            nums[i], nums[minIndex] = nums[minIndex], nums[i]
        return nums

选择排序动图

插入排序（Insertion Sort）

插入排序模拟整理扑克牌的手法，每次将新元素插入到已排序的部分中。虽然平均时间复杂度为O(n^2)，但在部分有序序列中表现良好。

    def insertionSort(nums):
        for i in range(len(nums) - 1):
            curNum, preIndex = nums[i+1], i
            while preIndex >= 0 and curNum < nums[preIndex]:
                nums[preIndex + 1] = nums[preIndex]
                preIndex -= 1
            nums[preIndex + 1] = curNum
        return nums

插入排序动图

希尔排序（Shell Sort）

希尔排序是插入排序的优化版本，通过比较距离较远的元素来加快排序速度。它的时间复杂度为O(n log n)。

    def shellSort(nums):
        lens = len(nums)
        gap = 1
        while gap  0:
            for i in range(gap, lens):
                curNum, preIndex = nums[i], i - gap
                while preIndex >= 0 and curNum < nums[preIndex]:
                    nums[preIndex + gap] = nums[preIndex]
                    preIndex -= gap
                nums[preIndex + gap] = curNum
            gap //= 3
        return nums

希尔排序过程图

归并排序（Merge Sort）

归并排序采用分治法，将序列递归拆分直至每部分仅含一个元素，然后合并排序。其时间复杂度为O(n log n)，但需要额外内存。

    def mergeSort(nums):
        def merge(left, right):
            result = []
            i = j = 0
            while i < len(left) and j < len(right):
                if left[i] <= right[j]:
                    result.append(left[i])
                    i += 1
                else:
                    result.append(right[j])
                    j += 1
            result += left[i:] + right[j:]
            return result
        if len(nums) <= 1:
            return nums
        mid = len(nums) // 2
        left = mergeSort(nums[:mid])
        right = mergeSort(nums[mid:])
        return merge(left, right)

归并排序动图

快速排序（Quick Sort）

快速排序是基于分治法的高效排序算法，常用于大数据集。其时间复杂度平均为O(n log n)，尽管最坏情况下为O(n²)。

    def quickSort(nums):
        if len(nums) <= 1:
            return nums
        pivot = nums[0]
        left = [x for x in nums[1:] if x = pivot]
        return quickSort(left) + [pivot] + quickSort(right)

快速排序动图

其他排序算法

堆排序（Heap Sort）

堆排序将序列构建为大根堆或小根堆，通过调整堆结构进行排序。其时间复杂度为O(n log n)。

    def heapSort(nums):
        def adjustHeap(nums, i, size):
            lchild = 2 * i + 1
            rchild = 2 * i + 2
            largest = i
            if lchild  nums[largest]:
                largest = lchild
            if rchild  nums[largest]:
                largest = rchild
            if largest != i:
                nums[largest], nums[i] = nums[i], nums[largest]
                adjustHeap(nums, largest, size)
        def builtHeap(nums, size):
            for i in range(len(nums)//2)[::-1]:
                adjustHeap(nums, i, size)
        size = len(nums)
        builtHeap(nums, size)
        for i in range(len(nums))[::-1]:
            nums[0], nums[i] = nums[i], nums[0]
            adjustHeap(nums, 0, i)
        return nums

堆排序动图

计数排序（Counting Sort）

计数排序为线性时间复杂度的排序算法，适用于值域不大的整数序列。

    def countingSort(nums):
        bucket = [0] * (max(nums) + 1)
        for num in nums:
            bucket[num] += 1
        i = 0
        for j in range(len(bucket)):
            while bucket[j] > 0:
                nums[i] = j
                bucket[j] -= 1
                i += 1
        return nums

计数排序动图

桶排序（Bucket Sort）

桶排序是计数排序的升级版，适合均匀分布的数据。其效率取决于桶的数量和数据分布。

    def bucketSort(nums, defaultBucketSize=5):
        maxVal, minVal = max(nums), min(nums)
        bucketSize = defaultBucketSize
        bucketCount = (maxVal - minVal) // bucketSize + 1
        buckets = [[] for _ in range(bucketCount)]
        for num in nums:
            buckets[(num - minVal) // bucketSize].append(num)
        nums.clear()
        for bucket in buckets:
            insertionSort(bucket)
            nums.extend(bucket)
        return nums

基数排序（Radix Sort）

基数排序适用于多关键字排序，常用的LSD方法从低位到高位排序。

    def radixSort(nums):
        mod = 10
        div = 1
        mostBit = len(str(max(nums)))
        buckets = [[] for _ in range(mod)]
        while mostBit:
            for num in nums:
                buckets[num // div % mod].append(num)
            i = 0
            for bucket in buckets:
                while bucket:
                    nums[i] = bucket.pop(0)
                    i += 1
            div *= 10
            mostBit -= 1
        return nums

基数排序动图

外部排序简介

外部排序用于处理无法全部载入内存的大数据集，通常采用归并排序法。其核心在于如何高效地进行子文件的划分和归并。

FAQ

问：什么是算法的时间复杂度？
- 答：时间复杂度是描述算法运行时间的函数，通常以输入规模n为变量。
问：如何选择合适的排序算法？
- 答：选择算法需考虑数据规模、排序稳定性需求和时间复杂度等因素。
问：什么是外部排序？
- 答：外部排序用于处理无法在内存中排序的大数据，通常采用分步归并的方法。
问：为什么快速排序通常优于归并排序？
- 答：虽然最坏情况下时间复杂度高于归并排序，但快速排序的常数因子小，内循环短小，通常效率更高。
问：排序算法的稳定性如何判断？
- 答：排序算法的稳定性指排序后相等元素的顺序是否保持不变，冒泡排序和归并排序是稳定的，而快速排序和堆排序是不稳定的。