选择排序算法对数组的元素进行排序。
在本文中，我们将研究核心算法以及如何在Python，Java，C++和C中实现它。

核心算法

选择排序算法非常简单。

• 首先设置i = 0，因为那是起点。

• 查找未排序子数组[i..end]的最小元素

• 然后，我们将其与a [i]位置的元素交换。

• 然后，我们增加i，并重复上述步骤，直到i == n

用伪代码，我们可以这样表示：

PROCEDURE SELECTION_SORT(arr):
  i = -1
  while i < size(arr):
      idx = find_min(arr[i+1..size(arr)])
      swap(i, idx)
      i++
  return arr

显示算法的工作

现在，将其应用于数组，以了解该算法的工作原理！

让我们考虑以下数组。

最初，未排序的数组如下所示：

选择排序开始

在第一次迭代中，我们从剩余的数组(来自{12，7，6，6，16，4})中找到了最小元素4。
现在，我们将arr [i]与4交换。

选择排序迭代1

在下一次迭代中，我们从子数组{7，6，16，12}中找到最小元素，即6。
因此，让我们交换6和7。

选择排序迭代2

现在，我们移至更新数组的下一个元素，并再次执行相同的步骤。

选择排序迭代3

在上一次迭代中，没有变化，因为7是其余子数组中的最小元素。

选择排序迭代4

现在终于到了数组的末尾，现在已经对整个数组进行了排序！

让我们应用选择排序算法对上述数组进行Python，C++和C排序。

选择在Python中排序

以下代码段显示了使用Python的算法的工作方式。

def find_min(arr, start, end):
  minimum = arr[start]
  min_idx = start
  for idx in range(start, end):
      if arr[idx] < minimum:
          minimum = arr[idx]
          min_idx = idx
  return min_idx

def selection_sort(arr):
  i = 0
  arr_size = len(arr)
  while i < arr_size:
      # Find minimum of remaining unsorted subarray
      min_idx = find_min(arr, i, arr_size)
      # Swap with arr[i]
      arr[min_idx], arr[i] = arr[i], arr[min_idx]
      i += 1
  return arr

a = [12, 7, 6, 16, 4]
print(selection_sort(a))

输出

[4, 6, 7, 12, 16]

选择Java排序

public class SelectionSort {
  int find_min(int arr[], int start, int end) {
      int min_idx = start;
      int minimum = arr[start];
      for (int i=start; i<end; i++) {
          if (arr[i] < minimum) {
              min_idx = i;
              minimum = arr[i];
          }
      }
      return min_idx;
  }

  void selection_sort(int arr[], int arr_len) {
      //Selection Sort on an Array
      //Pass by reference 
      int start = 0;
      int min_idx;
      while (start < arr_len) {
          min_idx = find_min(arr, start, arr_len);
          //Swap arr[start] and arr[min_idx]
          int temp = arr[start];
          arr[start] = arr[min_idx];
          arr[min_idx] = temp;
          start++;
      }
  }

  public static void main(String[] args) {
      int arr[] = {12, 7, 6, 16, 4};
      SelectionSort sel_sort = new SelectionSort();
      sel_sort.selection_sort(arr, 5);
      System.out.println("Array after sorting:");
      for (int i=0; i<5; i++) {
          System.out.printf("%d ", arr[i]);
      }
      System.out.println();
  }
}

将上面的代码另存为SelectionSort.java。

输出

Array after sorting:
4 6 7 12 16 

选择在C++中排序

这是C++中算法的另一种实现

#include <iostream>

using namespace std;

int find_min(int arr[], int start, int end) {
  int min_idx = start;
  int minimum = arr[start];
  for (int i=start; i<end; i++) {
      if (arr[i] < minimum) {
          min_idx = i;
          minimum = arr[i];
      }
  }
  return min_idx;
}

void selection_sort(int arr[], int arr_len) {
  //Selection Sort on an Array
  //Pass by reference 
  int start = 0;
  int min_idx;
  while (start < arr_len) {
      min_idx = find_min(arr, start, arr_len);
      //Swap arr[start] and arr[min_idx]
      int temp = arr[start];
      arr[start] = arr[min_idx];
      arr[min_idx] = temp;
      start++;
  }
}

int main() {
  int arr[] = {12, 7, 6, 16, 4};
  selection_sort(arr, 5);
  cout << "Array after sorting:\n";
  for (int i=0; i<5; i++) {
      cout << arr[i] << " ";
  }
  cout << endl;
  return 0;
}

输出

Array after sorting:
4 6 7 12 16 

在C语言中实现选择排序

#include <stdio.h>

int find_min(int arr[], int start, int end) {
  int min_idx = start;
  int minimum = arr[start];
  for (int i=start; i<end; i++) {
      if (arr[i] < minimum) {
          min_idx = i;
          minimum = arr[i];
      }
  }
  return min_idx;
}

void selection_sort(int arr[], int arr_len) {
  //Selection Sort on an Array
  int start = 0;
  int min_idx;
  while (start < arr_len) {
      min_idx = find_min(arr, start, arr_len);
      //Swap arr[start] and arr[min_idx]
      int temp = arr[start];
      arr[start] = arr[min_idx];
      arr[min_idx] = temp;
      start++;
  }
}

int main() {
  int arr[] = {12, 7, 6, 16, 4};
  selection_sort(arr, 5);
  printf("Array after sorting:\n");
  for (int i=0; i<5; i++) {
      printf("%d ", arr[i]);
  }
  printf("\n");
  return 0;
}

输出

Array after sorting:
4 6 7 12 16 

时间复杂度

由于该算法对数组执行2个循环，因此其时间复杂度为O(n ^ 2)。

如果不清楚，则表示数组执行的操作总数为" n"个元素：

(n +(n-1)+(n-2)+(n-3)+…+ 1)= n *(n + 1)/2 = O(n ^ 2)

因此，尽管这不是一个很好的排序算法，但它很容易实现，可用于对元素数量较少的数组进行排序。