当前位置:   article > 正文

数据结构常见算法

数据结构常见算法

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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/498998
推荐阅读
相关标签
  

闽ICP备14008679号