Java实现选择排序经典代码和算法思路

文
章
目
录

• 一、前言
• 二、内容
• 2.1 思路
• 2.2 代码实现步骤
• 2.3 代码
• 三、总结

一、前言

本文主要介绍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实现选择排序经典代码和算法思路的全部内容。