#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減一因為要插入的數(shù)是i+1
	{
		int M = i;//記錄有序列表最后應該元素下標
		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è)前n-1項是有序數(shù)列，現(xiàn)在將第n項插入其中，使得前n項有序。然后依次進行插入，直到將整個數(shù)列全部插入，排序完成。

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

二、代碼講解

void Compare(int arr[], int len)

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

void Compare(int arr[], int len)
{
	int i = 0;
	for (i = 0; i < len-1; i++)//len減一因為要插入的數(shù)是i+1
	{
		int M = i;//記錄有序列表最后應該元素下標
		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;
	}
}

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

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

這里需要前后兩個數(shù)據(jù)比較，且這兩個需要比較的數(shù)據(jù)是變化的，所以創(chuàng)建表示兩個數(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)進行比較，如果后一個數(shù)比前一個數(shù)小，就交換位置（數(shù)值）。如果后一個數(shù)比前一個數(shù)更大，break跳出循環(huán)。

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