所有文章 > 日积月累 > 算法Python实现与解析
算法Python实现与解析

算法Python实现与解析

什么是算法

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

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

算法概念图

算法的主要特征

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

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

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

算法的基本要素

数据对象的运算和操作

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

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

算法的控制结构

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

算法的评价标准

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

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

评价标准图

十种经典排序算法

冒泡排序(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

  1. 问:什么是算法的时间复杂度?

    • 答:时间复杂度是描述算法运行时间的函数,通常以输入规模n为变量。
  2. 问:如何选择合适的排序算法?

    • 答:选择算法需考虑数据规模、排序稳定性需求和时间复杂度等因素。
  3. 问:什么是外部排序?

    • 答:外部排序用于处理无法在内存中排序的大数据,通常采用分步归并的方法。
  4. 问:为什么快速排序通常优于归并排序?

    • 答:虽然最坏情况下时间复杂度高于归并排序,但快速排序的常数因子小,内循环短小,通常效率更高。
  5. 问:排序算法的稳定性如何判断?

    • 答:排序算法的稳定性指排序后相等元素的顺序是否保持不变,冒泡排序和归并排序是稳定的,而快速排序和堆排序是不稳定的。
#你可能也喜欢这些API文章!