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