数据结构 | 排序算法总结——（一）直接插入排序（附Java实现代码）

1.1排序基本概念

排序：重新排列表中的元素，使表中的元素满足按关键字递增或递减的过程。

算法的稳定性：如果待排序表中有两个元素Ri、Rj，其对应的关键字keyi=keyj，且在排序前Ri在Rj前面，如果使用某一排序算法排序后，Ri仍在Rj的前面，则称这个排序算法是稳定的。

分类：在排序过程中，根据数据元素是否完全在内存中，可将排序算法分为两类。

       内部排序：在排序期间元素全部存放在内存中的排序。

外部排序：在排序期间元素无法全部同时存放在内存中，必须在排序过程中根据要求不断地在内外存之间移动的排序。

1.2插入排序

基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中，直到全部记录完成。

1.2.1直接插入排序

原理：把n个待排序的元素看成一个有序表和一个无需表，开始的时候有序表只有1个元素，无序表中有n-1个元素每次从无序表中取出第一个元素，将它插入到有序表中，使之成为新的有序表，重复n-1次完成整个排序过程。

具体流程如下：

1. 首先比较数组的前两个数据，并排序；
2. 比较第三个元素与前两个排好序的数据，并将第三个元素放入适当的位置；
3. 比较第四个元素与前三个排好序的数据，并将第四个元素放入适当的位置；
   …
4. 直至把最后一个元素放入适当的位置
5. 实例：

0.初始状态 3，1，5，7，2，4，9，6（共8个数）

有序表：3；无序表：1，5，7，2，4，9，6

1.第一次循环，从无序表中取出第一个数 1，把它插入到有序表中，使新的数列依旧有序

有序表：1，3；无序表：5，7，2，4，9，6

2.第二次循环，从无序表中取出第一个数 5，把它插入到有序表中，使新的数列依旧有序

有序表：1，3，5；无序表：7，2，4，9，6

3.第三次循环，从无序表中取出第一个数 7，把它插入到有序表中，使新的数列依旧有序

有序表：1，3，5，7；无序表：2，4，9，6

4.第四次循环，从无序表中取出第一个数 2，把它插入到有序表中，使新的数列依旧有序

有序表：1，2，3，5，7；无序表：4，9，6

5.第五次循环，从无序表中取出第一个数 4，把它插入到有序表中，使新的数列依旧有序

有序表：1，2，3，4，5，7；无序表：9，6

6.第六次循环，从无序表中取出第一个数 9，把它插入到有序表中，使新的数列依旧有序

有序表：1，2，3，4，5，7，9；无序表：6

7.第七次循环，从无序表中取出第一个数 6，把它插入到有序表中，使新的数列依旧有序

有序表：1，2，3，4，5，6，7，9；无序表：（空）

性能分析：

空间效率：仅使用常数个辅助单元，空间复杂度O(1)

时间效率：时间复杂度O(n2)

    最差情况：反序，需要移动n*(n-1)/2个元素，时间复杂度O(n2)

               最好情况：正序，不需要移动元素，时间复杂度O(n)

稳定性：稳定的

适用性：适用于顺序存储和链式存储的线性表

import java.util.Scanner;
import java.util.Arrays;
public class InsertSort {
    public static void insertSort(int[] arr){
        int i=0,j=0,temp=0;//定义变量i,j,temp并初始化
        for (i=1;i<arr.length;i++){//从第二个开始比较
            temp = arr[i];
            for (j=i-1;j>=0;j--){
                if (arr[j]>temp){//如果前面的数大于当前数，将它后移
                    arr[j+1] = arr[j];
                }else {
                    break;
                }
            }
            arr[j+1] = temp;//一轮比较结束，将此轮确定元素放到正确位置
        }
        System.out.println("直接插入排序："+Arrays.toString(arr));
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);//Scanner工具类键盘输入数据
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            if (n > 0) {
                int arr[] = new int[n];
                for (int i = 0; i < n; i++) {
                    arr[i] = scanner.nextInt();
                }
                insertSort(arr);//调用直接插入排序insertSort方法
            }
        }
    }
}