直接插入排序

一颗蔬菜 2019-09-13 PM 36℃ 0条

插入排序的设计初衷是往有序的数组中快速插入一个新的元素。它的算法思想是:把要排序的数组分为了两个部分, 一部分是数组的全部元素(除去待插入的元素), 另一部分是待插入的元素; 先将第一部分排序完成, 然后再插入这个元素. 其中第一部分的排序也是通过再次拆分为两部分来进行的。

直接插入排序的基本思想是:将数组中的所有元素依次跟前面已经排好的元素相比较,如果选择的元素比已排序的元素小,则交换,直到全部元素都比较过为止。

 /*
 第一种写法:每次遍历前n个元素,反向冒泡排序.
 */
 public void insertionSort(int[] nums) {
        for (int i =  1; i < nums.length; i ++) {
            for (int j = i; j >=1; j --) {
                if (nums[j] < nums[j - 1]) {
                    int tmp = nums[j];
                    nums[j] = nums[j - 1];
                    nums[j - 1] = tmp;
                }else{ 
                    break;
                }
            }
            System.out.println(Arrays.toString(nums));
        }
}
/*
第二种写法:用当前元素和有序序列的每个元素比较,挖坑再填坑
public void insertionSort(int[] nums) {
    for (int i = 1; i < nums.length; i ++) {
       int index = nums[i]; // 挖坑
       for (int j = i - 1; j >= 0; j --) {
           if (nums[j] > index) {
               nums[j + 1] = nums[j];
           }else{
               nums[j + 1] = index;
               break;
           }
       }
       System.out.println(Arrays.toString(nums));
    }
}
*/
平均时间复杂度最好情况最坏情况空间复杂度
O(n²)O(n)O(n²)O(1)

我怎么这么笨....

标签: 算法

非特殊说明,本博所有文章均为博主原创。