数据结构（十）：直接插入排序

た入场券 2021-10-01 11:00 358阅读 0赞

*  直接插入排序是将未排序的数据插入至已排好序序列的合适位置

### 直接插入排序例子 ###

*  流程：
    
     *  首先比较数组的前两个数据，并排序
     *  比较第三个元素与前两个排好序的数据，并将第三个元素放入适当的位置  
        　 - 比较第四个元素与前三个排好序的数据，并将第四个元素放入适当的位置
 *  举例：
    
     *  假设数组如下
    
    <table> 
     <thead> 
      <tr> 
       <th style="text-align:center">25</th> 
       <th style="text-align:center">11</th> 
       <th style="text-align:center">45</th> 
       <th style="text-align:center">26</th> 
       <th style="text-align:center">12</th> 
       <th style="text-align:center">78</th> 
      </tr> 
     </thead> 
     <tbody> 
     </tbody> 
    </table>
    
     *  第一趟排序：比较 25 11，位置互换
    
    <table> 
     <thead> 
      <tr> 
       <th style="text-align:center">11</th> 
       <th style="text-align:center">25</th> 
       <th style="text-align:center">45</th> 
       <th style="text-align:center">26</th> 
       <th style="text-align:center">12</th> 
       <th style="text-align:center">78</th> 
      </tr> 
     </thead> 
     <tbody> 
     </tbody> 
    </table>
    
     *  第二趟排序：45 大于 11 25，位置不变
     *  第三趟排序：26 大于 11 25，小于 45，将其插入 25 和 45 之间
    
    <table> 
     <thead> 
      <tr> 
       <th style="text-align:center">11</th> 
       <th style="text-align:center">25</th> 
       <th style="text-align:center">26</th> 
       <th style="text-align:center">45</th> 
       <th style="text-align:center">12</th> 
       <th style="text-align:center">78</th> 
      </tr> 
     </thead> 
     <tbody> 
     </tbody> 
    </table>
    
     *  ........

### 直接插入排序代码 ###

int[] arr = new int[]{1, 3, 6, 4, 7, 8, 5, 10, 9};
    // 直接插入排序
    for (int i = 1; i < arr.length; i++) {
        int tmp = arr[i];
        int j;
        for (j = i - 1; j >= 0; j--) {
        // 判断是否大于tmp，大于则后移一位
            if (arr[j] > tmp) {
                arr[j + 1] = arr[j];
            } else {
                break;
            }
        }
        arr[j + 1] = tmp;
    }

### 直接插入排序性能 ###

*  如果排序是随机的，那么根据概率相同原则，直接插入排序时间复杂度为 O(n²)，相比冒泡排序和简单选择排序性能要好一些