C語言之直接插入排序算法的方法

更新時間：2021年12月22日 15:00:57 作者：紳士·永

這篇文章主要為大家介紹了C語言直接插入排序算法的方法，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助

#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])//繼續(xù)比較
			{
				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)

首先創(chuàng)建一個插入排序的函數，需要傳入數組和數據個數，因此創(chuàng)建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])//繼續(xù)比較
			{
				arr[M + 1] = arr[M];//交換數值
				M--;
			}
			else
			{
				break;
			}
		}
		arr[M + 1] = num;
	}
}

因為插入排序是由前一個和后一個數據進行比較的，所以比較次數為（數據個數-1）。

int M = i;//記錄有序列表最后應該元素下標
		int num = arr[i + 1];//要插入的數

這里需要前后兩個數據比較，且這兩個需要比較的數據是變化的，所以創(chuàng)建表示兩個數據的變量。

	while (M >= 0)
		{
			if (num < arr[M])//繼續(xù)比較
			{
				arr[M + 1] = arr[M];//交換數值
				M--;
			}
			else
			{
				break;
			}
		}
		arr[M + 1] = num;

利用循環(huán)進行比較，如果后一個數比前一個數小，就交換位置（數值）。如果后一個數比前一個數更大，break跳出循環(huán)。

當每一次循環(huán)比較到最后一次時，需要將兩個數進行最后的交換，因為之前只是將arr[M]的值賦給了arr[M+1],此時需要將arr[M+1]的值賦給arr[M]才算完成數值交換，否則會出現比較數據丟失和重復的問題。此時的M--了的，所以需要M+1得到所需要的數據下標進行交換。