【Java】直接插入排序实现

た入场券 2022-01-07 05:35 221阅读 0赞

插入类排序主要有三种排序方法：直接插入排序、折半插入排序和希尔排序。本次简要介绍直接插入排序的实现。

直接插入排序的基本思想：

仅有一个元素的序列总是有序的，因此，对 n 个记录的序列，可从第二个元素开始直到第 n 个元素，逐个向有序序列中执行插入操作，从而得到 n 个元素按关键字有序的序列。

一般来说，在含有 j-1 个元素的有序序列中插入一个元素的方法是：从第 j-1 个元素开始依次向前搜索应当插入的位置，并且在搜索插入位置的同时可以后移元素，这样当找到适当的插入位置时即可直接插入元素。

图示排序过程：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0x1eWFuYw_size_16_color_FFFFFF_t_70][]

代码实现：

import java.util.Arrays;
    
    public class InsertSortTest {
        public static void main(String[] args){
            Integer[] arr = {5,2,7,3,9,10,8,6,1,4};
            insertSort(arr);
            System.out.println(Arrays.toString(arr));
        }
    
        //假设从小到大排序
        public static void insertSort(Integer[] arr){
            for (int i = 1; i < arr.length; i++) {
                int temp = arr[i];
                int position = i;
                for (int j = i-1; j >= 0 ; j--) {
                    if(temp < arr[j]){
                        //记录后移
                        arr[j+1] = arr[j];
                        position = j;
                    }else {
                        break;
                    }
                }
                //插入到正确位置
                arr[position]=temp;
            }
        }
    }

时间效率：

假设待排序的元素个数为 n，则向有序表中逐个插入记录的操作进行了 n-1趟，每趟操作分为比较关键码和移动记录，而比较的次数和移动记录的次数取决于待排序列按关键码的初始排列。  
⑴ 在最好情况下，即待排序序列已按关键字有序，每趟操作只需 1 次比较 0 次移动。此时有：  
总比较次数 = n-1 次  
总移动次数 = 0 次  
⑵ 在最坏情况下，即待排序序列按关键字逆序排序，这时在第 j 趟操作中，为插入元素需要同前面的 j 个元素进行 j 次关键字比较，移动元素的次数为 j+1 次。此时有：

![20190625140323619.png][]

⑶ 平均情况下：即在第 j 趟操作中，插入记录大约需要同前面的 j/2 个元素进行关键字比较，移动记录的次数为 j/2+1 次。此时有：  
总比较次数 ≈ n²/4 次  
总移动次数 ≈ n²/4 次

由此，直接插入排序的时间复杂度为Ο(n²)，并且是一个稳定的排序方法。

空间效率：

仅需要一个辅助存储单元。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0x1eWFuYw_size_16_color_FFFFFF_t_70]: /images/20211227/3ccfa00feb844a58aa25dd5edd88e0da.png
[20190625140323619.png]: /images/20211227/6da10f420f43477981dd27b25c5c31f6.png