插入排序法的介绍

什么是插入排序法？

插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法  。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动 ；

稳定性分析

如果待排序的序列中存在两个或两个以上具有相同关键词的数据，排序后这些数据的相对次序保持不变，即它们的位置保持不变，通俗地讲，就是两个相同的数的相对顺序不会发生改变，则该算法是稳定的；如果排序后，数据的相对次序发生了变化，则该算法是不稳定的。关键词相同的数据元素将保持原有位置不变，所以该算法是稳定的；

插入排序基本思想

插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序；

如图

例子分析

如对数列     5  2  4  1   插入排序

第一次：用数列下标为1的数 2与5比较，5>2,所以交换位置，数列变为   2  5   4   1；

第一次后的数列为     2   5    4   1

第二次：然后下标增加，用下标为2的数 4与5比较，4<5,所以交换位置，变为  2  4  5  1   ，然后4与2比较，4>2,不用交换；

第二次后的数列 为    2   4    5   1

第三次：用下标为3的数 1 与5比较，5>1,所以交换，变为   2   4   1    5，然后1与4比较，4>1，交换，变为  2     1      4    

 5，再用1与2比较，2>1，交换，变为 1    2     4     5；

最后排完数列变为    1    2   4   5

实现代码

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
void Print(int arr[], int n)
{
  int i = 0;
  for (i = 0; i < n; i++)
  {
    printf("%d ",arr[i]);      //结果打印函数
  }
  printf("\n");
}
void Sort_arr(int arr[],int n)     //排序的函数   
{
  int tmp = 0;
  int i = 0;
  int j = 0;
  for (i = 1; i < n; i++)
  {
    tmp = arr[i];
    for (j = i - 1; j >= 0; j--)
    {
      if (tmp > arr[j])
      {
        break;
      }
      else
      {
        arr[j + 1] = arr[j];
      }
    }
    arr[j+1] = tmp;
    Print(arr, 10);          //打印排序过程
  }
}
int main()
{
  int a[10] = { 12,18,2,6,21,8,10,-6,11,9};
  Sort_arr(a, 10);
  Print(a,10);
  return 0;
}

运行结果