C語(yǔ)言直接插入排序算法介紹

更新時(shí)間：2021年12月21日 09:08:33 作者：紳士·永

大家好，本篇文章主要講的是C語(yǔ)言直接插入排序算法介紹，感興趣的同學(xué)趕快來(lái)看一看吧，對(duì)你有幫助的話記得收藏一下，方便下次瀏覽

前言

直接插入排序（Straight Insertion Sort）是一種最簡(jiǎn)單的排序方法，其基本操作是將一條記錄插入到已排好的有序表中，從而得到一個(gè)新的、記錄數(shù)量增1的有序表。.

廢話不多說(shuō)先看看代碼

#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減一因?yàn)橐迦氲臄?shù)是i+1
	{
		int M = i;//記錄有序列表最后應(yīng)該元素下標(biāo)
		int num = arr[i + 1];//要插入的數(shù)
		while (M >= 0)
		{
			if (num < arr[M])//繼續(xù)比較
			{
				arr[M + 1] = arr[M];//交換數(shù)值
				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;
}

一、什么是直接插入排序

? ? ? ? 就像玩撲克時(shí)相同，假設(shè)前n-1項(xiàng)是有序數(shù)列，現(xiàn)在將第n項(xiàng)插入其中，使得前n項(xiàng)有序。然后依次進(jìn)行插入，直到將整個(gè)數(shù)列全部插入，排序完成。

? ? ? ? 對(duì)于一組數(shù)據(jù)我們無(wú)法得知是否有序，但第一個(gè)元素只有一個(gè)，所以是有序的，所以將第一個(gè)元素作為第一個(gè)有序數(shù)列。后面的數(shù)值依次插入其中·。

二、代碼講解

void Compare(int arr[], int len)

首先創(chuàng)建一個(gè)插入排序的函數(shù)，需要傳入數(shù)組和數(shù)據(jù)個(gè)數(shù)，因此創(chuàng)建int arr[],int len兩個(gè)形參。

void Compare(int arr[], int len)
{
	int i = 0;
	for (i = 0; i < len-1; i++)//len減一因?yàn)橐迦氲臄?shù)是i+1
	{
		int M = i;//記錄有序列表最后應(yīng)該元素下標(biāo)
		int num = arr[i + 1];//要插入的數(shù)
		while (M >= 0)
		{
			if (num < arr[M])//繼續(xù)比較
			{
				arr[M + 1] = arr[M];//交換數(shù)值
				M--;
			}
			else
			{
				break;
			}
		}
		arr[M + 1] = num;
	}
}

因?yàn)椴迦肱判蚴怯汕耙粋€(gè)和后一個(gè)數(shù)據(jù)進(jìn)行比較的，所以比較次數(shù)為（數(shù)據(jù)個(gè)數(shù)-1）。

int M = i;//記錄有序列表最后應(yīng)該元素下標(biāo)
		int num = arr[i + 1];//要插入的數(shù)

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

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

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

當(dāng)每一次循環(huán)比較到最后一次時(shí)，需要將兩個(gè)數(shù)進(jìn)行最后的交換，因?yàn)橹爸皇菍rr[M]的值賦給了arr[M+1],此時(shí)需要將arr[M+1]的值賦給arr[M]才算完成數(shù)值交換，否則會(huì)出現(xiàn)比較數(shù)據(jù)丟失和重復(fù)的問(wèn)題。此時(shí)的M--了的，所以需要M+1得到所需要的數(shù)據(jù)下標(biāo)進(jìn)行交換。