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

从本文开始,会陆续记录自己学习的算法,并尽量用PHP语言和C语言表示出来,更好的去理解算法,和实践

选择排序:首先找到数组中最小的那个元素;其次,将它和数组的第一个元素交换位置(如果第一个元素就是最小的元素 那么它就和自己交换);再次,在剩下的元素中找到最小的元素,将它与数组第二个元素交换位置,如此往复,直到将整个数组排序(不断的选择剩余元素中的最小元素)

用PHP演示选择排序

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

  /*
  选择排序PHP语言实现版
  假设为N个元素的整数数组array(),进行排序.
  主要为了理解突出算法,没有整型 类型验证等等
  */
  //一个整数数组有N个元素,$arr=array(); eg:
  $arr=array(1,4,6,3,4,8,2,0);
  //计算数组中元素的个数
  $element_count = count($arr);
  for( $i=0; $i<$element_count; $i++){
    $min=$i;
    for( $j=$i+1; $j<$element_count; $j++){
      //找出最小的元素
      if ( $arr[$j] < $arr[$min] ){
                $min=$j;
            }
        }

        //交换元素,将小元素交换到前面的$arr[$i]处
        $tmp=$arr[$i];
        $arr[$i]=$arr[$min];
        $arr[$min]=$tmp;
    }
    //打印出排序后的数组;测试之用
    print_r( $arr ); 
?>

用C语言演示程序

/*
选择排序的算法 C语言实现
涉及数组初始化元素的具体个数,类型声明与一致性
*/
#include <stdio.h>

/*求数组元素个数的函数
int array_count(int *p)
{
  int length=1;
  for(;*p!='\0';p++)
  length++;
  return length;
}
*/

int main(void)
{
  /* 有n个元素的数组,
    int arr[n]; 下面举个具体例子
   */
  int numbers[]= { 1, 4, 6, 3, 4, 8, 2, 0};
  /* 计算数组中元素数目 ,也可以自己构造一个求数组长度的函数
  * eg:如上count函数,去掉注释,可替换下一条语句,调用count函数 获取数组元素数目
  */
  //int element_count=array_count(numbers);
  int element_count=(sizeof numbers)/(sizeof numbers[0]);
  //声明for循环中要用到的变量
  int i,j,min,tmp,y;
  for( i=0; i < element_count; i++)
  {
    min = i;
    //寻找剩余元素的最小元素
    for( j=i+1; j < element_count; j++)
    {
      if( numbers[j] < numbers[min] )
      {
        min=j;
      }
    }
    //交换元素
    tmp = numbers[i];
    numbers[i] = numbers[min];
    numbers[min] = tmp;
  }
  //for语句,测试输出 ...
  for(y=0;y<element_count; y++)
  {
    printf("%d \n",numbers[y]);
  }

  return 0;
}

 

由程序演绎归纳,对于长度为N的数组,选择排序需要进行N次交换,和(N²-N)/2比较。

选择算法有两个特点。

1. 运行时间和输入无关。为了找到最小的元素总会去扫描所有剩余的元素。有时也是缺点,因为扫描一个有顺序的数组和一个杂乱无章的数组执行时间是相同的

2.数据移动是最少的,本算法,数据只移动了N次。其他算法不具备这种线性关系。

 

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>