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

Java技术 潘老师 3个月前 (11-11) 84 ℃ (0) 扫码查看

一、前言

本文主要介绍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} 为例!分步骤图解如下:Java实现选择排序图解

2.2 代码实现步骤

假设待排序数组 arr 的元素个数为 n

选择排序的步骤如下:

  • 初始时,将整个数组视为未排序区间。同时已排序区间为空,已排序区间末尾位置的下标 i 指向 0;
  • 接着,在未排序区间中找到最小的元素,我们用 minIndex 来记录当前未排序区间中最小元素的下标。
  • 将找到的最小元素添加到已排序区间的末尾位置,即 swap(arr, i, minIndex)
  • 将已排序区间的末尾扩展一个元素,也就是 i++,此时继续去未排序区间中寻找当前最小值元素,再将其添加到已排序区间的末尾位置,以此类推。
  • 直到未排序区间变为空,已排序区间变成整个数组。

具体的,我们用两层for循环来模拟:

  • 外层循环中,循环变量 i0 遍历到 n-2,表示已排序区间的末尾位置的下标
  • 内层循环中,循环变量 ji+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实现选择排序经典代码和算法思路的全部内容。


版权声明:本站文章,如无说明,均为本站原创,转载请注明文章来源。如有侵权,请联系博主删除。
本文链接:https://www.panziye.com/java/11033.html
喜欢 (0)
请潘老师喝杯Coffee吧!】
分享 (0)
用户头像
发表我的评论
取消评论
表情 贴图 签到 代码

Hi,您需要填写昵称和邮箱!

  • 昵称【必填】
  • 邮箱【必填】
  • 网址【可选】