排序---插入排序实现和性能分析

短命女 2023-07-05 13:06 52阅读 0赞

## 插入排序 ##

public class InsertSort { 
        public static void main(String[] args) { 
            int[] arr = new int[10];
            Random random = new Random();
            for(int i = 0; i < 10; i++) { 
                arr[i] = random.nextInt(10);
            }
            Arrays.stream(arr).forEach(System.out::print);
            insertSort(arr);
            System.out.println("");
            Arrays.stream(arr).forEach(System.out::print);
        }
    
        public static void insertSort(int[] arr) { 
            int length = arr.length;
            int index;
            int item;
    
            for(int i = 1; i < length; i++) { 
                index = i - 1;
                item = arr[i]; //待插入的元素
    
                while(index >= 0 && item < arr[index]) { 
                    arr[index + 1] = arr[index];
                    index--;
                }
    
                arr[index + 1] = item;
            }
        }
    }

## 性能分析 ##

1.  **空间复杂度为O(1)**。
2.  在插入排序中，对于值相同的元素，可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是**稳定的**排序算法。
3.  假设待排序的n个元素有序，则每次将第i个元素往前i-1个已经有序的元素中插入时，一次比较即可找到插入的位置，因此**最好情况时间复杂度为O(n)**；  
    假设待排序的n个元素逆序，则每次将第i个元素往前i-1个已经有序的元素中插入时，每次都需要遍历完前i-1个元素才能找到插入位置，因此**最坏情况时间复杂度为O(n^2)**；  
    往有序数组中插入一个元素的平均时间复杂度为O(n)，所以，对于插入排序操作，每次将第i个元素插入到前i-1个元素中时，找插入的位置的时间复杂度为O(i-1)，所以**平均时间复杂度为O(n^2)**。