Skip to content

选择排序

选择排序

什么是选择排序

  1. 选择排序是一种简单且直观的排序算法。
  2. 其思想是： - 在未排序的序列中选择最小（大）的元素，把它放在序列的起始位置上。 - 然后再从剩余未排序的序列中继续选择小（大）的元素，放在已排序的末尾。 - 以此类推，直到全部待排序的数据元素排完。

选择排序的优点

  1. 选择排序的实现思路简单，易于理解和实现。
  2. 选择排序不需要占用额外的空间，节省资源，是一种原地排序的算法。

选择排序的适用场景

  1. 选择排序的思路简单，尽管它的时间复杂度相较于更优的算法来讲不占优势，但对一些数据规模少的数据集，使用选择排序会很简单，节省时间，提高效率，所以对于选择排序适用于数据类较小的情况。

  2. 由于选择排序的时间复杂度较高，对于数据量大的数据集，效率会非常低，所以不适合用于大规模的数据排序。

选择排序的实际应用场景

以下是选择排序的几个应用场景：

  • 部分有序数组：如果输入的数组已经部分有序，只有少量元素需要排序，那么此时可以使用选择排序的算法，因为交换次数相对较少，效率会相对提高一些。
  • 内存受限系统：选择排序是一种原地排序算法，不需要额外的空间存储排序结果，所以在内存受限的一些系统中有一定的应用价值。

选择排序的实现思路

  1. 遍历待排序数组，找出数组的最小值，记录其索引值，为之后的比较交换做准备。 

    # 找出数组的最小值
def findSmallest(arr):
    smallest = arr[0]  # 最小值
    smallest_index = 0  # 索引值
    for i in range(1, len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i
    return smallest_index
    2. 在剩余的未排序序列中寻找最小值，并将其与已找的最小值进行交换，添加到数组末尾。 

    smallest = findSmallest(arr)
newArr.append(arr.pop(smallest))

  2. 重复步骤 2，直到未排序序列为空，整体代码实现如下。 

    # 寻找最小值
def findSmallest(arr):
    smallest = arr[0]
    smallest_index = 0
    for i in range(1, len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i
    return smallest_index
# 循环遍历交换元素
def selectionSort(arr):
    newArr = []
    for i in range(len(arr)):
        smallest = findSmallest(arr)
        newArr.append(arr.pop(smallest))
    return newArr

选择排序的复杂度分析

时间复杂度

# 寻找最小值
def findSmallest(arr):
    for i in range(1, len(arr)):
        ...
    return smallest_index
# 循环遍历交换元素
def selectionSort(arr):
    for i in range(len(arr)):
        ...
    return newArr
  1. 选择排序的第一步是需要遍历整个数组，找出一个最小或最大值，所以第一层的循环时间复杂度为O(n)。
  2. 之后在未排序的列表中继续循环，把剩余元素与已选定的最大或最小值进行比较，第二层的循环还是O(n)。
  3. 根据嵌套相乘的计算方式，选择排序时间复杂度即为O(n^2^)。

空间复杂度

选择排序只需传入的数组参数，所以空间复杂度为O(1)。