插入排序(Insertion Sort)

发布于 2021-09-05  948 次阅读


3、插入排序(Insertion Sort)

插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

3.1 算法描述

一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:

  • 从第一个元素开始,该元素可以认为已经被排序;
  • 取出下一个元素,在已经排序的元素序列中从后向前扫描;
  • 如果该元素(已排序)大于新元素,将该元素移到下一位置;
  • 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
  • 将新元素插入到该位置后;
  • 重复步骤2~5。

 

import java.util.Arrays;
import java.util.Random;

/**
 * @Author Chengzhi
 * @Date 2021/9/3 16:17
 * @Version 1.0
 *
 * 插入排序
 */
public class InsertionSort {

    public static void main(String[] args) {
        //生成随机数组
        Random rd = new Random();
        int[] num = new int[10];
        for (int i = 0; i < 10; i++) {
            num[i] = rd.nextInt(100) + 1;
        }
        System.out.println(Arrays.toString(num));
        //进行插入排序
        InsertSort(num);
        System.out.println(Arrays.toString(num));
    }
    private static int[] InsertSort(int[] num){
        //从第一个元素开始,该元素可以认为已经被排序;
        //取出下一个元素,在已经排序的元素序列中从后向前扫描;
        //如果该元素(已排序)大于新元素,将该元素移到下一位置;
        //重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
        //将新元素插入到该位置后;
        //重复步骤2~5。
        int len = num.length;
        int preIndex, current;
        for(int i = 1; i < len; i++) {
            preIndex = i - 1;//preIndex 为前一个元素
            current = num[i];//
            while(preIndex >= 0 && num[preIndex] > current) {//防止越界并且已排序序列元素大于新元素
                num[preIndex + 1] = num[preIndex];//已排序序列元素后移,为新元素腾位置
                preIndex--;
            }
            num[preIndex + 1] = current;
        }
        return num;
    }
}

她喜欢所以就做咯