Java實現(xiàn)直接插入排序與折半插入排序的示例詳解
更新時間：2022年06月29日 10:38:50 作者：Fug_Lee
這篇文章主要為大家詳細介紹了插入排序中兩個常見的排序：直接插入排序與折半插入排序。本文用Java語言實現(xiàn)了這兩個排序算法，感興趣的可以學(xué)習(xí)一下
1.直接插入排序
插入排序的基本思想: 主要分為兩個區(qū)間, 無序區(qū)間和有序區(qū)間, 每次選擇無序區(qū)間的第一個元素, 在有序區(qū)間內(nèi)選擇合適的位置進行插入操作.
插入過程如下圖所示:
代碼:
public class InsertSort {
public static void insertSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int tmp = array[i];
int j = i-1;
for (; j >= 0; j--) {
if (array[j] > tmp) {
array[j+1] = array[j];
} else {
break;
}
}
array[j+1] = tmp;
}
}
public static void main(String[] args) {
int[] arr = {3,2,5,7,1,6,8,9,4};
System.out.println(Arrays.toString(arr));
insertSort(arr);
System.out.println(Arrays.toString(arr));
}
}
運行結(jié)果:
性能分析:
2. 折半插入排序
折半插入的詳細過程如下:
代碼:
public class InsertSort {
public static void bsInsertSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int tmp = array[i];
int left = 0;
int right = i;
while (left < right) {
int aver = (left + right) / 2;
if (tmp >= array[aver]) {
left = aver + 1;
} else {
right = aver;
}
}
for (int j = i; j > left; j--) {
array[j] = array[j-1];
}
array[left] = tmp;
}
}
public static void main(String[] args) {
int[] arr = {3,2,5,7,1,6,8,9,4};
System.out.println(Arrays.toString(arr));
bsInsertSort(arr);
System.out.println(Arrays.toString(arr));
}
}
運行結(jié)果:
性能分析:
以上就是Java實現(xiàn)直接插入排序與折半插入排序的示例詳解的詳細內(nèi)容，更多關(guān)于Java插入排序的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章主要給大家介紹了關(guān)于jdk中4個random的相關(guān)資料,分別是Random、ThreadLocalRandom、SecureRandom以及SplittableRandom,文中通過示例代碼介紹的非常詳細,需要的朋友可以參考下2021-06-06
這篇文章主要為大家介紹了java開發(fā)Activiti進階篇流程實例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-08-08
這篇文章主要介紹了Java使用Cipher類實現(xiàn)加密的過程詳解,Cipher類提供了加密和解密的功能,創(chuàng)建密匙主要使用SecretKeySpec、KeyGenerator和KeyPairGenerator三個類來創(chuàng)建密匙。感興趣可以了解一下2020-07-07
seata 是alibaba 出的一款分布式事務(wù)管理器，他有侵入性小，實現(xiàn)簡單等特點。這篇文章主要介紹了seata springcloud整合教程與遇到的坑,需要的朋友可以參考下2021-07-07
這篇文章主要給大家介紹了關(guān)于Java新特性之Optional類超詳細介紹的相關(guān)資料,Java8中的Optional類是一個容器對象,可以包含null或非null值,文中通過示例代碼介紹的非常詳細,需要的朋友可以參考下2023-07-07
MAC 系統(tǒng)如何使用 Sublime Text 2 直接編譯運行 java 代碼
這篇文章主要介紹了MAC 系統(tǒng)如何使用 Sublime Text 2 直接編譯運行 java 代碼,需要的朋友可以參考下2014-10-10
這篇文章主要介紹了Springcloud sentinel安裝和使用方法解析,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-12-12
如何基于SpringMVC實現(xiàn)斷點續(xù)傳(HTTP)
這篇文章主要介紹了如何基于SpringMVC實現(xiàn)斷點續(xù)傳(HTTP),文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-01-01
這篇文章主要介紹了java 工廠方法詳解及實例代碼的相關(guān)資料,需要的朋友可以參考下2017-01-01
對于上傳功能,我們在項目中是經(jīng)常會用到的,比如用戶注冊的時候,上傳用戶頭像,這個時候就會使用到上傳的功能,而對于下載使用場景也很常見,下面這篇文章主要給大家介紹了關(guān)于SpringMVC實現(xiàn)文件上傳下載的相關(guān)資料,需要的朋友可以參考下2022-01-01