八大排序算法之直接插入排序(InsertionSort)
2022/3/1 11:21:35
本文主要是介绍八大排序算法之直接插入排序(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)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-22项目:远程温湿度检测系统
- 2024-12-21《鸿蒙HarmonyOS应用开发从入门到精通(第2版)》简介
- 2024-12-21后台管理系统开发教程:新手入门全指南
- 2024-12-21后台开发教程:新手入门及实战指南
- 2024-12-21后台综合解决方案教程:新手入门指南
- 2024-12-21接口模块封装教程:新手必备指南
- 2024-12-21请求动作封装教程:新手必看指南
- 2024-12-21RBAC的权限教程:从入门到实践
- 2024-12-21登录鉴权实战:新手入门教程
- 2024-12-21动态权限实战入门指南