?个人博客：www.hellocode.top
?Java知识导航：Java-Navigate
?CSDN：HelloCode.
?知乎：HelloCode
?掘金：HelloCode
⚡如有问题，欢迎指正，一起学习~~
选择排序是一种简单但低效的排序算法，其基本思想是每次从待排序序列中选出最小（或最大）的元素，然后将其放置在已排序序列的末尾（或开头）。通过逐步选择出最小（或最大）元素，将其插入到已排序序列中，从而逐步构建有序序列。
基本思想
- 将数组分为已排序区和未排序区。
- 在未排序区中找到最小（或最大）的元素。
- 将找到的最小（或最大）元素与未排序区的第一个元素交换位置，将该元素放入已排序区。
- 重复步骤 2 和 3，直到未排序区为空。
和插入排序很像，区别就在于选择和插入，根据动画体会一下，选择排序的重点是选择出未排序中最小（大）的，不断的加入到已排序区中（选择对的元素插入已排序区末尾）
代码实现
代码和插入排序可以对比着来写，也很简单，两层for循环，外层用来控制已排序的元素个数（选择好的待排序元素该放入的位置），内层for用来遍历选择出最小（大）的元素，具体代码如下：
下面展示Java和C两种版本（C语言版本由俺的女朋友小周提供?）
/**
* @author HelloCode
* @blog https://www.hellocode.top
* @date 2023年08月09日 21:21
*/
public class SelectionSort {
public static void main(String[] args) {
int[] arr = {2, 12, 42, 13, 43, 85, 91, 23, 12, 4, 5, 8, 1, 9, 88, 66, 33, 123};
System.out.println("排序前："+ Arrays.toString(arr));
selectionSort(arr);
System.out.println("排序后："+ Arrays.toString(arr));
}
public static void selectionSort(int[] arr){
// 两层for循环，外层i代表已排序的元素个数
for(int i = 0; i < arr.length - 1; i++){
// 内层 for 进行选择，在待排序的元素中选择最小的进行排序
int min = i;
for(int j = i + 1; j < arr.length; j++){
if(arr[j] < arr[min]){
// j更小，更新min
min = j;
}
}
// 将选择出的最小元素插入已排序元素中
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
}测试：
排序前：[2, 12, 42, 13, 43, 85, 91, 23, 12, 4, 5, 8, 1, 9, 88, 66, 33, 123]
排序后：[1, 2, 4, 5, 8, 9, 12, 12, 13, 23, 33, 42, 43, 66, 85, 88, 91, 123]//C语言实现
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
void Select_Sort(int* arr, int len)
{
assert(arr != NULL);
if (arr == NULL)
return ;
int minindex; //保存最小值的下标
for (int i = 0; i < len-1; i++) //趟数 总数少一趟
{
minindex = i; //每趟循环一进来，我们首先认为待排序序列的第一个值是最小的
for (int j = i + 1; j < len; j++) //从待排序序列的第二个值开始和arr[minindex]比较
{
if (arr[j] < arr[minindex]) //如果找到更小的数 则minindex
{
minindex = j;
}
}
if (i != minindex) //防止最小值就是自身时发生自己与自己交换
{
int tmp = arr[i]; // i 保存的是待排序序列的第一个值
arr[i] = arr[minindex];
arr[minindex] = tmp;
} //一趟只交换一次（与冒泡算法的区别）
}
}
void Show(int* arr, int len)
{
for (int i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
int arr[] = {2, 12, 42, 13, 43, 85, 91, 23, 12, 4, 5, 8, 1, 9, 88, 66, 33, 123};
int len = sizeof(arr) / sizeof(arr[0]);
Select_Sort(arr, len);
Show(arr, len);
return 0;
}//C++实现
#include <iostream>
#include <assert.h>
using namespace std;
void Select_Sort(int* arr, int len)
{
assert(nullptr != arr);
if (nullptr == arr)
return ;
int minindex; //保存最小值的下标
for (int i = 0; i < len - 1; i++) //趟数 总数少一趟
{
minindex = i; //每趟循环一进来，我们首先认为待排序序列的第一个值是最小的
for (int j = i + 1; j < len; j++) //从待排序序列的第二个值开始和arr[minindex]比较
{
if (arr[j] < arr[minindex]) //如果找到更小的数 则minindex
{
minindex = j;
}
}
if (i != minindex) //防止最小值就是自身时发生自己与自己交换
{
int tmp = arr[i]; // i 保存的是待排序序列的第一个值
arr[i] = arr[minindex];
arr[minindex] = tmp;
} //一趟只交换一次
}
}
void Show(int* arr, int len)
{
for (int i = 0; i < len; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
int main()
{
int arr[] = { 2, 12, 42, 13, 43, 85, 91, 23, 12, 4, 5, 8, 1, 9, 88, 66, 33, 123 };
int len = sizeof(arr) / sizeof(arr[0]);
Select_Sort(arr, len);
Show(arr, len);
return 0;
}优化
虽然选择排序的时间复杂度不容易通过优化得到显著的提升，但一些小优化可以改善算法的实际性能。
- 可以在内层循环中同时找到最小和最大元素，从而减少交换的次数。
- 可以在选择最小（大）元素时采用不同的方法来代替逐个遍历，提高效率。
总结
优点
- 简单易懂：选择排序是一种简单直观的排序算法，易于实现。
- 稳定性：在相等元素的情况下，选择排序是一种稳定的排序算法。
缺点
- 低效性：选择排序的时间复杂度为 O(n^2)，即使在最佳情况下也需要进行多次比较和交换，效率较低。
- 不适合大规模数据：由于时间复杂度的限制，选择排序不适合对大规模数据进行排序。
复杂度
时间复杂度
- 平均时间复杂度：O(n^2)
- 最好情况时间复杂度：O(n^2)
- 最坏情况时间复杂度：O(n^2)
- 空间复杂度：原地排序，空间复杂度为 O(1)。
使用场景
由于其低效性，选择排序在实际应用中较少使用。在需要排序的数据规模较小时，选择排序可能是一个合理的选择。然而，对于大规模数据，其他高效的排序算法（如快速排序、归并排序）通常更为适用。选择排序适用于教学和学习排序算法的基本原理，但在实际应用中，通常会选择更优的排序算法。
当使用选择排序时，应特别注意其时间和空间复杂度的说明是基于固定的数据集。在实际情况中，选择排序的性能可能因为一些特定因素而有所不同，因此在特定情况下选择排序可能表现更好。
1 条评论
打卡算法学习第五天！！！