Java 十大排序算法之插入排序刨析
插入排序原理
①把所有元素分成已排序和未排序兩組
②找到未排序組的第一個(gè)元素，向已經(jīng)排序的組中進(jìn)行插入
③倒序遍歷已經(jīng)排好的元素，依次和待插入的元素進(jìn)行比較，直到找到一個(gè)元素小于等于待插入元素，那么就把待插入元素放到這個(gè)位置，其他元素向后移動(dòng)一位
插入排序API設(shè)計(jì)
| 類名 | Insertion |
| 構(gòu)造方法 | Insertion():創(chuàng)建Insertion對(duì)象 |
| 成員方法 |
1.public static void sort(Comparable[] a):對(duì)數(shù)組內(nèi)的元素進(jìn)行排序 2.private static boolean greater(Comparable v,Comparable w):判斷v是否大于w 3.private static void exchange(Comparable[] a,int i,int j):交換a數(shù)組中，索引i和索引j處的值 |
插入排序代碼實(shí)現(xiàn)
public class Insertion {
//對(duì)數(shù)組a的元素進(jìn)行排序
public static void sort(Comparable[] a){
for(int i=1;i<a.length;i++){
//當(dāng)前元素為a[i],依次和i前面的元素比較，找到一個(gè)小于等于a[i]的元素
for(int j=i;j>0;j--){
if(greater(a[j-1],a[j])){
exchange(a,j-1,j);
}else{
//找到了該元素，結(jié)束
break;
}
}
}
}
//比較v元素是否大于w元素
private static boolean greater(Comparable v,Comparable w){
return v.compareTo(w)>0;
}
//數(shù)組元素i和j交換位置
private static void exchange(Comparable[] a,int i,int j){
Comparable t=a[i];
a[i]=a[j];
a[j]=t;
}
}
//測(cè)試代碼
class Test{
public static void main(String[] args) {
Integer[] a={4,3,2,10,12,1,5,6};
Insertion.sort(a);
System.out.println(Arrays.toString(a));
}
}
運(yùn)行結(jié)果：
插入排序的時(shí)間復(fù)雜度分析
和冒泡排序分析相同！
雖然使用了雙層循環(huán)，但內(nèi)循環(huán)是真正完成排序的代碼，所以主要分析內(nèi)層循環(huán)的執(zhí)行次數(shù)即可！
在數(shù)組元素為{12,10,6,5,4,3,2,1}為最壞情況
元素的比較次數(shù)為：(N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2;
元素的交換次數(shù)為：(N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2;
總執(zhí)行次數(shù)為：2*(N^2/2-N/2)=N^2-N;
根據(jù)大O推導(dǎo)法則，保留最高階項(xiàng)，即插入排序的時(shí)間復(fù)雜度為O(N^2)
到此這篇關(guān)于Java 十大排序算法之插入排序刨析的文章就介紹到這了,更多相關(guān)Java 插入排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
每個(gè)bean都有一個(gè)或者多個(gè)標(biāo)識(shí)符,這些標(biāo)識(shí)符在容器中必須是唯一的,這篇文章主要給大家介紹了關(guān)于spring bean名稱命名的那些事,需要的朋友可以參考下2021-07-07
這篇文章主要介紹了Java線程之程安全與不安全代碼示例，還是比較不錯(cuò)的，這里分享給大家，供需要的朋友參考。2017-11-11
解決Spring Batch框架job任務(wù)只跑一次的問題
這篇文章主要介紹了解決Spring Batch框架job任務(wù)只跑一次的問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-09-09
java.lang.OutOfMemoryError: Metaspace異常解決的方法
這篇文章主要介紹了java.lang.OutOfMemoryError: Metaspace異常解決的方法，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03
Java使用JDK與Cglib動(dòng)態(tài)代理技術(shù)統(tǒng)一管理日志記錄
這篇文章主要介紹了Java使用JDK與Cglib動(dòng)態(tài)代理技術(shù)統(tǒng)一管理日志記錄，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-05-05
這篇文章主要為大家詳細(xì)介紹了java設(shè)計(jì)模式之工廠方法的相關(guān)資料，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-09-09
這篇文章主要介紹了spring boot集成pagehelper(兩種方式)，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2018-01-01
這篇文章主要介紹了面試題ThreadLocal,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友可以參考下2019-06-06
java實(shí)現(xiàn)微信掃碼登錄第三方網(wǎng)站功能（原理和代碼）
為避免繁瑣的注冊(cè)登陸，很多平臺(tái)和網(wǎng)站都會(huì)實(shí)現(xiàn)三方登陸的功能，增強(qiáng)用戶的粘性。這篇文章主要介紹了java實(shí)現(xiàn)微信掃碼登錄第三方網(wǎng)站功能（原理和代碼），避免做微信登錄開發(fā)的朋友們少走彎路2022-12-12
Spring Boot集成Redis實(shí)現(xiàn)緩存機(jī)制(從零開始學(xué)Spring Boot)
這篇文章主要介紹了Spring Boot集成Redis實(shí)現(xiàn)緩存機(jī)制(從零開始學(xué)Spring Boot),需要的朋友可以參考下2017-04-04