选择排序

1. 选择排序算法
2. 选择排序示例
3. 选择排序算法的实现
4. 选择排序算法的复杂度

选择排序是一种简单的排序算法。它的工作原理是将数组分为两部分：已排序和未排序的子数组。选择排序在未排序子数组中找到最小的元素，并将其移动到排序子数组的最后一个索引。当交换操作的成本非常高时，就会用到它，因为在最大限度内，只需要 n 交换。

选择排序算法

假设我们有一个未排序的数组 A[]，包含 n 个元素。

选择排序示例

假设我们有数组：(5,3,4,2,1,6)。我们将使用选择排序算法对其进行排序。

• 第一次迭代

最小要素：A[4]=1；

交换(A[4],A[0])。数组变成：(1) (3,4,2,5,6)。

• 第二次迭代

最小要素：A[3]=2；

交换(A[3],A[1])。数组变成：(1,2) (4,3,5,6)。

• 第三次迭代

最小要素：A[3]=3；

交换(A[3],A[2])。数组变成：(1,2,3) (4,5,6)。

• 第四次迭代

最小要素：A[3]=4；

交换(A[3],A[3])。数组变成：(1,2,3,4) (5,6)。

• 第五次迭代

最小要素：A[4]=5；

交换(A[4],A[4])。数组变成：(1,2,3,4,5) (6)。

最后一个元素已经被排序了。我们得到的排序数组为：(1,2,3,4,5,6)

选择排序算法的实现

#include <bits/stdc++.h>
using namespace std;

void selectionSort(int arr[], int n) {
  for (int i = 0; i < n - 1; i++) {
    // Find the minimum element for index i
    int min = i;
    for (int j = i + 1; j < n; j++)
      if (arr[j] < arr[min]) min = j;
    // Put element in sorted position
    swap(arr[min], arr[i]);
  }
}
int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  selectionSort(arr, n);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

选择排序算法的复杂度

时间复杂度

• 平均情况

平均来说，在插入排序的第 i 次传递中，会进行 n-i 次比较。因此，如果有 n 次迭代，那么平均时间复杂度可以在下面给出。

(n-1) + (n-2) + (n-3) + ... + 1 = n*(n-1)/2

因此，时间复杂度为 [Big Theta]量级：O(n²). 它也可以通过计算循环次数来计算。总共有两个循环的 n 次迭代，所以复杂度为：n*n = n²。

• 最坏情况

最坏情况下的时间复杂度为 [Big O]：O(n²)。

• 最佳情况

最佳情况下的时间复杂度为 [Big Omega]：O(n²)。它与最坏情况下的时间复杂度相同。

空间复杂度

选择排序算法的空间复杂度为 O(1)，因为除了一个临时变量外，不需要额外的内存。