文
章
目
录
章
目
录
一、前言
本文主要介绍Java实现选择排序经典代码和具体的算法思路。
选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。
二、内容
2.1 思路
选择排序的思路就是将数组视为两部分：已排序区间和未排序区间。然后，在未排序区间中找到最小元素，放到已排序区间的起始位置，再从剩余未排序区间元素中继续寻找最小元素，再放到已排序区间的末尾。以此类推，直到所有元素均排序完毕。
简单地说，选择排序就是遍历数组，找到最小元素，存放到数组的起始位置。然后再从剩下的元素中继续寻找最小元素，再放到数组的第二个位置，以此类推。
选择排序的基本思想步骤如下：
第一次：从arr[0]~arr[n-1]中选取最小值，与arr[0]进行交换；
第二次：从arr[1]~arr[n-1]中选取最小值，与arr[1]进行交换；
第三次：从arr[2]~arr[n-1]中选取最小值，与arr[2]进行交换；
…
第 i 次：从arr[i]~arr[i-1]中选取最小值，与arr[i]进行交换；
总共通过n-1次，可以得到从小到大的有序序列。
以序列：{8, 3, 2, 1, 7, 4, 6, 5} 为例！分步骤图解如下：
2.2 代码实现步骤
假设待排序数组 arr 的元素个数为 n 。
选择排序的步骤如下：
- 初始时，将整个数组视为未排序区间。同时已排序区间为空，已排序区间末尾位置的下标
i指向 0； - 接着，在未排序区间中找到最小的元素，我们用
minIndex来记录当前未排序区间中最小元素的下标。 - 将找到的最小元素添加到已排序区间的末尾位置，即
swap(arr, i, minIndex)。 - 将已排序区间的末尾扩展一个元素，也就是
i++，此时继续去未排序区间中寻找当前最小值元素，再将其添加到已排序区间的末尾位置，以此类推。 - 直到未排序区间变为空，已排序区间变成整个数组。
具体的，我们用两层for循环来模拟：
- 外层循环中，循环变量
i从0遍历到n-2，表示已排序区间的末尾位置的下标 - 内层循环中，循环变量
j从i+1遍历到n-1，用于遍历待排序部分的元素，找到最小值。 - 当我们在内层循环中找到当前待排序部分的最小值元素后，将其赋给
arr[i]，表示将最小值元素添加到已排好序的序列的末尾。
逐渐的，已排好序的序列末尾会是一个递增的趋势。
2.3 代码
首先说明，在代码中会使用到自定义的 swap()，该方法将数组中指定下标的两个数据元素进行交换操作。定义如下：
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
下面是选择排序算法的Java代码经典实现方式。
public static void selectionSort(int[] arr) {
// 数组的长度为 n
int n = arr.length;
// 处理特殊情况
if(arr == null || n < 2) {
return;
}
// i 指向当前已排序区间的末尾位置
for(int i = 0; i <= n-2; i++) {
// 在未排序区间中寻找最小元素的下标，并记录到 minIndex 中
int minIndex = i;
// j 用于遍历未排序区间
for(int j = i+1; j <= n-1; j++) {
// 寻找最小值元素的下标
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
// 在每轮遍历完未排序区间后，
// minIndex 指向的就是未排序区间中最小元素的下标，
// 将其指向的数据元素放到已排好序的序列的末尾
// 也就是将 arr[i] 与 arr[minIndex] 进行交换
swap(arr, i, minIndex);
}
}
三、总结
以上就是以上就是Java实现选择排序经典代码和算法思路的全部内容。
