排序算法 - 简单选择排序

基本思想

在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

操作方法

第一趟，从n 个记录中找出关键码最小的记录与第一个记录交换；
第二趟，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换；
以此类推…..
第i 趟，则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换，
直到整个序列按关键码有序。

算法流程图

selectProcess

代码

package main.java.com.study.sortingAalgorithm;

import main.java.com.study.utils.CommonUtils;

/**
 * @author: whb
 * @description: 选择排序
 */
public class SelectionSort {

    /**
     * 选择排序：每一趟在剩余未排序的若干记录中选取关键字最小的（也可以是最大的）记录作为有序序列中下一个记录。
     * 如第i趟选择排序就是在n-i+1个记录中选取关键字最小的记录作为有序序列中第i个记录。
     * 这样，整个序列共需要n-1趟排序。
     */
    public static void selctionSort(int[] numArr) {
        int length = numArr.length;
        //要遍历的次数（length-1）
        for (int i = 0; i < length - 1; i++) {
            //将当前下标定义为最小值下标
            int min = i;
            //遍历min之后的数据
            for (int j = i + 1; j < length - 1; j++) {
                //如果有小于当前最小值的元素，将它的下标赋值给min
                if (numArr[j] < numArr[min]) {
                    min = j;
                }
            }
            //如果min不等于i，则说明找到了真正的最小值
            if (min != i) {
                swap(numArr, min, i);
            }
        }
    }

    /**
     * 交换数组中两个元素的位置
     *
     * @param numArr
     * @param min
     * @param i
     */
    public static void swap(int[] numArr, int min, int i) {
        int temp = numArr[min];
        numArr[min] = numArr[i];
        numArr[i] = temp;
    }

    public static void main(String[] args) {
        int[] numArr = {27, 11, 13, 45, 34, 22, 19, 8, 3, 99, 74, 55, 88, 66};
        System.out.println("**************选择排序******************");
        System.out.println("排序前：");
        CommonUtils.display(numArr);
        System.out.println("排序后：");
        selctionSort(numArr);
        CommonUtils.display(numArr);
    }
}

CommonUtils工具类：

package main.java.com.study.utils;

/**
 * @author: whb
 * @description: 工具类
 */
public class CommonUtils {

    /**
     * 遍历打印
     *
     * @param numArr
     */
    public static void display(int[] numArr) {
        if (numArr != null && numArr.length > 0) {
            for (int num : numArr) {
                System.out.print(num + "  ");
            }
        }
        System.out.println("");
    }
}

测试结果

selectionSort