python排序算法

排序算法

1.冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地比较相邻的两个元素，如果顺序不对，则交换它们。通过多次遍历数组，将最大（或最小）的元素逐渐"浮"到数组的末尾，从而实现排序。

以下是冒泡排序的基本步骤：

1. 从数组的第一个元素开始，比较它与相邻的后一个元素。
2. 如果顺序不正确，交换这两个元素的位置。
3. 继续比较下一个相邻的元素，重复上述步骤，直到遍历完整个数组。
4. 针对数组中的每个元素，依次执行上述步骤。

这样一次遍历后，最大（或最小）的元素会移动到数组的末尾。重复执行多次遍历，直到所有元素都按照顺序排列。

冒泡排序的时间复杂度为O(n^2)，其中n是数组的长度。由于它的比较和交换操作比较简单，因此在小规模数据的排序中具有一定的优势，但对于大规模数据的排序效率较低。

示例代码（python）：

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]

# 测试示例
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("排序后的数组：", arr)

1
2
3
4
5
6
7
8
9
10
11
12

该示例中，数组 [64, 34, 25, 12, 22, 11, 90] 经过冒泡排序后，输出为 [11, 12, 22, 25, 34, 64, 90]。

2.选择排序

选择排序（Selection Sort）是一种简单的排序算法。它将待排序数组分为已排序区和未排序区，每次从未排序区中选择最小（或最大）的元素，与已排序区的最后一个元素交换位置。

以下是选择排序的基本步骤：

1. 将整个数组分为已排序区和未排序区。
2. 每次从未排序区中选择最小（或最大）的元素，记录该元素的下标。
3. 交换该元素和未排序区的第一个元素的位置，将该元素加入到已排序区中。
4. 针对数组中的每个元素，依次执行上述步骤。

通过多次遍历，每次将最小（或最大）的元素加入到已排序区的末尾，实现排序。

选择排序的时间复杂度为O(n^2)，其中n是数组的长度。由于它的比较和交换操作比较简单，因此在小规模数据的排序中具有一定的优势，但对于大规模数据的排序效率较低。

示例代码（Python）：

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # 从未排序区中选择最小值的下标
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        
        # 将最小值移动到已排序区的末尾
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

# 测试示例
arr = [64, 34, 25, 12, 22, 11, 90]
selection_sort(arr)
print("排序后的数组：", arr)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

该示例中，数组 [64, 34, 25, 12, 22, 11, 90] 经过选择排序后，输出为 [11, 12, 22, 25, 34, 64, 90]。

3.插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法。它将待排序数组分为已排序区和未排序区，每次从未排序区选择一个元素，插入到已排序区的正确位置。

以下是插入排序的基本步骤：

1. 将整个数组分为已排序区和未排序区。
2. 从未排序区选择第一个元素，将其插入到已排序区的合适位置。
3. 比较该元素与已排序区中的元素，找到正确的插入位置。
4. 将该元素插入到正确的位置，并将已排序区的元素后移。
5. 针对数组中的每个元素，依次执行上述步骤。

通过多次遍历，将未排序区的元素逐个插入到已排序区的合适位置，实现排序。

插入排序的时间复杂度为O(n^2)，其中n是数组的长度。由于它的比较和移动操作较多，因此在小规模数据的排序中效率较高，但对于大规模数据的排序效率较低。

示例代码（Python）：

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        # 将比key大的元素后移
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]
            j -= 1
        # 插入key到正确位置
        arr[j+1] = key

# 测试示例
arr = [64, 34, 25, 12, 22, 11, 90]
insertion_sort(arr)
print("排序后的数组：", arr)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

该示例中，数组 [64, 34, 25, 12, 22, 11, 90] 经过插入排序后，输出为 [11, 12, 22, 25, 34, 64, 90]。

函数

函数的定义和调用函数

结构

def 函数名(参数1，参数2.....):
    函数体
    return True
1
2
3

传入参数的类型检查

def my_a(x):
    if not isinstance(x,(int,float)):
        raise TypeError ("i am sorry")
a = my_a(x)
print(a)
1
2
3
4
5

返回值

def sum_01():
    a = 1 
    b = 2
    return a,b
a,b = sum_01()
print(a)
print(b)
1
2
3
4
5
6
7

事实上，函数返回的是一个元组，多个变量可以同时接受以个元组

参数

函数的参数是用于接收函数调用时传递给函数的值或对象。在函数定义时，可以定义函数的参数列表，并在函数体内使用这些参数进行相应的操作。

函数的参数可以分为以下几种类型：

1. 位置参数（Positional Arguments）：也称为必需参数，按照定义时的顺序依次传入函数。调用函数时要求按照参数定义的顺序提供相应的参数值。

示例：

def greet(name, age):
    print(f"Hello, {name}! You are {age} years old.")

greet("Alice", 25)

1
2
3
4
5

这里的 name 和 age 就是位置参数，函数 greet 在调用时需要提供这两个参数，按照位置依次传入。

2. 关键字参数（Keyword Arguments）：通过指定参数名来传递参数值，可以乱序提供参数值。使用关键字参数时，不需要按照参数定义的顺序传递参数值。

示例：

def greet(name, age):
    print(f"Hello, {name}! You are {age} years old.")

greet(age=25, name="Alice")

1
2
3
4
5

这里通过指定参数名 age 和 name 来传递参数值，可以不按照定义时的顺序传入参数。

3. 默认参数（Default Arguments）：在函数定义时给参数指定一个默认值，如果在调用函数时没有传递该参数的值，则使用默认值。

示例：

def greet(name, age=30):
    print(f"Hello, {name}! You are {age} years old.")

greet("Alice")  # 使用默认值
greet("Bob", 25)  # 不使用默认值

1
2
3
4
5
6

这里的 age 参数通过给定默认值为 30 成为了默认参数，在调用函数时如果不提供 age 的值，则使用默认值。

4. 可变参数（Variable Arguments）：允许传递任意数量的参数，这些参数会被收集成一个元组或列表供函数内部使用。

示例：

def sum_numbers(*args):
    total = 0
    for num in args:
        total += num
    return total

result = sum_numbers(1, 2, 3, 4, 5)
print(result)

1
2
3
4
5
6
7
8
9

这里的 *args 允许传递任意数量的参数，函数内部将这些参数收集成元组 args，可以在函数内部进行遍历和处理。

5. 关键字可变参数（Keyword Variable Arguments）：允许传递任意数量的关键字参数，这些参数会被收集成一个字典供函数内部使用。

示例：

def print_info(**kwargs):
    for key, value in kwargs.items():
        print(key, ":", value)

print_info(name="Alice", age=25, city="New York")

1
2
3
4
5
6

这里的 **kwargs 允许传递任意数量的关键字参数，函数内部将这些参数收集成字典 kwargs，可以在函数内部进行遍历和处理。

函数的参数类型可以根据具体的需求进行选择和组合，灵活使用不同类型的参数可以提高函数的适用性和可扩展性。

解包，拆包

解包和拆包指的是将一个对象（通常是序列或者字典）拆分成单独的元素，或者将多个元素合并为一个对象的操作。在 Python 中，可以使用以下两种方式进行解包和拆包：

1. 序列解包：将序列中的元素拆分成单独的变量。拆分后变量的数量必须与序列中元素的数量相同。

示例：

a, b, c = [1, 2, 3]
print(a)  # 输出 1
print(b)  # 输出 2
print(c)  # 输出 3

1
2
3
4
5

这里通过将列表 [1, 2, 3] 解包成 a, b, c 三个变量。

2. 星号表达式：将一个序列拆分成多个部分，其中一部分绑定到一个变量，其余部分使用星号表达式进行拆分。

示例：

a, *b, c = [1, 2, 3, 4, 5]
print(a)  # 输出 1
print(b)  # 输出 [2, 3, 4]
print(c)  # 输出 5

1
2
3
4
5

这里使用星号表达式 *b 将列表中除了第一个元素和最后一个元素外的元素都拆分到 b 列表中。

对于字典，可以通过以下方式进行解包和拆包：

1. 字典解包：将字典中的键值对拆分成单独的变量。拆分后变量的数量必须与字典中键值对的数量相同。

示例：

my_dict = {"name": "Alice", "age": 25}
name, age = my_dict.items()
print(name)  # 输出 ('name', 'Alice')
print(age)  # 输出 ('age', 25)

1
2
3
4
5

2. 双星号表达式：将一个字典拆分成多个部分，其中一部分绑定到一个变量，其余部分使用双星号表达式进行拆分。

示例：

my_dict = {"name": "Alice", "age": 25, "city": "New York"}
name_age, **other_info = my_dict
print(name_age)  # 输出 "name", "age"
print(other_info)  # 输出 {"city": "New York"}

1
2
3
4
5

在 Python 的函数调用中，也常常使用解包和拆包。例如，可以使用 *args 和 **kwargs 来接收任意数量的位置参数和关键字参数，然后在函数内部对其进行拆包和处理。

示例：

def my_func(*args, **kwargs):
    for arg in args:
        print(arg)

    for key, value in kwargs.items():
        print(key, value)

my_list = [1, 2, 3]
my_dict = {"name": "Alice", "age": 25}

my_func(*my_list, **my_dict)

1
2
3
4
5
6
7
8
9
10
11
12

这里通过 *my_list 和 **my_dict 将列表 my_list 和字典 my_dict 拆包，可以将其作为参数传递给函数 my_func。然后在函数内部使用 *args 和 **kwargs 分别对传入的位置参数和关键字参数进行解包和处理。