排序算法：选择排序，分别用c++、java、python实现

选择排序介绍

选择排序（Selection Sort）是一种简单的比较排序算法，它的工作原理如下：

1. 分区: 将待排序的数组分成两个部分，一个部分是已排序的子数组，另一个部分是未排序的子数组。初始时，已排序的子数组为空，而未排序的子数组包含整个数组。

2. 选择最小值: 从未排序的子数组中找到最小（或最大，根据排序顺序而定）的元素。

3. 交换: 将找到的最小值与未排序子数组的第一个元素交换，将其放入已排序的子数组的末尾。

4. 重复: 重复上述步骤，依次选择未排序子数组中的下一个最小值，放入已排序的子数组中，直到未排序子数组为空。

5. 完成: 当未排序子数组为空时，整个数组已经排序完成。

选择排序的特点：

• 它的实现非常简单，容易理解。
• 它的时间复杂度为O(n^2)，其中n是待排序数组的长度，这使得它在大型数据集上的性能相对较差。
• 由于它交换的次数相对较少，所以在某些情况下，它可能比其他简单排序算法（如冒泡排序）略快。

虽然选择排序在实际应用中不如高级排序算法（如快速排序或归并排序）高效，但它在理解排序算法的工作原理时很有用，通常用于教学或小型数据集的排序。

与其他排序算法比较

下面是对选择排序、冒泡排序、快速排序和归并排序的比较，使用表格形式呈现：

排序算法	平均时间复杂度	最坏情况时间复杂度	稳定性	额外空间	主要优点	主要缺点
选择排序	O(n^2)	O(n^2)	不稳定，相同元素的相对位置可能会改变	O(1)	简单易懂，适用于小型数据集	性能较差，不适用于大型数据集
冒泡排序	O(n^2)	O(n^2)	稳定，相同元素的相对位置不会改变	O(1)	简单易懂，适用于小型数据集	性能较差，不适用于大型数据集
快速排序	O(n*log(n))	O(n^2)	不稳定，相同元素的相对位置可能会改变	O(log(n))	平均情况下性能优秀，适用于大型数据集	最坏情况下性能较差
归并排序	O(n*log(n))	O(n*log(n))	稳定 ，相同元素的相对位置不会改变	O(n)	稳定且性能稳定，适用于大型数据集	需要额外空间，递归实现可能占用栈空间

c++实现

#include<iostream>
using namespace std;const int MAXN=10001;
int main(){int n=8,k,i,j;float temp,a[MAXN];a[1]=10;a[2]=6;a[3]=7;a[4]=1;a[5]=2;a[6]=16;a[7]=18,a[8]=9;for(i=1;i<=n;i++){k=i;for(j=i+1;j<=n;j++){if(a[j]<a[k]){k=j;}}if(k!=i){temp = a[i];a[i] = a[k];a[k]=temp;}}for(i=1;i<=n;i++){cout<<a[i]<<" ";}return 0;
}

java实现

public class SelectionSort {public static void selectionSort(float[] arr) {int n = arr.length;for (int i = 0; i < n; i++) {int minIndex = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}if (minIndex != i) {float temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}}public static void main(String[] args) {float[] a = {10, 6, 7, 1, 2, 16, 18, 9};selectionSort(a);for (float num : a) {System.out.print(num + " ");}}
}

python 实现

def selection_sort(arr):n = len(arr)for i in range(n):min_index = ifor j in range(i + 1, n):if arr[j] < arr[min_index]:min_index = jif min_index != i:arr[i], arr[min_index] = arr[min_index], arr[i]return arrif __name__ == "__main__":a = [10, 6, 7, 1, 2, 16, 18, 9]sorted_a = selection_sort(a)print(sorted_a)