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

概述本文章向大家介绍数据结构与算法 (三) 插入排序，主要包括数据结构与算法 (三) 插入排序使用实例、应用技巧、基本知识点总结和需要注意事项，具有一定的参考价值，需要的朋友可以参考一下。

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^)

总结

以上是内存溢出为你收集整理的数据结构与算法 (三) 插入排序全部内容，希望文章能够帮你解决数据结构与算法 (三) 插入排序所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。