Python与人工自能36——排序算法(冒泡、选择、插入)

前言

Python作为当前最为流行的一种语言与身份程序员的大家们几乎是时时刻刻分不开的，无论是做任何方面的工作基本上不会缺少Python的出现，就好似现阶段各平台的低代码Agent开发都支持的是Python语言，对其它的语言友好度都不是很高，那么，我们就非常的有必要将Python深入的了解一下，本系列文章的目的就是为了让大家对于Python有个更加直观的了解，并且要使用Python做很多的小应用，只有真正的实操了才能更好的掌握它。

正文

开发工具：Pythony与人工智能——3、Python开发IDE工具VSCode-CSDN博客

Python与人工自能36——排序算法

一、学习排序算法的目的

理解算法思维基础

排序算法是计算机科学中最基本的算法类型之一。通过学习排序算法，能够深入理解算法设计的基本思路，如比较、交换、移动元素等操作，这些操作是构建更复杂算法的基石。

例如，在处理搜索算法时，很多时候预先对数据进行排序可以大大提高搜索效率，像二分搜索算法就要求数据是有序的。

提升程序性能优化意识

不同的排序算法在时间复杂度和空间复杂度上有所不同。了解这些特性可以帮助程序员在面对实际问题时，根据数据规模、数据特点和硬件资源等因素选择最合适的排序算法，从而优化程序的性能。

比如，在处理大规模数据时，时间复杂度为的排序算法（如快速排序、归并排序）通常比时间复杂度为的算法（如冒泡排序、选择排序）更高效。

应用于数据处理和分析

在实际的数据处理场景中，如数据库管理、数据分析软件等，经常需要对数据进行排序操作。排序可以使数据更有规律，便于用户查看和进一步分析。

例如，在一个销售数据系统中，按照销售额对各个店铺进行排序，可以快速找出销售业绩最好和最差的店铺。

二、代码实现

冒泡排序

时间复杂度：在最坏情况下（数组是逆序的），冒泡排序的时间复杂度为O(n²)。最好情况下（数组已经有序），只需要进行一轮比较，没有交换操作，时间复杂度为O(n)。平均情况下，时间复杂度约为O(n²)。 空间复杂度：冒泡排序也是原地排序算法，空间复杂度为O(1)。

def bubble_sort(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]
   return arr

arr = bubble_sort([12,31,24,35,32,43,64,567,456,876,968,7,54632,45,435,346,45,74])
print(arr)

选择排序

时间复杂度：O(n²)，比较次数是n*(n-1)/2

空间复杂度：选择排序是一种原地排序算法，它只需要一个额外的变量用于交换元素，所以空间复杂度为O(1)

def selection_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

arr = selection_sort([12,31,24,35,32,43,64,567,456,876,968,7,54632,45,435,346,45,74])
print(arr)

插入排序

时间复杂度：在最坏情况下（数组是逆序的），插入排序的时间复杂度为O(n²)。最好情况下（数组已经有序），每个元素只需要比较一次就可以插入到正确位置，时间复杂度为O(n)。平均情况下，时间复杂度约为O(n²)。 空间复杂度：插入排序是原地排序算法，空间复杂度为O(1)。

def insertion_sort(arr):
    for i in range(1, len(arr)):
        current_value = arr[i]
        position = i
        while position > 0 and current_value < arr[position - 1]:
            arr[position] = arr[position - 1]
            position -= 1
        arr[position] = current_value
    return arr
arr = insertion_sort([12,31,24,35,32,43,64,567,456,876,968,7,54632,45,435,346,45,74])
print(arr)