排序算法：直接插入排序算法实现及分析

Bertha 。 2022-05-31 11:05 224阅读 0赞

# 直接插入排序算法介绍 #

还是先过一遍定义。**直接插入排序（Straight Insertion Sort）的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。**来我们用通俗一点的话说，就是把数组中元素一个个取出插入到有序表中，直到将数组元素全部插入到有序表中。那么如何构造有序表呢？我们不需要构造，有序表 只是一种形式。当有序表中只有一个元素时，那它肯定是有序的呀。所以我们开始将第0个元素当做有序表。

我们先假定升序。int temp = arr\[1\]与有序表的最大值arr\[0\]进行比较，arr\[1\]<arr\[0\]那么arr\[0\]就往后挪，挪到arr\[1\]的位置，此时temp 和 有序表中的第二个最值进行比较，发现和有序表比较完了，temp 就放到arr\[0\]处呗。

现在我们假定有序表中已经有多个元素了。**我们取到数组中的第i个数组元素，往 0~ i-1 的有序表中进行插入，它的比较过程如下**：跟有序表的最大值arr\[i-1\]比较，发现比最大值小，将最值arr\[i-1\]往前挪，继续和有序表中第二大的值arr\[i-2\]，进行比较，如果还是发现比它小，这有序表中的第二大的值arr\[i-2\]继续往前挪，继续进行比较直到找到有序表中第j个元素比当前元素要小或者将有序表找完了。将当前元素放到j+1的位置，这样就找到了第i元素要插入的位置了。

# 直接插入排序算法代码 #

//直接插入排序 升序
    void InsertSort_Up(int* arr, int length)
    {
    	//假定第0个元素是有序表，从第1个元素开始往有序表中插入数据
    	for (int i = 1; i < length; i++)
    	{
    		int temp = arr[i];
    		int j;
    		for (j = i - 1; j >= 0 && arr[j] > temp; j--)
    		{
    			arr[j + 1] = arr[j];//往前挪
    		}
    		arr[j + 1] = temp;
    	}
    	return;
    }

# **直接插入排序算法时间复杂度分析** #

我们考虑最坏的情况，当数组完全逆序的时候比如\{6,5,4,3,2,1\}这种情况，我们进行升序排序，我们比较的次数：1+2+3+4+5，数据移动的次数：1+2+3+4+5。扩展到n个元素的数组 比较次数：1+2...+n-1 = n\*(n-1)/2，移动的次数同样为n\*(n-1)/2，所考虑数据随机的情况，时间复杂度为（n^2 -n）/2 = **O(n^2)**。**从这里可以看出同样的O(n^2)时间复杂度，直接插入排序比选择排序和冒泡排序性能要要一些**。**直接插入排序对数组基本有序和数组元素比较少的时候，速度比较快**。

# **完整代码** #

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #include <sys/timeb.h>
    #define MAXSIZE 20
    #define MAXNUM 21
    //交换值
    void Swap(int* a, int* b)
    {
    	int temp = *a;
    	*a = *b;
    	*b = temp;
    }
    //直接插入排序 升序
    void InsertSort_Up(int* arr, int length)
    {
    	//假定第0个元素是有序表，从第1个元素开始往有序表中插入数据
    	for (int i = 1; i < length; i++)
    	{
    		int temp = arr[i];
    		int j;
    		for (j = i - 1; j >= 0 && arr[j] > temp; j--)
    		{
    			arr[j + 1] = arr[j];//往前挪
    		}
    		arr[j + 1] = temp;
    	}
    	return;
    }
    //直接插入排序 降序
    void InsertSort_Down(int* arr, int length)
    {
    	//假定第0个元素是有序表，从第1个元素开始往有序表中插入数据
    	for (int i = 1; i < length; i++)
    	{
    		int temp = arr[i];
    		int j;
    		for (j = i - 1; j >= 0 && arr[j] < temp; j--)
    		{
    			arr[j + 1] = arr[j];//往前挪
    		}
    		arr[j + 1] = temp;
    	}
    	return;
    }
    //打印数组元素
    void PrintArr(int* arr, int length)
    {
    	for (int i = 0; i < length; i++)
    	{
    		printf("%d ", arr[i]);
    	}
    	printf("\n");
    	return;
    }
    
    int main(int argc, char *argv[])
    {
    	srand((size_t)time(NULL));//设置随机种子
    	int arr[MAXSIZE] = { 0 };
    	//给每个元素设置一个随机值
    	for (int i = 0; i < MAXSIZE; i++)
    	{
    		int num = rand() % MAXNUM;
    		arr[i] = num;
    	}
    	printf("排序前:\n");
    	PrintArr(arr, MAXSIZE);
    	printf("直接插入排序升序:\n");
    	InsertSort_Up(arr, MAXSIZE);
    	PrintArr(arr, MAXSIZE);
    	printf("直接插入排序降序:\n");
    	InsertSort_Down(arr, MAXSIZE);
    	PrintArr(arr, MAXSIZE);
    	return 0;
    }

# 运行结果检测 #

![20180222191121268][]

[20180222191121268]: /images/20220531/d1d0f2f8c782441bbbbcf5ab34e0c746.png