八大排序算法之直接插入排序（InsertionSort）八大排序算法之直接插入排序

常见的排序算法

文章图片

今天复习【直接插入排序】
核心思想：有序数组中找位置 -- 给无序数组第一个找位置
`

public class InsertionSort { // 核心思想：有序数组中找位置 -- 给无序数组第一个找位置 public void myInsertSort(int[] arr) { int len = arr.length; for (int i = 1; i < len; i++) { // 查找位置插入 -- 可能存在二分查找进行优化 int toInsert = arr[i]; int toPos = 0; while (arr[toPos] <= toInsert && toPos < i) { toPos++; } // 插入到 toPos 位置 if (toPos != i) { System.arraycopy(arr, toPos, arr, toPos + 1, i - toPos); arr[toPos] = toInsert; }} }// 针对位置插入从后向前边判断大小，边移动元素 public void insertSortOpt(int[] arr) { int len = arr.length; for (int i = 1; i < len; i++) { // 从后往前移动元素 int toInsert = arr[i]; for (int pos = i; pos >= 0; pos--) { if (pos > 0 && arr[pos - 1] > toInsert) { arr[pos] = arr[pos - 1]; } else { arr[pos] = toInsert; break; } } // 这种情况解决不了插入位在第 0 位的情况 //for (int pos = i - 1; pos >= 0; pos--) { //if (arr[pos] > toInsert) { //arr[pos + 1] = arr[pos]; //} else { //arr[pos + 1] = toInsert; //break; //} //} } }public void insertSortSwap(int[] arr) { // 此刻 i 标记的有序数组最后一位 for (int i = 0; i < arr.length - 1; i++) { for (int j = i + 1; j > 0; j--) { if (arr[j] >= arr[j - 1]) { break; } // 交换 int tmp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = tmp; } } }public void insertSortBinary(int[] arr) { for (int i = 1; i < arr.length; i++) { // 通过二分查找插入位置// 边界 0、i两种情况，返回何值比较合适 int toInset = arr[i]; int pos = binarySearch(arr, i - 1, toInset); if (pos != i) { System.arraycopy(arr, pos, arr, pos + 1, i - pos); arr[pos] = toInset; } } }public int binarySearch(int[] arr, int end, int key) { int left = 0; int right = end; while (left <= right) { int mid = (left + right) >>> 1; if (key >= arr[mid]) { left = mid + 1; } else { right = mid - 1; } } return left; }public static void main(String[] args) { InsertionSort testClass = new InsertionSort(); int[] arr = new int[]{49, 38, 65, 97, 76, 13, 27, 49, 55, 4}; testClass.insertSortBinary(arr); System.out.println(Arrays.toString(arr)); } }

【八大排序算法之直接插入排序（InsertionSort）】`