选择排序

// todo

思想

// todo

算法实现

Java 实现

package com.littlefxc.examples.algorithm;/** * 选择排序 * * @author fengxuechao * @date 2019/1/17 **/public class SelectionSort {
       private SelectionSort() {
       }    public static void sort(Comparable[] arr) {
           int n = arr.length;        for (int i = 0; i < n; i++) {
               // 寻找数组在区间[i, n)的最小值            int minIndex = i;            for (int j = i + 1; j < n; j++) {
                   if (arr[j].compareTo(arr[minIndex]) < 0) {
                       minIndex = j;                }            }            swap(arr, i, minIndex);        }    }    /**     * 交换元素在数组的中位置     *     * @param arr 被交换元素所在的数组     * @param i   被交换元素i的索引     * @param j   被交换元素j的索引     */    private static void swap(Object[] arr, int i, int j) {
           Object objTmp = arr[i];        arr[i] = arr[j];        arr[j] = objTmp;    }}

测试

package com.littlefxc.examples.algorithm;import org.junit.Test;/** * 测试选择排序 * * @author fengxuechao * @date 2019/1/17 **/public class SelectionSortTest {
       @Test    public void sort() {
           int N = 20000;        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);        SortTestHelper.testSort("com.littlefxc.examples.algorithm.SelectionSort", "sort", arr);    }}

输出

在这里插入图片描述

测试帮助类

package com.littlefxc.examples.algorithm;import java.lang.reflect.Method;/** * 测试帮助类 * * @author fengxuechao */public class SortTestHelper {
       private SortTestHelper() {
       }    /**     * 生成有n个元素的随机数组,每个元素的随机范围为[rangeL, rangeR]     *     * @param n     * @param rangeL     * @param rangeR     * @return     */    public static Integer[] generateRandomArray(int n, int rangeL, int rangeR) {
           assert rangeL <= rangeR;        Integer[] arr = new Integer[n];        for (int i = 0; i < n; i++) {
               arr[i] = new Integer((int) (Math.random() * (rangeR - rangeL + 1) + rangeL));        }        return arr;    }    /**     * 生成一个近乎有序的数组,     * 首先生成一个含有[0...n-1]的完全有序数组, 之后随机交换swapTimes对数据.
     * swapTimes定义了数组的无序程度:     * 
   
         * 
    swapTimes == 0 时, 数组完全有序
     * 
    swapTimes 越大, 数组越趋向于无序
     * 
   
     *     * @param n     * @param swapTimes     * @return     */    public static Integer[] generateNearlyOrderedArray(int n, int swapTimes) {
           Integer[] arr = new Integer[n];        for (int i = 0; i < n; i++) {
               arr[i] = new Integer(i);        }        for (int i = 0; i < swapTimes; i++) {
               int a = (int) (Math.random() * n);            int b = (int) (Math.random() * n);            int t = arr[a];            arr[a] = arr[b];            arr[b] = t;        }        return arr;    }    /**     * 打印arr数组的所有内容     *     * @param arr     */    public static void printArray(Object[] arr) {
           for (int i = 0; i < arr.length; i++) {
               System.out.print(arr[i]);            System.out.print(' ');        }        System.out.println();        return;    }    /**     * 判断arr数组是否有序     *     * @param arr     * @return     */    public static boolean isSorted(Comparable[] arr) {
           for (int i = 0; i < arr.length - 1; i++) {
               if (arr[i].compareTo(arr[i + 1]) > 0) {
                   return false;            }        }        return true;    }    /**     * 测试sortClassName所对应的排序算法排序arr数组所得到结果的正确性和算法运行时间     *     * @param sortClassName     * @param arr     */    public static void testSort(String sortClassName, String sortMethodName, Comparable[] arr) {
           // 通过Java的反射机制，通过排序的类名，运行排序函数        try {
               // 通过sortClassName获得排序函数的Class对象            Class sortClass = Class.forName(sortClassName);            // 通过排序函数的Class对象获得排序方法            Method sortMethod = sortClass.getMethod(sortMethodName, new Class[]{
   Comparable[].class});            // 排序参数只有一个，是可比较数组arr            Object[] params = new Object[]{
   arr};            long startTime = System.currentTimeMillis();            // 调用排序函数            sortMethod.invoke(null, params);            long endTime = System.currentTimeMillis();            if (!isSorted(arr)) {
                   throw new IllegalStateException(sortClassName + "." + sortMethodName + " failed!");            }            System.out.println(sortClass.getSimpleName() + "." + sortMethodName + " : " + (endTime - startTime) + "ms");        } catch (Exception e) {
               e.printStackTrace();        }    }}