Tyrone 的博客

经典排序算法-冒泡/插入/选择排序

发表于 更新于 分类于
本文字数： 2.2k 阅读时长 ≈ 2 分钟
冒泡、插入、选择排序

经典排序算法——冒泡、选择、插入

今天我们一起来回顾三种排序算法，这三种排序算法的平均时间复杂度都是 O(n^2)，都是属于原地排序的算法。

冒泡排序

首先学习的是冒泡排序算法，我们还是使用 3W 方法来学习，What? Why? How?

什么是冒泡排序？

冒泡排序指的是对于一组数据，只会操作相邻的两个数据，对其进行比较，判断是否满足大小关系，如果不满足则互换位置，一次冒泡至少会让一个数据移动到其该有的位置。

为什么要使用冒泡排序？

对于一种排序算法，其需要从实现复杂度，空间复杂度，时间复杂度上来理解，对于冒泡排序而言，其时间复杂度为 O（n^2），空间复杂度为 O(1)，且为原地的排序算法。

如何实现冒泡排序？

首先，我们可以通过一个例子来观察冒泡排序的具体细节。

这是一组未排序的数据：[9, 10, 2, 0, 2, 3, 0]

冒泡次数 结果
第一次 [9, 2, 0, 2, 3, 0, 10]
第二次 [2, 0, 2, 3, 0, 9, 10]
第三次 [2, 0, 2, 0, 3, 9, 10]
第四次 [0, 2, 0, 2, 3, 9, 10]
第五次 [0, 0, 2, 2, 3, 9, 10]
第六次 [0, 0, 2, 2, 3, 9, 10]
第七次 [0, 0, 2, 2, 3, 9, 10]

以上就是冒泡排序的详细细节。

从每次的排序过程中，我们可以看到，对于这组数组而言，其实是在构建有序范围和无序范围。例如，第一次冒泡，有序空间为：arr[6:6], 无序空间为：arr[0:6]

现在：我们可以基于以上的结论实现冒泡排序了，本次使用的是 Python 编程。

1
2
3
4
5
6
7
8
9
10
11
12
13
def bubble_sort(arr: list):
  """
  冒泡排序
  """
  n = len(arr)
  if n <= 1:
    return arr

  for i in range(n):
    for j in range(n-i-1):
      if arr[j] > arr[j+1]:
        arr[j], arr[j+1] = arr[j+1], arr[j]
  return arr

然后在 5，6， 7 次排序的过程中，我们发现数据已经在第 5 次排序完成了。

此时，我们可以进一步优化, 在一次冒泡中是否发生数据交换标识位来判断是否已经排序完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def bubble_sort(arr: list):
  """
  冒泡排序
  """
  n = len(arr)
  if n <= 1:
    return arr
 
  for i in range(n):
    exchange = False
    for j in range(n-i-1):
      if arr[j] > arr[j+1]:
        arr[j], arr[j+1] = arr[j+1], arr[j]
        exchange = True
    if not exchange:
      break
 
  return arr

以上就是冒泡排序的总结了

插入排序

在学习完冒泡排序后，我们接下来学习插入排序。

什么是插入排序呢？

我们通过一个问题来学习插入排序，一个有序的数组，如何插入一个数据，使得其仍然有序？插入排序便是这样的思想，在每次排序时，构建有序空间，将无序空间中的数据放置在有序空间中该有的位置（满足大小关系）。

同样，插入排序的时间复杂度为 o(n^2), 空间复杂度为 O（1）实现复杂度较于冒泡排序而言难度高一些。

我们还是通过一个例子来学习插入排序。

现在有一组未排序的数组 [9, 10, 2, 0, 2, 3, 0]。

这里也是通过一个例子来看一下插入排序的详细过程。

3031690552330_.pic_hd_副本

现在使用 python 进行编程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def insert_sort(arr: list):
    """
    插入排序
    """
    n = len(arr)
    
    for i in range(1, n):
        flag = arr[i]
        j = i-1
        
        while j >= 0 and flag < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = flag
    
    return arr

选择排序

接下来，我们学习最后一个排序算法是选择排序。

那么什么是选择排序呢？

选择排序的实现原理和插入排序较为类似，也分为有序区间和无序区间，但是每次选择排序都是找到未排序中最小的元素，将其放置已排序空间末尾。

其时间复杂度为 O(n^2), 空间复杂度为 O(1), 个人觉得实现复杂度较选择排序而言相对简单一些。

同样，我们还是使用一个例子，观察其排序细节来进行学习。

image-20230728233635871

在上面的例子中，我们可以看到，每次都查找未排序数组最小的值和有序数组末尾+1 的值进行交换，从而进行排序。

现在，我们使用 python 来实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def change_sort(arr: list):
  """
  选择排序
  """
    n = len(arr)

    for i in range(n):
        min_index = i
        min_value = arr[i]
        for j in range(i, n):
            if arr[j] < min_value:
                min_index = j
                min_value = arr[j]

        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

今天学习的三种排序算法，在实际应用中较少，但是对于小规模的数据，用起来非常高效。但是插入排序还是挺有用的。

-------------THANKS FOR READING-------------