插入排序及时间复杂度

向右看齐 2022-03-12 04:46 289阅读 0赞

## 思想 ##

在已经排好序的数组上插入值，即选择第一个数为有序数组，  
然后依次插入后面的数，如 6 4 5 7 0排序，选择6为有序数组，  
依次插入4 5 7 0，其过程数组如下  
`6` 4 5 7 0  
`4 6` 5 7 0  
`4 5 6` 7 0  
`4 5 6 7` 0  
`0 4 5 6 7` .

插入排序过程有三种情况，  
一种是插入的数值应该在原地（结尾），  
一种插入的数值在应该中间，  
一种插入的数值应该在开头，

## 代码 ##

private int[] insertSort() {
        if (this.arr.length < 2) {
          return this.arr;
        }
        for (int i = 1; i<this.arr.length; i++) {
          int tmp = this.arr[i];
          if(this.arr[i] >= this.arr[i-1]) {      // 原地不动
            continue;
          }
          for(int j=i-1; j>=0; --j) {
            this.arr[j+1] = this.arr[j];
            if (tmp >= this.arr[j]) {   // 插入中间位置
              this.arr[j+1] = tmp;
              break;
            }
            if (0 == j) {   // 比第一个还小的情况
              this.arr[j] = tmp;
            }
          }
        }
        return this.arr;
      }

## 时间复杂度 ##

按照代码，最坏的情况（每次插入都遍历一遍已经排好序的数组）：  
外层循环n-1次，内层循环1+2+3+…+(n-2)=(n-2)(n-1)/2次  
所以最坏情况是`O(n^2)`  
按照代码，最好的情况（已经有序）：`O(n)`  
平均情况为：(n^2 + n)/2，因为二次函数比一元一次函数增长快，  
所以为插入排序算法的时间复杂度为`O(n^2)`

## 空间复杂度 ##

因为辅助空间只有一个辅助变量，所以为O(1)