排序-插入排序

偏执的太偏执、 2022-09-29 14:55 258阅读 0赞

## 1.直接插入排序算法的定义 ##

直接插入排序(Straight Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。

## 2.直接插入排序的代码 ##

顾名思义，从名称上也可以知道它是一种插入排序的方法。

/*对顺序表L作直接插入排序*/
    1   void InsertSort(SqList *L)
    2   {
    3       int i,j;
    4       for(i=2; i<=L->length; i++)
    5       {
    6           if(L->r[i]<L->r[i-1])   /*需将L->r[i]插入有序子集*/
    7           {
    8               L->r[0] = L->r[i];  /*设置哨兵*/
    9               for(j=i-1; L->r[j]>L->r[0]; j--)
    10                  L->r[j+1] = L->r[j];        /*记录后移*/
    11              L->r[j+1] = L->r[0];        /*插入到正确位置*/
    12          }
    13      }
    14  }

1.程序开始运行，此时我们传入的SqList参数的值为length=6，r\[6\]=\{0，5，3，4，6，2\}，其中r\[0\]=0将用于后面起到哨兵的作用。

2.第4~13行就是排序的主循环。i从2开始的意思是我们假设r\[1\]=5已经放好位置，后面的牌其实就是插入到它的左侧还是右侧的问题。

3.第6行，此时i=2，L.r\[i\]=3比L.r\[i-2\]=5要小，因此执行第8~11行的操作。第8行，我们将L.r\[0\]赋值为L.r\[i\]=3的目的是为了起到第9~10行的循环终止的判断依据。如下图所示，图中下方的虚线箭头，就是第10行，L.r\[j+1\]=L.r\[j\]的过程，将5右移一位。

![O75eV1D.jpg][]

4.此时，第10行就是在移动完成后，空出了空位，然后第11行L.r\[j+1\]=L.r\[0\]，将哨兵的3赋值给j=0时的L.r\[j+1\]，也就是说，将3放置到L.r\[1\]的位置，如下图所示

![aBNtNfH.jpg][]

5.继续循环，第6行，因为此时i=3，L.r\[i\]=4比L.r\[i-1\]=5要小，因此执行第8~11行的操作，将5再右移一位，将4放置到当前5所在位置，如下图所示

![p6W7G2r.jpg][]

6.再次循环，此时i=4。因为L.r\[i\]=6比L.r\[i-1\]=5要大，于是第8~11行代码不执行，此时前三个数的位置没有变化，如下图所示

![8j3VlBX.jpg][]

7.再次循环，此时i=5，因为L.r\[i\]=5比L.r\[i-1\]要小，因此要执行第8~11行的操作。由于6、5、4、3都比2大，它们都将右移一位，将2放置到当前3所在位置。如下图所示，此时我们的排序也就完成了。

![fJOLqSv.jpg][]

## 3.直接插入排序的复杂度分析 ##

从空间上来看，直接插入排序算法需要一个记录的辅助空间，因此关键是看它的时间复杂度。

当最好的情况，也就是要排序的表本身就是有序的，比如纸牌拿到后就是\{2,3,4,5,6\}，那么我们比较次数，其实就是代码第6行每个L.r\[i\]与L.r\[i-1\]的比较，共比较了![jfPZdzo.png][]次，由于,每次都是L.r\[i\]>L.r\[i-1\]，因此没有移动的记录，时间复杂度为O(n)。

当最坏的情况，即待排序表示逆序的情况，比如\{6，5，4，3，2\}，此时需要比较(n+2)(n-1)/2次，而记录的移动次数也达到最大值(n+4)(n-1)/2次。

如果排序记录时随机的，那么根据概率相同的原则，平均比较和移动次数约为n\*n/4次。\*因此，我们得出直接插入排序法的时间复杂度为O(n2)。从这里也看出，同样的O(n2)时间复杂度，直接插入排序法比冒泡和简单选择排序的性能要好一些。

## 4.直接插入排序的实现(Java) ##

#### 工程目录结构 ####

![这里写图片描述][SouthEast]

#### 排序类 ####

package com.red.sort.insertion;
    
    public class InsertionSort {
        public void insertionSort(int[] array) {
            int i, j, key;
            for (j = 1; j < array.length; j++) {
                key = array[j];
                i = j - 1;
                while (i >= 0 && array[i] > key) {
                    array[i + 1] = array[i];// 记录后移
                    i = i - 1;
                }
                array[i + 1] = key;// 插入到正确位置
            }
        }
    }

#### 测试类 ####

package com.red.sort.insertion;
    
    public class Main {
        public static void main(String[] args) {
            int[] array = new int[] { 9, 1, 5, 8, 3, 7, 4, 6, 2  };
            InsertionSort insertionSort = new InsertionSort();
            insertionSort.insertionSort(array);
    
            for (int i = 0; i < array.length; i++) {
                System.out.print(array[i] + " ");
            }
        }
    }

#### 输出结果： ####

1 2 3 4 5 6 7 8 9

[O75eV1D.jpg]: http://i.imgur.com/O75eV1D.jpg
[aBNtNfH.jpg]: http://i.imgur.com/aBNtNfH.jpg
[p6W7G2r.jpg]: http://i.imgur.com/p6W7G2r.jpg
[8j3VlBX.jpg]: http://i.imgur.com/8j3VlBX.jpg
[fJOLqSv.jpg]: http://i.imgur.com/fJOLqSv.jpg
[jfPZdzo.png]: http://i.imgur.com/jfPZdzo.png
[SouthEast]: /images/20220708/dc143eb0d42f4c4b908ce08f75c3dfba.png