"啃下"插入排序

2018-06-18 04:18:27来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

插入排序法基本原理

  插入排序法较冒泡排序法和选择排序法更贴近生活,应该来说理解起来更快。如果你现在能够得到一副麻将,请把里面的“一万”到“六万”拿出来,打乱顺序,再重新排好,就像打麻将开始那样。是否需要拿出某个麻将拿出来再插入其它麻将之间?这就是插入排序了。不过计算机没有你那么聪明,你只要小小几步就可以将麻将排序好,而计算机还要一个一个地比较,但是,它超快的速度使你根本不知道它的笨拙!同样,你也可以用扑克牌来试试。这里引用网络上的图片来理解这个排序方法。

 

  我们设定两个数组定位的变量i和j。array[i]指向数组第2~最后一个元素,我们用array[j]表示第0~i之前的最后一个元素,通过依次比较array[i]与array[j],array[j - 1],...直到比较到比它小的元素。因为终止比较时,array[j]指向一个比要插入的元素小的元素,而array[j + 1]和array[j + 2]是内容相同的元素,因此,我们要把array[i]插入到array[j + 1]。

  再来结合上图看代码(仔细分析,认真理解):

#include <stdio.h>
#include <stdlib.h>

#define SIZE 10

int main(int argc, char * argv[]){
    int i, j, temp, array[SIZE] = {5,1,8,9,4,6,3,2,7,0};
    
    for(i = 1; i < SIZE; i++){ //排序开始,把i初值定为数组第二个元素
        temp = array[i]; //保存这个元素,然后方便比较和排序
        for(j = i - 1; j >= 0 && array[j] > temp; j--)
        //j最初表示i的前一个元素,通过与array[i]大小后,找到一个可插入的位置array[j + 1]
            array[j + 1] = array[j];//大的元素向后移,关键!
        array[j + 1] = temp; //插入!!!
    }
    
    for(i = 0; i < SIZE; i++)
        printf("%-5d",array[i]);
        
    getch();
    return 0;
}

  这里需要注意的是,array[0]~array[i]是已经排序好的数组,我们称它为子数组,将array[i]后面的元素依次插入子数组直到没有元素可以插入,这个子数组就是整个数组,排序完成。

  有些地方出现的代码和上面的代码可能会不同,第二个循环我们用的是for而不是while。因为冒泡,选择,排序这样简单的排序算法都可以用一个for循环嵌套另一个for循环表示,为了方便记忆,我使用了前者。这里给出第二个循环用的是while的代码:

#include <stdio.h>
#include <stdlib.h>

#define SIZE 10

int main(int argc, char * argv[]){
    int i, j, temp, array[SIZE] = {5,1,8,9,4,6,3,2,7,0};
    
    for(i = 1; i < SIZE; i++){ //道理是一样的
        j = i - 1;
        temp = array[i];
        while(j >= 0 && array[j] > temp){
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = temp; 
    }
    
    for(i = 0; i < SIZE; i++)
        printf("%-5d",array[i]);
        
    getch();
    return 0;
}

  如果不理解,请照着代码把麻将或扑克牌排序几遍!

运行结果:

附:算法导论对插入排序法的介绍

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:解读 C 语言中的指针

下一篇:C语言编写的简单的电话本管理系统