java数据结构与算法____插入排序

╰半夏微凉° 2022-04-15 00:50 209阅读 0赞

import java.util.Arrays;
     
    /**
     * @author God
     * 有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，
     * 但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,
     * 插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、
     * 个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。
     * 插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），
     * 而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
     * 插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
     */
    public class InsertionSort {
    	public static void main(String[] args) {
    		//定义简短数组方便查看
    		int[] ary = { 4, 3, 2, 1};
    		//遍历
    		for (int i = 1; i < ary.length; i++) {
    			//定义临时变量
    			int temp = ary[i];
    			System.out.println("临时变量temp =ary[i]__:"+temp+"___=ary[i]=__:"+ary[i]);
    			int j=0;
    			System.out.println("初始化的j__=:"+j);
    			for (j = i - 1; j >= 0 && temp < ary[j]; j--) {
    				System.out.println("循环内ary[j+1]=ary[j]____:ary[j+1]="+ary[j+1]+"___ary[j]="+ary[j]);
    				ary[j + 1] = ary[j];
    			}
    			ary[j + 1] = temp;
    			System.out.println("ary[j + 1] = temp___ary[j + 1]="+ary[j + 1]+"____temp="+temp);
    			System.out.println("第"+i+"一次遍历排序后为"+Arrays.toString(ary)+"\n__________________________________________");
    		}
    	}
    }