回顾篇之Java的插入排序

妖狐艹你老母 2021-06-24 16:09 291阅读 0赞

前一段时间看到了一片文章《为什么我们要像驯化小狗狗一样驯化算法》，就一直在想我是否需要重头开始做一遍Java的基本算法排序，无论自己现在水平几何，都要回顾这些经典的，值得回味的程序片段。

那么接下来我们就一睹为快了，看看你是否已经忘记了她，还是她依然活在你深深的脑海里。

package com.honzh.mwq.sort;
    
    /**
     * 插入排序（原则就是当前位置的数和前面位置的数进行比较，如果当前位置的数小于之前的数，则交换位置）.
     * 
     * @author qinge
     * 
     */
    public class Inserting {
    
    	public static void main(String[] args) {
    		// 数组元
    		int[] orgins = { 2, 1, 5, 4, 9, 8, 6, 7, 10, 3, 3 };
    		
    		// 排序前的数
    		for (int num : orgins) {
    			System.out.print(num + "、");
    		}
    		System.out.println();
    
    		// 从第二个位置开始，因为第一个位置和他前面的位置（0个位置）相比，肯定为最小
    		for (int index = 1; index < orgins.length; index++) { // 复杂度为数组元的长度，或者说n
    			// 当前数
    			int curValue = orgins[index];
    
    			// 前一位的下标
    			int preIndex = index - 1;
    
    			// 当前数和前一位数相比，如果小，则交换位置，当前数继续和前一位数的前一位相比
    			while (preIndex >= 0 && curValue < orgins[preIndex]) {// 复杂度为1+2+3+...+(n-1)
    				// 前一位数的下一位等于前一位的数
    				orgins[preIndex + 1] = orgins[preIndex];
    
    				// 前一位的数等于当前数
    				orgins[preIndex] = curValue;
    
    				// 继续（前一位的前一位）
    				preIndex = preIndex - 1;
    			}
    		}
    
    		// 排序后的数
    		for (int num : orgins) {
    			System.out.print(num + "、");
    		}
    	}
    
    }

看完感觉怎么样，你是否想起了她？