数据结构与算法 (三) 插入排序

1.算法思想

? ? ? 插入排序的思想是每次选择排序的记录序列的第1个记录，按照排序码的大小将其插入已排序的记录序列中的适当位置，直到所有记录全部排序完毕

2.算法原理

? ? ? 先将第1个记录视为一个有序的记录序列，然后从第2个记录开始，依次将未排序的记录插入这个有序的记录序列中，直到整个文件中的全部记录排序完毕，在排序过程中，前面的记录序列是已经排好序的，而后面的记录序列有待排序处理

3.算法实现

sort.h

typedef int ElementType;

struct forSort

{

ElementType key;

};

typedef struct forSort ForSort;

void InitForSort(ForSort *FS,int a)

{

FS->key=a;

}

main.c

#include

#include

#include "sort.h"

void DirectInsertionSort(ForSort A[],int n)

{

int i,j;

ForSort temp;

for(i=1; i

{

j=i;

temp= A[i];

//此处判断temp 是否比j-1小 如果比temp.key大 向前移动文件 空出 j 这个位置

while(j>0 && temp.key

{

A[j]=A[j-i];

j--;

}

//将空出j 的位置的值加入文件 由此看出插入排序是稳定排序

A[j]=temp;

}

}

int main(){

int i;

int A[8]={28,13,72,85,39,41,6,20};

DirectInsertionSort(A,8);

for(i=0;i<8;i++){

printf("%dn",A[i]);

}

return 1;

}

//时间复杂度 是总的比较次数是 n(n-1)/2 时间复杂度为O(n^)

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!