本文目的

上一章节已经详细的向大家介绍过排序的相关概念学习笔记-排序简单介绍，本文旨在为大家详细的介绍直接插入排序。

直接插入排序

直接插入排序（Straight Insertion Sort）是一种简单的排序方法，是一种插入类排序。其基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。

算法原理

将一个记录插入到已排好序的序列中，从而得到一个新的有序序列（将序列的第一个数据看成是一个有序的子序列，然后从第二个记录逐个向该有序的子序列进行有序的插入，直至整个序列有序）

算法流程

当插入第i(i >= 1)时，前面的V[0]，V[1]，……，V[i-1]已经排好序。这时，用V[I]的排序码与V[i-1]，V[i-2]，…的排序码顺序进行比较，找到插入位置即将V[i]插入，原来位置上的元素向后顺移。

算法实现

算法思路（从小到大排序）：

1、一组数据a[N]，设置变量i , j , temp，i 是待插入元素的下标，将a[i]赋值给temp，j是用来搜索比较

2、i 的初始值为1，即从第二个元素开始，一个元素认为是已经排好序的，所以从第二个元素开始，j的初始值为i-1

3、将i前面的数据都与temp比较，即与待插入数据进行比较，用 j 来移动下标，直到找到一个比temp小的或等于的值，亦或者找到了该序列的尽头（即下标为0）停止，将temp放到j+1的位置，即将待插入的数据插入到j+1的位置，该待插入数据就已经插入到了正确的位置

4、然后将i=2，从第三个元素开始，j=i-1，执行temp=a[i]，重复步骤3，直到 i==N-1停止，即所有数据都已经放到了正确的位置上，该序列称为有序序列

#include <stdio.h> 
#define elemType int /*元素类型*/

int k=1;//轮次记录 

void Print (elemType arr[], int len){
	
	int i;
	
	for (i=0; i<len; i++){
		printf ("%d\t", arr[i]);
	}
        
    printf("\n");
}

void Sort(elemType a[], int len)
{
	int i,j;
    for(i=1;i<len;i++)
      //循环从第2个元素开始
    {
        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;
          //此处就是a[j+1]=temp;
        }
        
    printf("第===%d===轮排序后结果如下：\n",k);
		Print (a, 9);
		k=k+1;
    }
}
 
int main() {
	
	int i;
    elemType arr[9] = {94,19,29,9,11,1,14,13,29};
    printf("待排序的序列为：\n");
    Print(arr, 9);  
    printf("\n\n");
    
    Sort (arr,9);
    printf("\n\n");
    printf("排好序的结果如下：\n");
    Print(arr, 9);  
 }

算法分析

时间复杂度

最好情况：当初始序列为正序时，只需要外循环n-1次，每次进行一次比较，无需移动元素。此时比较次数Cmin=n-1和移动次数Mmin=0达到最小值。此时时间复杂度为O(n)。

最差情况：当初始序列为反序时，需要外循环n-1次，每次排序中待插入的元素都要和[0,i-1]中的i个元素进行比较且要将这i个元素后移i次，加上tmp=arr[i]与arr[j]=temp的两次移动，每趟移动次数为i+2,此时比较次数和移动次数达到最大值。此时时间复杂度O(n2)

平均时间复杂度O(n2)

空间复杂度

在直接插入排序中只使用了i,j,tmp这三个辅助元素，与问题规模无关，空间复杂度为O(1)。

排序稳定性

相同元素的相对位置不变，如果两个元素相同，插入元素放在相同元素后面。是一种稳定排序

本文的初衷为学习笔记的分享，部分图文来源于网络，如侵，联删。