【大话数据结构&算法】直接插入排序

柔光的暖阳◎ 2022-09-25 01:29 204阅读 0赞

直接插入排序的基本思想：**每趟将一个待排元素作为关键字，按照其关键字值得大小插入到已经排好序的部分序列的适当位置，直到插入完成**。

--------------------

**算法思想总结如下**：（设待排序的数组为a\[0…n-1\]）

> 1、初始时，a\[0\]就是第一个有序区间，无序区间为a\[1…n-1\]；  
> 2、将a\[i\]并入当前的有序区a\[0…i-1\]中形成a\[0…i\]的有序区间；  
> 3、i++并重复第二步，知道i=n-1，此时排序完成。

--------------------

**直接插入排序基本算法实现如下**：

void insertSort1(int[] a,int n){
            int i,j,temp;
            //第一个元素有序，所以从第二个开始处理
            for (i = 1; i < n; i++) {
                  temp = a[i];//将待排元素暂存于temp中
                  j = i - 1;
                  //从待排元素之前的元素开始扫描，如果大于待排元素，则后移一位
                  while(j >= 0 && a[j] > temp){
                        a[j + 1] = a[j];
                        j--;
                  }
                  //找到插入位置，将temp中暂存的待排元素插入
                  a[j + 1] = temp;
            }
      }

--------------------

**java代码实现如下**：

public class InsertSort {
          public static void main(String[] args) {
                int[] a = {
       5,2,9,6,8,4,3,0};
                insertSort1(a,8);
                for (int i = 0; i < a.length; i++) {
                      System.out.println(a[i]);
                }
                System.out.println("**************");
                int[] b = {
       5,2,9,6,8,4,3,0};
                insertSort2(b,8);
                for (int i = 0; i < b.length; i++) {
                      System.out.println(b[i]);
                }
          }
    
          public static void insertSort1(int[] a,int n){
                int i,j,temp;
                //第一个元素有序，所以从第二个开始处理
                for (i = 1; i < n; i++) {
                      temp = a[i];//将待排元素暂存于temp中
                      j = i - 1;
                      //从待排元素之前的元素开始扫描，如果大于待排元素，则后移一位
                      while(j >= 0 && a[j] > temp){
                            a[j + 1] = a[j];
                            j--;
                      }
                      //找到插入位置，将temp中暂存的待排元素插入
                      a[j + 1] = temp;
                }
          }
    
        public static void insertSort2(int[] a, int n){
              int i,j;
              for (i = 1; i < n; i++) {
                    if (a[i] < a[i-1]) {
                          int temp = a[i];
                          for (j = i-1; j >= 0 && a[j] > temp; j--) {
                               a[j+1] = a[j];
                         }
                         a[j+1] = temp;
                   }
             }
       }
    }

--------------------

> **时间复杂度**：
> 
> 考虑**最坏**的情况，即整个序列式逆序的，则内层循环temp < a\[j\]这个条件是始终成立的。此时，对于每一次外层循环，最内层循环的执行次数（也就是基本操作a\[j+1\] = a\[j\] 的执行次数）达到最大值，为i次，i的取值范围为2~n，由此可得基本操作总的执行次数为n(n-1)/2，时间复杂度为**O(n2)\{n的平方\}**。
> 
> 考虑**最好**的情况，即整个序列已经是有序序列，则对于内层循环temp < a\[j\]这个条件是始终不成立的。此时内层循环始终不执行，时间复杂度为\*\*重点内容\*\*0(n)。

--------------------

> **空间复杂度**：
> 
> 由算法代码可知，算法所需的额外空间只有一个temp，因此它的空间复杂度为**0(1)**。