数据结构常见算法

1. 排序算法

1.1 冒泡排序

冒泡排序是一种简单直观的排序算法，它重复地走访要排序的元素列，一次比较两个元素，如果它们的顺序错误就将它们交换过来。这个过程持续多次，每次都会将最大（或最小）的数"浮"到最后，因此称为冒泡排序。

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

1. 比较相邻的元素：从数组的第一个元素开始，依次比较相邻的两个元素。
2. 交换元素位置：如果前面的元素大于后面的元素，则交换它们的位置。
3. 重复进行步骤1和2：对数组中的所有相邻元素进行上述比较和交换，这样一轮操作完成后，最大的元素就会被"冒泡"到数组的末尾。
4. 重复以上步骤：重复执行步骤1到3，每次都会将当前未排序的部分中最大的元素放到正确的位置，直到整个数组排序完成。

冒泡排序的时间复杂度为 O(n^2)

代码示例：

def bubble_sort(arr):
    n = len(arr)
    # 遍历所有数组元素
    for i in range(n):
        # 最后 i 个元素已经排序好了，不需要再次比较
        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
13
14

1.2 快速排序

快速排序是一种高效的排序算法，它采用了分治法的思想。其基本思想是选择一个基准元素，然后将待排序的数组按照基准元素的大小分割成两个子数组，一个子数组中的元素都小于基准元素，另一个子数组中的元素都大于基准元素。然后对这两个子数组分别进行快速排序，直到整个数组排序完成。

下面是快速排序的基本步骤：

1. 选择基准元素：从数组中选择一个元素作为基准元素。通常选择第一个元素、最后一个元素或者数组中间的元素作为基准元素。
2. 分割数组：重新排列数组，所有比基准元素小的元素都移到基准元素的左边，所有比基准元素大的元素都移到基准元素的右边。在分割结束后，基准元素将位于最终排序数组的正确位置。
3. 递归排序：递归地对基准元素左边的子数组和右边的子数组进行快速排序。
4. 合并结果：不需要合并步骤，因为在分割过程中就已经完成了排序。

快速排序是一种原地排序算法，它不需要额外的空间来存储临时数组，因此具有较小的空间复杂度。其平均时间复杂度为 O(n log n)，其中 n 是要排序的元素个数。但在最坏情况下（当选择的基准元素不幸地是数组中最大或最小的元素），时间复杂度为 O(n^2)。尽管如此，在大多数情况下，快速排序仍然是最快的通用排序算法之一。

代码示例：

def quick_sout(arr):
    left = []
    right = []
    if len(arr) <= 1:
        return arr
    else:
        curr = arr[0]  # 选择第一个元素作为基准元素
        for i in range(1,len(arr)):
            if arr[i] <= curr:
                left.append(arr[i])  # 小于等于基准元素的子数组
            else:
                right.append(arr[i])  # 大于基准元素的子数组
    return quick_sout(left) + [curr] + right
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = quick_sout(arr)
print("排序后的数组:", sorted_arr)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1.3 归并排序

归并排序是一种基于分治思想的排序算法，它将待排序的数组分成两个子数组，然后分别对这两个子数组进行排序，最后将两个已排序的子数组合并成一个有序的数组。归并排序的核心思想是将一个大问题拆分成多个小问题，分别解决，然后将解决后的结果合并起来。

下面是归并排序的基本步骤：

1. 分割数组：将待排序的数组分成两个子数组，直到每个子数组的长度为 1，即数组无法再分割为更小的部分。
2. 合并子数组：将两个已排序的子数组合并成一个有序的数组。这个过程中，会不断比较两个子数组的第一个元素，将较小（或较大）的元素放入合并后的数组中，直到其中一个子数组为空。
3. 重复合并：不断重复以上合并步骤，直到整个数组排序完成。
   归并排序是一种稳定的排序算法，其时间复杂度为 O(n log n)，其中 n 是待排序数组的长度。它的主要优点是稳定且具有较好的性能，在处理大型数据集时表现良好。

你可以将归并排序比作整理一副扑克牌的过程，将一副乱序的牌分成两堆，然后分别将这两堆牌整理成有序的序列，最后再将这两堆有序的牌合并起来

代码示例：

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    # 将数组分成两半
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]
    
    # 递归地对左右两半进行归并排序
    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)
    
    # 合并排序好的左右两半
    return merge(left_half, right_half)

def merge(left, right):
    result = []
    left_index, right_index = 0, 0
    
    # 比较左右两半的元素，将较小的元素依次放入结果数组中
    while left_index < len(left) and right_index < len(right):
        if left[left_index] < right[right_index]:
            result.append(left[left_index])
            left_index += 1
        else:
            result.append(right[right_index])
            right_index += 1
    
    # 将剩余的元素依次放入结果数组中
    result.extend(left[left_index:])
    result.extend(right[right_index:])
    
    return result

# 测试示例
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = merge_sort(arr)
print("排序后的数组:", sorted_arr)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39