1. 算法

  • 算法就是解决问题的一种方法或一个过程，是一个由若干运算或指令组成的有穷序列。

    2. 算法-问题

  • 求解问题的算法可以看做是输入实例与输出之间的函数2.算法的概念 - 图1

    3. 算法的概念

    3.1 排序问题

    输入：n个元素序列2.算法的概念 - 图2
    输出：一个有序的排列2.算法的概念 - 图3，满足2.算法的概念 - 图4

    4. 算法的特征

  1. 算法有输入和输出：输入/输出
  2. 算法是确定的：确定性
  3. 算法必须是可行的：可行性

  4. 算法是必须在有限的时间内完成：有穷性

    5. 算法的描述

  5. 伪代码描述

  6. 流程图描述

  7. 。。。

    5.1 例直接插入排序算法

    参考资料：

  8. https://www.cnblogs.com/yinzhengjie/p/10959123.html

    5.1.1 直接插入排序原理：

  9. 在需要进行排序的无序序列中，构建一个子排序序列，直至全部数据排序完成

  10. 将未进行排序的数，插入到已经排序的序列中合适的位置
  11. 增加一个哨兵，放入比较值，让它和后面已经排好的序列比较，找到合适的插入点

    5.1.2 直接插入排序实例：

    2.算法的概念 - 图5

    5.1.3 插入排序算法伪代码：

    ```java

    A是需要被排序的无序序列，假设A中的元素从1开始计数

    InsertSort(A) for j = 2 to n do
    1.  key = A[j]    // 将当前需要被插入到已经排好序的序列的元素A[j]存到中间变量key中
    2.  i = j-1
    3.  while i > 0 and A[i] > key do    // 在已经排好序的序列中去找到A[j]的插入位置
    4.      A[i+1] = A[i]    // 往后移动一位
    5.      i = i-1
    6.  A[i + 1] = key    // 将A[j]插入到合适的位置
    return A
  2. <a name="eEPvS"></a>
  3. ### 5.1.4 直接排序Java代码实现
  4. 代码参见我的github:[https://github.com/JHong-Tao/Algorithm-Design-and-Analysis/tree/master/Insertsort](https://github.com/JHong-Tao/Algorithm-Design-and-Analysis/tree/master/Insertsort)
  5. ```java
  6. package cn.jhong.tao.insertsort;
  8. import java.util.Arrays;
  10. /**
  11.  * Created with IntelliJ IDEA.
  12.  * Author: JHong.Tao
  13.  * Date: 2019-10-12-19:41
  14.  * Version：1.0.0
  15.  * Description:
  16.  */
  17. public class InsertSort {
  19.     /**
  20.      * 插入排序算法
  21.      * @param arr
  22.      * @return
  23.      */
  24.     public static int[] insertSort(int[] arr){
  25.         int temp;   // temp为中间变量也就是担任哨兵
  26.         // i从1开始计数，默认将未进行排序的序列的第一个数当做已经拍好序的序列
  27.         for (int i = 1;i < arr.length; i++){
  28.             if(arr[i] < arr[i-1]){
  29.                 temp = arr[i];  // 获取数组将要被插入已经拍好序的未排序元素
  30.                 // 遍历已经排好序的序列，寻找需要被插入的元素在已经排好序的元素的位置
  31.                 for (int j = i; j >= 0; j--){
  32.                     if(j > 0 && arr[j-1] > temp){
  33.                         arr[j] = arr[j-1];
  34.                     }else {
  35.                         arr[j] = temp;
  36.                         break;  // 找到位置就退出循环
  37.                     }
  38.                 }
  39.             }
  40.             System.out.println("第"+i+"轮排序的结果："+Arrays.toString(arr));
  41.         }
  42.         return arr;
  43.     }
  44.     public static void main(String[] args) {
  45.         int arr[]  = {13,6,3,31,9,27,5,11};
  46.         System.out.println("排序前："+Arrays.toString(arr));
  47.         int arrSort[] = insertSort(arr);
  48.         System.out.println("排序后："+Arrays.toString(arr));
  49.     }
  50. }

5.1.5 插入排序算法复杂度分析：

插入排序算法的每一步的执行次数

image.png

算法的总计算次数

image.png

最好的情况

即输入的序列原本就是有序的序列，在这种情况下，不需要在进行排序，只相当于遍历整个序列去验证一下是否是有序的，所以2.算法的概念 - 图8每次都不会进入while循环，所以2.算法的概念 - 图9他们都不执行
image.png

最坏的情况

最差的情况就是输入的序列为一个逆序的序列
image.png
1，当初始序列为正序时，只需要外循环n-1次，每次进行一次比较，无需移动元素。此时比较次数（2.算法的概念 - 图12）和移动次数（2.算法的概念 - 图13）达到最小值。

2.算法的概念 - 图14=n-1，即只需要进行n-1次外层循环
2.算法的概念 - 图15=0，内存循环不需要，因为不需要移动数据
此时时间复杂度为2.算法的概念 - 图16。
2，当初始序列为反序时，需要外循环n-1次，每次排序中待插入的元素都要和[0,i-1]中的i个元素进行比较且要将这i个元素后移i次，加上tmp=arr[i]与arr[j]=temp的两次移动，每趟移动次数为i+2,此时比较次数和移动次数达到最大值。
2.算法的概念 - 图17 = 1+2+…+(n-1) = n(n-1)/2=2.算法的概念 - 图18
2.算法的概念 - 图19 = （1+2）+ （2+2）+…..+（n-1+2）=（n-1）(n+4)/2=2.算法的概念 - 图20
此时时间复杂度2.算法的概念 - 图21
3，在直接插入排序中只使用了i,j,tmp这三个辅助元素，与问题规模无关，空间复杂度为2.算法的概念 - 图22。
4，相同元素的相对位置不变，如果两个元素相同，插入元素放在相同元素后面。是一种稳定排序