数据结构笔记 - 排序算法 直接插入排序算法

直接插入排序:

将一个元素通过和当前已经排序好的数组的最大元素进行比较,并在待插入数组较小的情况下通过设置哨兵,整体移动,插入正确位置的步骤,从此得到一个新的排序好的数组的过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdio.h>

#define MAXSIZE 100 /* 待排序数组的大小 */

typedef struct
{
int r[MAXSIZE+1]; /* 待排序数组r,r[0]为哨兵或临时变量 */
int length; /* 待排序数组的长度,为了方便理解,不包含r[0]元素 */
}SortList;

/* 直接插入排序算法 */
void InsertSort(SortList *L)
{
int i,j;
for(i=2;i<=L->length;i++)
{
/* 将r[i]插入有序数组前进行判断 */
if (L->r[i]<L->r[i-1])
{
L->r[0]=L->r[i]; /* 设置哨兵 */
for(j=i-1;L->r[j]>L->r[0];j--)
/* 循环向右移动数据元素 */
L->r[j+1]=L->r[j];
L->r[j+1]=L->r[0]; /* 把r[i](此时存在r[0]中)插入到循环移动腾出的位置 */
}
}
}

直接插入排序时间复杂度分析:

最好的情况下,即每次需要插入的元素都是最大的,这样只需要比较n-1次,没有移动记录,所以时间复杂度为O(n)。

最坏的情况下,即待排序的是逆序的,此时需要比较的次数为:2+3+4+…+n=(n+2)(n-1)/2,而移动的次数为:(n+4)(n-1)/2。总得时间复杂度为O(n^2)。

直接插入排序算法比冒泡和简单排序算法的性能要好一点。

arthinking wechat
欢迎关注itzhai公众号