常見的排序演算法
今天復習【直接插入排序】
核心思想：有序陣列中 找位置 -- 給無序陣列第一個 找位置
點擊查看代碼
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));
}
}
還存在 ShellSort
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/435331.html
標籤：Java
下一篇：微服務中服務間通信