第C語(yǔ)言直接插入排序算法介紹目錄前言一、什么是直接插入排序二、代碼講解總結(jié)

前言

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

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

#define_CRT_SECURE_NO_WARNINGS1

//直接插入排序法

#includestdio.h

voidCompare(intarr[],intlen)

inti=0;

for(i=0;ilen-1;i++)//len減一因?yàn)橐迦氲臄?shù)是i+1

intM=i;//記錄有序列表最后應(yīng)該元素下標(biāo)

intnum=arr[i+1];//要插入的數(shù)

while(M=0)

if(numarr[M])//繼續(xù)比較

arr[M+1]=arr[M];//交換數(shù)值

M--;

else

break;

arr[M+1]=num;

intmain()

intarr[]={2,3,4,1,2,34,4,56,3,434,4};

intlen=sizeof(arr)/4;

inti=0;

Compare(arr,len);

for(i=0;ilen;i++)

printf("%d",arr[i]);

return0;

}

一、什么是直接插入排序

就像玩撲克時(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ù)值依次插入其中·。

二、代碼講解

voidCompare(intarr[],intlen)

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

voidCompare(intarr[],intlen)

inti=0;

for(i=0;ilen-1;i++)//len減一因?yàn)橐迦氲臄?shù)是i+1

intM=i;//記錄有序列表最后應(yīng)該元素下標(biāo)

intnum=arr[i+1];//要插入的數(shù)

while(M=0)

if(numarr[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）。

intM=i;//記錄有序列表最后應(yīng)該元素下標(biāo)

intnum=arr[i+1];//要插入的數(shù)

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

while(M=0)

if(numarr[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í)需要