初等排序之插入排序(Java)

素颜马尾好姑娘i 2022-02-02 09:36 166阅读 0赞

**1. 直接插入排序**

/** * 初始序列:5 4 3 2 9 8 * 第一趟:[4 5] 3 2 9 8 * 第二趟:[3 4 5] 2 9 8 * 第三趟:[2 3 4 5] 9 8 * 第四趟:[2 3 4 5 9] 8 * 第五趟:[2 3 4 5 8 9] * * @param array */
    	public static void insertSort(int[] array) { 
    		int len = array.length;
    		for (int i = 1; i < len; i++) {  // 控制排序次数
    			// 要插入有序序列的值
    			int temp = array[i];
    			int j;
    			// 遍历有序序列,和temp比较,寻找合适的位置
    			for (j = i - 1; j >= 0; j--) { 
    				if (array[j] > temp) { 
    					array[j + 1] = array[j]; // 元素后移
    				} else {  				// 否则,位置找到,跳出循环
    					break;
    				}
    			}
    			// 将temp插入
    			array[j + 1] = temp;
    			
    			// 打印每一次排序的结果
    			System.out.print("第" + i + "次排序: ");
    			outArray(array);
    		}
    	}
    
    	/** * 输出数组元素 * * @param array */
    	public static void outArray(int[] array) { 
    		for (int i = 0; i < array.length - 1; i++) { 
    			System.out.print(array[i] + " ");
    		}
    		System.out.println(array[array.length - 1]);
    	}

**2. 二分插入排序**

/** * 二分查找函数,返回插入下标 * * @param array * @param left * @param right * @param key * @return */
    	public static int binarySearch(int[] array, int left, int right, int key) { 
    		while (left <= right) { 
    			int mid = (left + right) >> 1;
    			int data = array[mid];
    			if (data > key) { 
    				right = mid - 1;
    			} else { 
    				left = mid + 1;
    			}
    		}
    		return left;
    	}
    
    	/** * 元素插入 * * @param array */
    	public static void insertSort(int[] array) { 
    		if (array == null) { 
    			return;
    		}
    		for (int i = 1; i < array.length; i++) { 
    			if (array[i] < array[i - 1]) { 
    				int temp = array[i];
    				int insertIndex = binarySearch(array, 0, i, array[i]);// 获取array[i]的插入下标
    				for (int j = i - 1; j >= insertIndex; j--) {  // 移动元素
    					array[j + 1] = array[j];
    				}
    				array[insertIndex] = temp; // 插入元素
    			}
    			System.out.print("第" + i + "次排序: ");
    			printArray(array);
    		}
    	}
    
    	/** * 打印数组元素 * * @param array */
    	public static void printArray(int[] array) { 
    		for (int i = 0; i < array.length; i++) { 
    			System.out.print(array[i] + " ");
    		}
    		System.out.println();
    	}

![在这里插入图片描述][20190511095305325.png]

[20190511095305325.png]: /images/20220202/d2eb73a83d894c229827b5a798516512.png