选择排序算法Java、Go、Python和Rust四种代码实现

选择排序是一种简单高效的排序算法，其工作原理是通过迭代找到数组未排序部分中最小的元素，并将其与未排序部分开头的元素交换。这个过程不断重复，直到整个数组排序完毕。

其工作原理如下：

  1. 它会遍历整个项目列表。
  2. 查找具有最小值的元素。
  3. 将此元素与列表中的第一个元素交换。
  4. 它重复此过程，现在选择剩余元素中具有最低值的元素。
  5. 它会继续这样的替换，直到整个列表排序完毕。

Java代码：

public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

Go代码：

func selectionSort(arr []int) []int {
  for i := 0; i < len(arr)-1; i++ {
    minIndex := i
    for j := i + 1; j < len(arr); j++ {
      if arr[j] < arr[minIndex] {
        minIndex = j
      }
    }
    if i != minIndex {
      arr[i], arr[minIndex] = arr[minIndex], arr[i]
    }
  }
  return arr
}


Go代码在遍历数组的语法上与Java相似。

下面是代码的详细说明：

  • 外循环：遍历数组中除最后一个元素外的每个元素。
  • 内循环：从当前元素的索引 + 1 开始遍历数组中的其余元素。
  • 在内循环中，如果当前元素小于目前找到的最小元素，则更新最小索引。
  • 交换：内循环结束后，如果当前元素的索引不是最小索引，则交换这些索引处的元素。

以下是一些需要考虑的补充要点：

  • 通过改变 arr 片的类型和内循环中使用的比较运算符，可以轻松地将此实现与其他数据类型配合使用。
  • 您可以通过添加逻辑来跟踪交换过程中元素的原始位置，从而修改代码使其保持稳定。
  • 如果数据集较大或性能要求较高，可以考虑使用其他排序算法，如标准库提供的 sort.Ints。
  • 选择排序并不是大型数据集最有效的排序算法。其他排序算法（如 quicksort 或 mergesort）通常性能更高。


Python代码：

def selection_sort(array):

  for i in range(len(array) - 1):
    min_index = i
    for j in range(i + 1, len(array)):
      if array[j] < array[min_index]:
        min_index = j
    array[i], array[min_index] = array[min_index], array[i]
  return array


my_list = [64, 34, 25, 12, 22, 11, 90]
selection_sort(my_list)
print("Sorted array:", my_list)

本例使用 selection_sort 函数对数组进行升序排序。该算法的工作原理是从数组未排序部分迭代选择最小的元素，并将其与未排序部分的第一个元素交换。

Rust代码：

fn selection_sort<T: Ord>(arr: &mut [T]) {
  for i in 0..(arr.len() - 1) {
    let mut min_index: usize = i;
    for j in (i + 1)..arr.len() {
      if arr[j] < arr[min_index] {
        min_index = j;
      }
    }
    if i != min_index {
      arr.swap(i, min_index);
    }
  }
}

Rust代码在遍历数组的语法上与Python相似。
如果数据集较大或对性能要求较高，可以考虑使用标准库提供的其他排序算法，如 sort_by 或 sort_unstable。


需要注意的是，选择排序在最差和平均情况下的时间复杂度均为 O(n^2)，因此对于大型数据集来说效率很低。还有更高效的排序算法，如 quicksort 或 mergesort，在实际应用中通常更受欢迎。

特点：

  • 简单性——选择排序是最简单的排序算法之一，易于理解和实现。
  • 没有额外的内存——它是一种就地算法，这意味着它不需要额外的内存来存储排序的项目。
  • 对于小型集合有效- 对于小型项目列表，选择排序非常有效且高效。


以下是一些需要考虑的补充要点：

  • 选择排序是一种稳定的排序算法，这意味着相等元素的相对顺序会保持不变。
  • 选择排序有多种变体，如双向选择排序和带哨兵的选择排序，它们的性能特点可能略有不同。