• 插入排序算法的原理与示例
  • 发布于 1周前
  • 27 热度
    0 评论
  • 果酱
  • 21 粉丝 58 篇博客
  •   
原理
外层循环:确定要与已排序元素进行比较的元素,它是未排序元素中的第一个元素
内层循环:将未排序元素中要比较的元素与已排序元素以从后到前的顺序、进行相邻元素的比较,较小元素放到前面

外层循环原理图

内层循环原理图

示例
package wxw.mengyuan;
/**
 * 堆代码 duidaima.com
 * 插入排序
 */
public abstract class InsertSorting {

  /**
   * 对数组中的元素进行排序
   *
   * 原理
   * (1) 外层循环:确定未排序元素中的第一个元素
   * (2) 内层循环:将该未排序元素与已排序元素从后到前一一比较
   *
   * @param arr 要排序的数组
   */
  public static void sort(Comparable[] arr) {
    // 外层循环:确定未排序元素中的第一个元素
    for (int i = 1; i < arr.length; i++) {
      // 内层循环:将该未排序元素与已排序元素从后到前一一比较
      for (int j = i; j > 0; j--) {
        if (greater(arr[j-1], arr[j])) {
          exch(arr, j-1, j);
        } else {
          // 当前一个元素比后一个元素小时,那么再前面的元素就不需要再比较了
          break;
        }
      }
    }
  }

  /**
   * 校验第一个元素是否比第二个元素大
   *
   * @param v 第一个元素
   * @param w 第二个元素
   */
  private static boolean greater(Comparable v, Comparable w) {
    return v.compareTo(w) > 0;
  }

  /**
   * 将数组中索引为i、j的两个元素交换位置
   *
   * @param arr 数组
   * @param i 索引i
   * @param j 索引j
   */
  private static void exch(Comparable[] arr, int i, int j) {
    Comparable temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }

}

用户评论