一、算法介绍
选择排序是一种简单直观的排序算法，其基本思想是通过遍历待排序序列，每次从剩余未排序的元素中选择当前最小（或最大）的元素，然后将其放到已排序序列的正确位置上。此种算法的排序效率不高，不适合大规模数据集的排序处理，算法的操作时间复杂度较高，比较的次数较多。但是空间复杂度低，一般是常数级别内空间即可完成排序。
选择排序是一种初级排序算法。
原理与步骤：
- 初始化：给定一个待排序的数组 A，包含 n 个元素。
- 遍历并选择最小（或最大）元素：从数组的第一个元素开始，依次遍历剩余未排序的部分，寻找当前范围内最小（或最大）的元素。这一步通常通过一个额外的变量来记录当前找到的最小（或最大）元素的索引。
- 交换：将找到的最小（或最大）元素与数组的第一个未排序位置（即当前遍历到的位置）进行交换。这样，当前位置就被正确地放置了当前范围内的最小（或最大）值。
- 迭代：继续上述过程，每次遍历范围缩小一位（即从第二个未排序位置开始，直到最后一个未排序位置），每次找出剩余部分的最小（或最大）元素并与对应的未排序位置交换。重复这个过程，直到整个数组都被遍历过，即所有的元素都经过了一次排序。
时间复杂度与空间复杂度：
- 时间复杂度：选择排序的时间复杂度在最坏、最好和平均情况下都是 O(n²)，其中 n 为数组的长度。这是因为无论输入数据如何排列，都需要进行 n-1 轮比较和最多 n-1 次交换。由于每轮都要遍历剩余未排序的所有元素，导致其效率较低，尤其不适合处理大规模数据。
- 空间复杂度：选择排序是原地排序算法，只需要常数级别的额外空间用于临时存储索引，因此其空间复杂度为 O(1)
稳定性：
- 选择排序不是稳定的排序算法。当存在相等的元素时，它们之间的相对顺序可能会在排序过程中改变，因为选择排序会直接将找到的最小（或最大）元素与当前未排序位置的元素交换，不考虑它们是否相等。
实际应用场景：
- 数据规模较小：当需要排序的数据量非常有限时，选择排序的 O(n²) 时间复杂度带来的性能影响可能并不显著。在这种情况下，选择排序的简洁实现和无需额外空间的优势使其成为一种可行的选择。
- 内存限制严重：在内存资源极其受限的环境中，选择排序作为原地排序算法，不需要额外的存储空间来辅助排序，这对于无法承受较大内存开销的系统来说尤为关键。
- 特定硬件或嵌入式系统：在某些特定的硬件平台或嵌入式系统中，复杂的排序算法可能难以高效地实现或硬件支持不足。此时，选择排序由于其简单性和对硬件要求较低，可能成为一种更为实际的选择。
- 初学者算法实践：因为选择排序算法本身较为简单，容易理解，适合用来作为案例，用来理解排序中的比较、交换等概念，笔者学习的第一个算法就是选择排序算法
二、代码实践
问题：求一个具有N个数的数组中第K个最大者的值
代码如下：
package com.datastructures;
import java.util.Arrays;
/**
* 查找数组中第k大的元素,使用选择排序
* @author hulei
* @date 2024/4/27 8:55
*/
public class SelectSolution {
/**
* 查询第k大的元素
* 这里使用了选择排序算法，先找到数组中最大值，然后把它放到数组的第一个位置，然后再找到第二大值，把它放到数组的第二个位置，以此类推，直到找到第k大的元素。
* 时间复杂度O(n^2)
*/
public static int queryKthLargest(int[] arr,int k) {
//i=0时,把整个数组的最大值放到arr[0]的位置;i=1时,把整个数组的第二大值放到arr[1]的位置,以此类推
for (int i = 0; i < k; i++) {
//先设置最大值索引为第一个元素索引,即maxIndex=0
int maxIndex = i;
//这个for循环找出整个数组中的最大值,然后把maxIndex更新为最大值索引
for (int j = i + 1; j < arr.length; j++) {
if (arr[maxIndex] < arr[j]) {
maxIndex = j;
}
}
//arr[i]此时已经不是当前比较范围内的最大值了,先临时保存起来
int temp = arr[i];
//把当前比较范围内整个数组的最大值放到arr[i]的位置
arr[i] = arr[maxIndex];
//把temp放到原arr[i]的位置
arr[maxIndex] = temp;
}
//打印排序交换位置后的数组
System.out.println("排序后的数组：" + Arrays.toString(arr));
//最后返回arr[k-1]即为第k大元素,如第五大的元素，它的索引位置应该是4
return arr[k-1];
}
public static void main(String[] args) {
int[] arr = {15, 34, 9,71, 23, 12, 19, 21, 5, 6, 4,8,11,16,3,32,59,38,27};
//排序前的数组
System.out.println("排序前的数组：" + Arrays.toString(arr));
int k = 6;
int kthLargest = queryKthLargest(arr, k);
System.out.println("第" + k + "大的元素是：" + kthLargest);
}
}
第6大的值
第9大的值
通过结果可以看到
当我们要求第k大的值时，数组位置只交换到第K个位置，即把整个数组中的数按照从大到小顺序依次交换位置排序出来，并且只排序到第K大的元素
注意数据集几百个使用此排序适用，数据集很大时，此排序就不适合了
笔者这里测试了下，生成10000000万个随机数字数据集
package com.datastructures;
import java.util.Arrays;
import java.util.HashSet;
import java.util.concurrent.ThreadLocalRandom;
/**
* 查找数组中第k大的元素,使用选择排序
* @author hulei
* @date 2024/4/27 8:55
*/
public class SelectSolution {
/**
* 查询第k大的元素
* 这里使用了选择排序算法，先找到数组中最大值，然后把它放到数组的第一个位置，然后再找到第二大值，把它放到数组的第二个位置，以此类推，直到找到第k大的元素。
* 时间复杂度O(n^2)
*/
public static int queryKthLargest(int[] arr,int k) {
//i=0时,把整个数组的最大值放到arr[0]的位置;i=1时,把整个数组的第二大值放到arr[1]的位置,以此类推
for (int i = 0; i < k; i++) {
//先设置最大值索引为第一个
int maxIndex = i;
//这个for循环找出整个数组中的最大值,然后把maxIndex更新为最大值索引
for (int j = i + 1; j < arr.length; j++) {
if (arr[maxIndex] < arr[j]) {
maxIndex = j;
}
}
//arr[i]此时已经不是当前比较范围内的最大值了,先临时保存起来
int temp = arr[i];
//把当前比较范围内整个数组的最大值放到arr[i]的位置
arr[i] = arr[maxIndex];
//把temp放到原arr[i]的位置
arr[maxIndex] = temp;
}
//打印排序交换位置后的数组
System.out.println("排序后的数组：" + Arrays.toString(arr));
//最后返回arr[k-1]即为第k大元素,如第五大的元素，它的索引位置应该是4
return arr[k-1];
}
public static int[] getArray(){
int[] randomNumbers = new int[10000000];
HashSet<Integer> generated = new HashSet<>(); // 用于存放已生成的随机数
for (int i = 0; i < 10000000; i++) {
int num;
do {
num = ThreadLocalRandom.current().nextInt(1, 10000001); // 生成1到10000000范围内的随机整数
} while (!generated.add(num)); // 保证不重复
randomNumbers[i] = num;
}
return randomNumbers;
}
public static void main(String[] args) {
int[] arr = getArray();
//排序前的数组
System.out.println("排序前的数组：" + Arrays.toString(arr));
int k = 5000;
int kthLargest = queryKthLargest(arr, k);
System.out.println("第" + k + "大的元素是：" + kthLargest);
}
}
数据集很大时，需要很久，这里只获取了第5000大的值，执行结束要几分钟如果是获取更靠后的值，则更慢