算法之“插入排序”(PHP与C语言实现)

插入排序:人们摸牌时的方法是一张一张的摸,然后将每张牌插入到其他已经有序的牌中的适当的位置。在计算机的实现中,为了给要插入的元素腾出空间,我们需要将其余所有元素在插入之前都向右移动一位。这种算法就是插入排序。

PHP实现

<?php
  //字符编码
  header("Content-type:text/html;charset=utf-8");

  /*
  插入排序 PHP实现
  将一个元素与它之前的有序元素倒序比较,小于时就交换,
  直到找到大于时就插入成功
  */
  //一个数组 $arr=array(); eg:
  $arr = array( 5, 4, 7, 3, 9, 3, 8, 6);
  //获取数组元素个数
  $element_count = count( $arr );
  for( $i=0; $i<$element_count ; $i++) {
        //与其前面元素进行比较,比其小时,交换,再与前面元素比较
        for( $j=$i; $j>0 && ( $arr[$j] < $arr[$j-1] ) ; $j--) { 
            //交换元素
            $tmp = $arr[$j];
            $arr[$j] = $arr[$j-1];
            $arr[$j-1] = $tmp;
        }
    }
    //测试输出
    print_r($arr);
?>

C语言实现

/*
* 插入排序 C语言实现(C99)
* 将一个元素与它之前的有序元素倒序比较,小于时就交换,
* 直到找到大于时就插入成功
*/
#include <stdio.h>

int main(void){
    //声明一个数组,举一个实际的例子
    int numbers[] = { 5, 4, 7, 3, 9, 3, 8, 6};
    //计算数组元素个数,另一个实现方法 请参考 ”选择排序 C语言实现“
    int element_count = sizeof numbers / sizeof numbers[0];
    for(int i=0; i < element_count; i++){
        for(int j=i; j>0 && (numbers[j]<numbers[j-1]); j--){
            int tmp = numbers[j];
            numbers[j] = numbers[j-1];
            numbers[j-1] = tmp;
        }
    }

    for(int y=0; y < element_count; y++) {
        printf("%d\n", numbers[y]);
    }
}

上面两个实现中原理是,比较大小后,然后交换,然后再比较,最坏时会有N²/2次交换和N²/2次比较。最好时是N-1次比较和0次交换,平均情况是N²/4比较和N²/4交换。其实每次比较后插入是不必要的,就像摸牌时不会每次比较就插入一样,算法可以改进,下面是改进版的

PHP实现改进版

<?php
    //字符编码
    header("Content-type:text/html;charset=utf-8");
    /* 插入排序 PHP实现 将一个元素与它之前的有序元素倒序比较,小于时就交换, 直到找到大于时就插入成功 */
    
    //一个数组 $arr=array(); eg:
    $arr = array( 5, 4, 7, 3, 9, 3, 8, 6);
    //获取数组元素个数
    $element_count = count( $arr );
    for( $i=0; $i<$element_count ; $i++) {
        $tmp = $arr[$i]; $j=$i;
        //与其前面元素进行比较,比其小时,将前面元素后移
        for( $j; $j>0 && ( $tmp < $arr[$j-1] ) ; $j--) {
            //后移元素
            $arr[$j] = $arr[$j-1];
        }
        //将找到的位置上插入该元素
        $arr[$j]=$tmp;
    }
    //测试输出
    print_r($arr);
?>

C语言实现改进版

/*
* 插入排序 C语言实现(C99)
* 将一个元素与它之前的有序元素倒序比较,小于时就交换,
* 直到找到大于时就插入成功
*/
#include <stdio.h>

int main(void){
    //声明一个数组,举一个实际的例子
    int numbers[] = { 5, 4, 7, 3, 9, 3, 8, 6};
    //计算数组元素个数,另一个实现方法 请参考 ”选择排序 C语言实现“
    int element_count = sizeof numbers / sizeof numbers[0];
    for(int i=0; i < element_count; i++){
        int tmp = numbers[i];
        int j=i;
        //比较,如果前面元素比它大,就后移
        for( ; j>0 && ( tmp < numbers[j-1]); j--){
            numbers[j] = numbers[j-1];
        }
        //最后找到的位置插入
        numbers[j]=tmp;
    }

    for(int y=0; y < element_count; y++) {
        printf("%d\n", numbers[y]);
    }
}

 

这下交换的次数就少了,变成只右移,最后一次插入,执行时间势必缩短了

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>