基础排序算法之直接选择排序

文章目录[x]
  1. 1:直接选择排序
  2. 1.1:1 基本思想
  3. 1.2:2 算法示例
  4. 1.3:3 算法实现(java)
  5. 1.4:运行结果

直接选择排序

直接选择排序算法属于选择选择排序的一种,也是初学者应该掌握的常用的排序算法。

1 基本思想

直接选择排序的基本思想是将指定排序位置与其他数组元素分别对比,如果满足条件就交换元素值。注意这里与冒泡排序的区别,不是交换相邻元素,而是把满足条件的元素与指定的排序位置交换(如从最后一个元素开始排序),这样排序好的位置逐渐扩大,最后整个数组都成为已排序好的格式。
这就好比有一个小学生,从包含数字 1-10 的乱序的数字堆中分别选择合适的数字,组成一个 1-10的排序,而这个学生首先从数字堆中选出 1,放在第一位,然后选出(注意这时数字堆中已经没有1了),放在第二位,依此类推,直到其找到数字 9,放到 8 的后面,最后剩下 10,就不用选择了,直接放到最后就可以了。

2 算法示例

每一趟从待排序的元素中选出最小(最大)的每一个元素,顺序地放在已排好序的数列的最后,直到全部待排序的数据元素排完。
例如

初始数组资源 【63 4 24 1 3 15】

第一趟排序后 【15 4 24 1 3】 63

第二趟排序后 【15 4 3 1】 24 63

第三趟排序后 【1 4 3】 15 24 63

第四趟排序后 【1 3】 4 15 24 63

第五趟排序后 【1】 3 4 15 24 63

3 算法实现(java)

/**
 * 直接选择排序算法
 * @author  Vincents
 * @url     https://vincents.top
 * @time    2020/09/02
 */
package ArraySortingAlgorithm;
//导入类
import java.util.Scanner;
//创建类
public class DirectSelectionSort {
    //主方法 权限修饰符 静态修饰符 返回值修饰符
    public static void main(String[] args) {
        //输入数组
        System.out.print("请输入一个数组(数组元素以空格隔开):");
        Scanner str = new Scanner(System.in);
        String[] arrs = null;
        arrs = str.nextLine().split(" ");   //吸取字符,以回车键结束,并将字符按空格分割存入数组
        str.close();    //释放内存
        int arr[] = new int[arrs.length];   //新建整型变量数组,数组长度为arr.length
        //将输入的值赋值给arr[]并输出
        System.out.print("原数组为:");
        for (int i = 0; i < arrs.length; i++) {
            arr[i] = Integer.valueOf(arrs[i]);
            System.out.print(arr[i] + " ");
        }
        System.out.print("\n");     //换行
        //创建直接排序类的对象
        DirectSelectionSort sorter = new DirectSelectionSort();
        //调用排序对象的方法将数组排序
        sorter.directly(arr);
    }
    /**
     * 直接选择排序
     * @param arr
     * 要排序的数组
     */
    private void directly(int[] arr) {
        int index = 0;
        for (int i = 1; i < arr.length; i++) {
            index = 0;
            for (int j = 0; j <= arr.length-i; j++) {
                //假设arr[index]最小
                if(arr[index] < arr[j] ) {
                    index = j;
                }
            }
            //元素交换
            int temp = arr[arr.length-i];       //依次把末尾元素保存到临时变量值
            arr[arr.length-i] = arr[index];     //依次将最大的元素保存到末尾元素
            arr[index] = temp;                  //依次将末尾元素保存到最大的元素位置
        }
        showArray(arr);                         //输出排序后的数组元素
    }
    /**
     * 显示数组中的所有元素
     * @param arr
     * 要显示的元素
     */
    private void showArray(int[] arr) {
        System.out.print("排序后的数组:");
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.print("\n");                 //换行
    }
}

运行结果

avatar

点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像

Title - Artist
0:00