日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

C語言直接插入排序算法介紹_C 語言

作者：紳士·永 ? 更新時間： 2022-03-09 編程語言

前言

直接 插入排序 （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得到所需要的數據下標進行交換。

總結

原文鏈接：https://blog.csdn.net/weixin_63246064/article/details/122050587

欄目分類
最近更新