C语言-直接插入排序算法

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

废话不多说先看看代码

#define  _CRT_SECURE_NO_WARNINGS 1
//直接插入排序法
#include <stdio.h>

void Compare(int arr[], int len)
{
	int i = 0;
	for (i = 0; i < len-1; i++)//len减一因为要插入的数是i+1
	{
		int M = i;//记录有序列表最后应该元素下标
		int num = arr[i + 1];//要插入的数
		while (M >= 0)
		{
			if (num < arr[M])//继续比较
			{
				arr[M + 1] = arr[M];//交换数值
				M--;
			}
			else
			{
				break;
			}
		}
		arr[M + 1] = num;
	}
}
int main()
{
	int arr[] = { 2,3,4,1,2,34,4,56,3,434,4 };
	int len = sizeof(arr) / 4;
	int i = 0;
	Compare(arr,len);
	for (i = 0; i < len; i++)
	{
		printf("%d ", arr[i]);
	}

	return 0;
}

一、什么是直接插入排序

 

        就像玩扑克时相同,假设前n-1项是有序数列,现在将第n项插入其中,使得前n项有序。然后依次进行插入,直到将整个数列全部插入,排序完成。

        对于一组数据我们无法得知是否有序,但第一个元素只有一个,所以是有序的,所以将第一个元素作为第一个有序数列。后面的数值依次插入其中·。

二、代码讲解

void Compare(int arr[], int len)

首先创建一个插入排序的函数,需要传入数组和数据个数,因此创建int arr[],int len两个形参。

void Compare(int arr[], int len)
{
	int i = 0;
	for (i = 0; i < len-1; i++)//len减一因为要插入的数是i+1
	{
		int M = i;//记录有序列表最后应该元素下标
		int num = arr[i + 1];//要插入的数
		while (M >= 0)
		{
			if (num < arr[M])//继续比较
			{
				arr[M + 1] = arr[M];//交换数值
				M--;
			}
			else
			{
				break;
			}
		}
		arr[M + 1] = num;
	}
}

因为插入排序是由前一个和后一个数据进行比较的,所以比较次数为(数据个数-1)。

int M = i;//记录有序列表最后应该元素下标
		int num = arr[i + 1];//要插入的数

这里需要前后两个数据比较,且这两个需要比较的数据是变化的,所以创建表示两个数据的变量。

	while (M >= 0)
		{
			if (num < arr[M])//继续比较
			{
				arr[M + 1] = arr[M];//交换数值
				M--;
			}
			else
			{
				break;
			}
		}
		arr[M + 1] = num;

利用循环进行比较,如果后一个数比前一个数小,就交换位置(数值)。如果后一个数比前一个数更大,break跳出循环。

当每一次循环比较到最后一次时,需要将两个数进行最后的交换,因为之前只是将arr[M]的值赋给了arr[M+1],此时需要将arr[M+1]的值赋给arr[M]才算完成数值交换,否则会出现比较数据丢失和重复的问题。此时的M--了的,所以需要M+1得到所需要的数据下标进行交换。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码

)">
< <上一篇
下一篇>>