插入排序

//todo

思想

//todo

Java 实现

算法实现

package com.littlefxc.examples.algorithm;/** * 插入排序 * * @author fengxuechao * @date 2019/1/17 **/public class InsertionSort {
       private InsertionSort() {
       }    /**     * 经过测试选择"插入排序写法 3"     *     * @param arr     */    public static void sort(Comparable[] arr) {
           sort3(arr);    }    /**     * 插入排序:对区间[left,right]进行排序     *     * @param arr     * @param left     * @param right     */    public static void insertionSort(Comparable[] arr, int left, int right) {
           for (int i = left + 1; i <= right; i++) {
               Comparable key = arr[i];            int j = i - 1;            while (j > left && arr[j].compareTo(key) > 0) {
                   arr[j + 1] = arr[j];                j--;            }            arr[j] = key;        }    }    /**     * 插入排序写法 3     *     * @param arr     */    public static void sort3(Comparable[] arr) {
           for (int j = 1; j < arr.length; j++) {
               Comparable key = arr[j];            int i = j - 1;            while (i >= 0 && arr[i].compareTo(key) > 0) {
                   arr[i + 1] = arr[i];                i--;            }            arr[i + 1] = key;        }    }    /**     * 插入排序写法 2     *     * @param arr     */    public static void sort2(Comparable[] arr) {
           for (int i = 0; i < arr.length; i++) {
               for (int j = i; j > 0 && (arr[j].compareTo(arr[j - 1]) < 0); j--) {
                   swap(arr, j, j - 1);            }        }    }    /**     * 插入排序写法 1     *     * @param arr     */    public static void sort1(Comparable[] arr) {
           for (int i = 0; i < arr.length; i++) {
               for (int j = i; j > 0; j--) {
                   if (arr[j].compareTo(arr[j - 1]) < 0) {
                       swap(arr, j, j - 1);                }            }        }    }    /**     * 交换元素在数组的中位置     *     * @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;import java.util.Arrays;/** * 测试插入排序 * * @author fengxuechao */public class InsertionSortTest {
       /**     * 比较选择排序     */    @Test    public void sort() {
           int N = 20000;        Integer[] arr1 = SortTestHelper.generateRandomArray(N, 0, 10000);        Integer[] arr2 = Arrays.copyOf(arr1, arr1.length);        Integer[] arr3 = Arrays.copyOf(arr1, arr1.length);        Integer[] arr4 = Arrays.copyOf(arr1, arr1.length);        System.out.println("完全无序的数组排序");        SortTestHelper.testSort("com.littlefxc.examples.algorithm.InsertionSort", "sort1", arr1);        SortTestHelper.testSort("com.littlefxc.examples.algorithm.InsertionSort", "sort2", arr2);        SortTestHelper.testSort("com.littlefxc.examples.algorithm.InsertionSort", "sort3", arr3);        SortTestHelper.testSort("com.littlefxc.examples.algorithm.SelectionSort", "sort", arr4);    }    /**     * 用插入排序和选择排序比较近乎有序的数组之间的性能     */    @Test    public void sortNearlyOrderedArray() {
           int N = 20000;        Integer[] arr1 = SortTestHelper.generateNearlyOrderedArray(N, 1);        Integer[] arr2 = Arrays.copyOf(arr1, arr1.length);        Integer[] arr3 = Arrays.copyOf(arr1, arr1.length);        Integer[] arr4 = Arrays.copyOf(arr1, arr1.length);        System.out.println("近乎有序的数组排序");        SortTestHelper.testSort("com.littlefxc.examples.algorithm.InsertionSort", "sort1", arr1);        SortTestHelper.testSort("com.littlefxc.examples.algorithm.InsertionSort", "sort2", arr2);        SortTestHelper.testSort("com.littlefxc.examples.algorithm.InsertionSort", "sort3", arr3);        SortTestHelper.testSort("com.littlefxc.examples.algorithm.SelectionSort", "sort", arr4);    }}

在这里插入图片描述

测试帮助类

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();        }    }}