选择排序算法

提示

1. 基本原理：选择排序算法通过在每次迭代中选择未排序列表中的最小元素，并将其置于未排序列表的起始位置来对数组进行排序。
2. 执行步骤：首先设定列表中的第一个元素为最小值，然后与其余元素比较，找到实际的最小值，并将其置于适当位置；接着对剩余的未排序列表重复此过程。
3. 复杂度分析：选择排序在所有情况下的时间复杂度均为 O(n²)，空间复杂度为 O(1)，是一种不稳定的排序算法。

选择排序是一种排序算法，它在每次迭代中从未排序的列表中选择最小的元素，并将该元素放置在未排序列表的开始位置。

选择排序的工作原理

1. 将第一个元素设为 最小值。

   

2. 将 最小值 与第二个元素比较。如果第二个元素小于 最小值，则将第二个元素设为 最小值。

   将 最小值 与第三个元素比较。同样，如果第三个元素更小，则将 最小值 指定为第三个元素，否则不做任何操作。这个过程一直进行到最后一个元素。

3. 每次迭代后，最小值 被放置在未排序列表的前面。

4. 每次迭代，索引都从第一个未排序的元素开始。重复步骤 1 到 3，直到所有元素都放置在正确的位置上。

选择排序算法

selectionSort(array, size)
  重复 (size - 1) 次
  将第一个未排序的元素设为最小值
  对每个未排序的元素
    如果 element < currentMinimum
      将 element 设为新的最小值
  将最小值与第一个未排序的位置交换
end selectionSort

Python、Java 和 C/C++ 中的选择排序代码

Python Java C C++

# Python 中的选择排序


def selectionSort(array, size):

    for step in range(size):
        min_idx = step

        for i in range(step + 1, size):

            # 若要按降序排序，请在此行中将 > 更改为 <
            # 在每次循环中选择最小元素
            if array[i] < array[min_idx]:
                min_idx = i

        # 将最小值放置在正确位置上
        (array[step], array[min_idx]) = (array[min_idx], array[step])


data = [-2, 45, 0, 11, -9]
size = len(data)
selectionSort(data, size)
print('按升序排列的数组：')
print(data)

// Java 中的选择排序

import java.util.Arrays;

class SelectionSort {
  void selectionSort(int array[]) {
    int size = array.length;

    for (int step = 0; step < size - 1; step++) {
      int min_idx = step;

      for (int i = step + 1; i < size; i++) {

        // 若要按降序排序，请在此行中将 > 更改为 <
        // 在每次循环中选择最小元素
        if (array[i] < array[min_idx]) {
          min_idx = i;
        }
      }

      // 将最小值放置在正确位置上
      int temp = array[step];
      array[step] = array[min_idx];
      array[min_idx] = temp;
    }
  }

  // 驱动代码
  public static void main(String args[]) {
    int[] data = { 20, 12, 10, 15, 2 };
    SelectionSort ss = new SelectionSort();
    ss.selectionSort(data);
    System.out.println("按升序排列的数组： ");
    System.out.println(Arrays.toString(data));
  }
}

// C 语言中的选择排序

#include <stdio.h>

// 交换两个元素位置的函数
void swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

void selectionSort(int array[], int size) {
  for (int step = 0; step < size - 1; step++) {
    int min_idx = step;
    for (int i = step + 1; i < size; i++) {

      // 若要按降序排序，请在此行将 > 改为 <
      // 在每次循环中选择最小元素
      if (array[i] < array[min_idx])
        min_idx = i;
    }

    // 将最小值放置在正确位置上
    swap(&array[min_idx], &array[step]);
  }
}

// 打印数组的函数
void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    printf("%d  ", array[i]);
  }
  printf("\n");
}

// 驱动代码
int main() {
  int data[] = {20, 12, 10, 15, 2};
  int size = sizeof(data) / sizeof(data[0]);
  selectionSort(data, size);
  printf("按升序排列的数组：\n");
  printArray(data, size);
}

// C++ 中的选择排序

#include <iostream>
using namespace std;

// 交换两个元素位置的函数
void swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

// 打印数组的函数
void printArray(int array[], int size) {
  for (int i = 0; i < size; i++) {
    cout << array[i] << " ";
  }
  cout << endl;
}

void selectionSort(int array[], int size) {
  for (int step = 0; step < size - 1; step++) {
    int min_idx = step;
    for (int i = step + 1; i < size; i++) {

      // 若要按降序排序，请在此行将 > 改为 <
      // 在每次循环中选择最小元素
      if (array[i] < array[min_idx])
        min_idx = i;
    }

    // 将最小值放置在正确位置上
    swap(&array[min_idx], &array[step]);
  }
}

// 驱动代码
int main() {
  int data[] = {20, 12, 10, 15, 2};
  int size = sizeof(data) / sizeof(data[0]);
  selectionSort(data, size);
  cout << "按升序排列的数组：\n";
  printArray(data, size);
}

选择排序的复杂度

时间复杂度
最优情况	O(n²)
最坏情况	O(n²)
平均情况	O(n²)
空间复杂度	O(1)
---	---
稳定性	否
---	---

循环次数	比较次数
第1次	(n-1)
第2次	(n-2)
第3次	(n-3)
...	...
最后一次	1

比较次数: (n - 1) + (n - 2) + (n - 3) + ..... + 1 = n(n - 1) / 2 近似等于 n²。

复杂度 = O(n²)

通过观察循环的次数也可以简单分析复杂度。这里有2个循环，所以复杂度为 n*n = n²。

时间复杂度:

• 最坏情况复杂度: O(n²) 如果我们想对一个降序数组进行升序排序，那么就会发生最坏情况。
• 最优情况复杂度: O(n²) 发生在数组已经排序的情况下。
• 平均情况复杂度: O(n²) 发生在数组元素顺序杂乱（既不是升序也不是降序）的情况下。

选择排序在所有情况下的时间复杂度都是一样的。在每一步，你都需要找到最小元素并将其放置在正确的位置。在没有遍历完整个数组之前，最小元素是未知的。

空间复杂度:

空间复杂度为 O(1)，因为使用了额外的变量 temp。

选择排序的应用

选择排序适用于以下情况：

• 排序小型列表
• 交换成本不重要
• 必须检查所有元素
• 写入内存的成本很重要，如在闪存中（写入/交换的次数为 O(n)，与冒泡排序的 O(n²) 相比）

类似的排序算法

1. 冒泡排序
2. 快速排序
3. 插入排序
4. 归并排序