• 排序是將一串?dāng)?shù)據(jù)按照其某個(gè)或者某些關(guān)鍵字的大小進(jìn)行遞增或遞減排列的操作我，通常指的排序是升序，排序方式是原地排序
• 下面介紹下插入排序

插入排序

• 原理：插入排序是將待排序區(qū)間分成兩個(gè)區(qū)間，分別是無(wú)序區(qū)間和有序區(qū)間，遍歷無(wú)序區(qū)間中的每一個(gè)元素，將其插入到有序區(qū)間的對(duì)應(yīng)位置。當(dāng)無(wú)序區(qū)間的元素遍歷完畢后，待排序區(qū)間就有序了
• 插入排序是一個(gè)穩(wěn)定的排序

實(shí)現(xiàn)方式

1. 直接插入排序
   • 將待排序區(qū)間的左邊[0, i)看做有序區(qū)間，[i, size)看做無(wú)序區(qū)間，遍歷無(wú)序區(qū)間的元素，全部插入到有序區(qū)間后，排序結(jié)束
   • 代碼1（推薦）：

     public void insertSort(int[] array) {
             int length = array.length;
             //遍歷無(wú)序區(qū)間[1, length)
             for (int i = 1; i < length; i++) {
                     //表示當(dāng)前需要被插入到有序區(qū)間的元素
                     int tmp = array[i];
                     int j;
                     //遍歷有序區(qū)間[0, i)
                     //不寫(xiě)等于是為了保證排序的穩(wěn)定性
                     for (j = i - 1; j >= 0 && array[j] > tmp; j--) {
                             array[j + 1] = array[j];
                     }
                     array[j + 1] = tmp;
             }
     }

   • 代碼2（不推薦）：
   • 在遍歷有序區(qū)間找對(duì)應(yīng)位置時(shí)，由于每次比較都可能進(jìn)行次交換，時(shí)間和空間上會(huì)造成一定程度的浪費(fèi)，因此效率不如代碼1

     public void insertSort2(int[] array) {
             int length = array.length;
             //遍歷無(wú)序區(qū)間[1, length)
             for (int i = 1; i < length; i++) {
                     //遍歷有序區(qū)間
                     for(int j = i; j >0; j--) {
                             //如果待排序元素小于有序區(qū)間的最后一個(gè)元素就與其交換
                             if(array[j] < array[j - 1]) {
                                     int tmp = array[j];
                                     array[j] = array[j - 1];
                                     array[j - 1] = tmp;
                             }
                     }
             }
     }

2. 折半插入排序

   

   創(chuàng)新互聯(lián)專(zhuān)業(yè)為企業(yè)提供渦陽(yáng)網(wǎng)站建設(shè)、渦陽(yáng)做網(wǎng)站、渦陽(yáng)網(wǎng)站設(shè)計(jì)、渦陽(yáng)網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁(yè)設(shè)計(jì)與制作、渦陽(yáng)企業(yè)網(wǎng)站模板建站服務(wù)，十載渦陽(yáng)做網(wǎng)站經(jīng)驗(yàn)，不只是建網(wǎng)站，更提供有價(jià)值的思路和整體網(wǎng)絡(luò)服務(wù)。

   • 同樣是將待排序區(qū)間分為了有序和無(wú)序兩個(gè)區(qū)間，但是在遍歷插入位置時(shí)采用了二分查找的方式
   • 找到要插入的位置后將有序區(qū)間中該位置后的的元素向后搬移一位
   • 然后將要插入的元素插入

   • 代碼：

     public void bsInsertSort(int[] array) {
             for(int i = 1; i < array.length; i++) {
                     int tmp = array[i];
                     int left = 0;
                     int right = i;
     
                     //在有序區(qū)間內(nèi)進(jìn)行二分查找操作，找到要插入的位置
                     while(left < right) {
                             int mid = (right + left) >>> 1;
                             if(array[mid] <= tmp) {
                                     left = mid + 1;
                             } else {
                                     right = mid;
                             }
                     }
     
                     //將有序區(qū)間內(nèi)[left, i)中的元素向后移動(dòng)一位
                     for(int j = i - 1; j >= left; j--) {
                             array[j + 1] = array[j];
                     }
                     array[left] = tmp;
             }
     }

性能分析

• 時(shí)間復(fù)雜度：
  • 最好的情況：待排序有序時(shí)，時(shí)間復(fù)雜度為O(N)
  • 最壞的情況：待排序逆序時(shí)，時(shí)間復(fù)雜度為O(N^2)
  • 平均情況：時(shí)間復(fù)雜度 為O(N^2)
• 空間復(fù)雜度：O(1)
• 穩(wěn)定性：穩(wěn)定
• 初始數(shù)據(jù)越接近有序，時(shí)間效率越高

網(wǎng)站名稱(chēng)：java實(shí)現(xiàn)插入排序代碼
網(wǎng)站路徑：http://chinadenli.net/article6/pggpig.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供電子商務(wù)、微信小程序、營(yíng)銷(xiāo)型網(wǎng)站建設(shè)、建站公司、服務(wù)器托管、品牌網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)