为什么学习排序算法

排序和查找是计算机专业课程数据结构和算法中最重要的部分之一，也是编程中常用的基础知识。C语言初学者对直接插入、简单选择两种最简单的排序算法必须掌握，足以应付一般的考试、课程设计、小程序编写。

但是对于计算机专业、编程开发的同学，必须熟练掌握这12个算法，达到手写算法的程序，排序算法在算法能力训练、考研笔试和机试、工作面试、真实软件项目中普遍使用。

C语言必须的12个排序算法文章系列，每篇文章介绍一个算法，使用C语言实现一个排序算法，这些代码可以作为模板代码，大家可以收藏，方便编程使用。

备注：所有排序算法程序，默认均为从小到大排序，至于从大到小，可以简单修改比较方式即可实现。另外所有程序都是独立可运行的完整C语言程序，而不仅仅知识给出一个函数或伪代码。

直接插入排序算法基本思想

每次循环，将当前的一个记录插入到之前已经插入排序好的有序子表中，从而得到一个新的、记录数增加1的有序子表。

例如：给定10个整数：(4,3,1,2,6,5,0,9,8,7) 从小到大排序。

首先排序第1个数据 4，因为此时只有一个数据，无需排序，肯定有序，得到有序子表(4)；

再看第2个数据 3，和之前4发现小，因此需要插入到4前面，首先将4向后移动占用1的位置，空出位置将3插入到原来4的位置，得到有序子表(3,4)；

第3个数据 1，依次和有序子表(3,4)比较，发现小于它们，因此将4后移位置占用1的位置，将3也后移，将1直接插入到原来3的位置，得到(1,3,4)；

…依次循环，完成10个整数排序。

很明显，每次只处理一个数据，每次数据比较后，移动前面数据的位置，插入到合适位置。

直接插入算法时间复杂度是O(n^2)，需要一个记录大小的辅助空间，算法是稳定的排序。

代码实现

读代码是最精确的学习方式，建议大家多读。

第一种方式：

/*#include 
   
    void insert_sort(int a[], int length){int i,j;int t;for(i=1; i
    
     =0 && t < a[j]; j--)a[j+1] = a[j];a[j+1] = t;}}}int main(void){    int a[10] = {4,3,1,2,6,5,0,9,8,7};    insert_sort(a,10);    int i;    for(i=0; i<10; i++)      printf("%d ", a[i]);    return 0;}

很明显，insert_sort函数中，需要临时变量t保存待排数据记录，因此需要一个辅助空间，两层循环，时间复杂度是O(n^2)

第二种方式：在保存数据记录的数组中，增加一个空间a[0]，用作监视哨，a[0]单元作为辅助空间，这样不需要临时变量t，也不需要判断 j>=0防止数组下标出界。这是很精巧的设计，很多教材中均有介绍。

/*#include 
   
    // a[0]临时辅助空间，数据从a[1]开始 void insert_sort(int a[], int length){int i,j;for(i=2; i<=length; i++){if(a[i] < a[i-1] ){a[0] = a[i];a[i] = a[i-1];for(j=i-2; a[0] < a[j]; j--)a[j+1] = a[j];a[j+1] = a[0];}}}int main(void){// a[0] 不保存数据     int a[11] = {0,4,3,1,2,6,5,0,9,8,7};    insert_sort(a,10);    int i;    for(i=1; i<=10; i++)      printf("%d ", a[i]);    return 0;}

其实做为一个学习者，有一个学习的氛围跟一个交流圈子特别重要这里我推荐一个C/C++基础交流583650410，不管你是小白还是转行人士欢迎入驻，大家一起交流成长。

转载地址：http://ddjwi.baihongyu.com/

你可能感兴趣的文章