背景知识:
- 排序算法算是比较基础的算法了,但是在面试过程中偶尔也会被问到,虽然很多语言都内置了排序函数,例如php的sort函数等等,但是还是有必要聊聊排序算法,这篇文章中将介绍时间复杂度为O(N^2)的几个排序算法。
- 本文基于从小到大排序讲解。
1.冒泡排序:前一个和后一个比较,如果前一个比后一个大则交换位置,继续向下比较。如果前一个比后一个小则不交换位置,继续向下比较。
//冒泡排序
class Bubble{
public $array;
public function __construct($array)
{
$this->array=$array;
}
//交换两个值的位置
protected function swap($left,$right){
$temp=$this->array[$left];
$this->array[$left]=$this->array[$right];
$this->array[$right]=$temp;
}
//冒泡核心算法:注意外层循环,一趟遍历之后最后一个元素为最大值也是排序之后应该在的位置
//因此下一趟排序就不需要考虑最后一个值,因此是$end--
public function getBubbleSort(){
//简单的判断待排序的数组是否合法
if(!is_array($this->array)||count($this->array)<2){
return $this->array;
}
//
for($end=count($this->array)-1;$end>0;$end--){
for ($i=0;$i<$end;$i++){
if($this->array[$i]>$this->array[$i+1]){
$this->swap($i,$i+1);
}
}
}
return $this->array;
}
}
$bubble=new Bubble(array(2,1,8,3,6,5));
var_dump($bubble->getBubbleSort());
2.选择排序:序列中最小的值和起始位置的值交换
<?php
class Select {
public $array;
public function __construct($array)
{
$this->array=$array;
}
protected function swap($left,$right){
$temp=$this->array[$left];
$this->array[$left]=$this->array[$right];
$this->array[$right]=$temp;
}
//选择排序的核心算法:注意内层循环是从$i+1开始的
public function getSelectSort(){
for ($i=0;$i<count($this->array);$i++){
//存放的是最小值的下标
$minIndex=$i;
for ($j=$i+1;$j<count($this->array);$j++){
$minIndex=$this->array[$j]>$this->array[$i]?:$j;
}
$this->swap($i,$minIndex);
}
return $this->array;
}
}
$select=new Select(array(2,1,4,7,6,5));
var_dump($select->getSelectSort());
3.插入排序:当前位置的值和前一个位置的值比较,如果比前一个位置的值小,则交换位置,然后再向前一个位置的值比较,直到比前一个位置的值大,则本躺循环结束。
<?php
//插入排序简单的逻辑就是当前元素和之前的元素比较
class Insert{
public $array;
public function __construct($array)
{
$this->array=$array;
}
protected function swap($left,$right){
$temp=$this->array[$left];
$this->array[$left]=$this->array[$right];
$this->array[$right]=$temp;
}
//插入排序的核心算法:外层循环$i从1开始,因为要保证前一个位置每越界
//内层循环从$i-1开始。
//这里有一点需要注意:如果当前位置($j)比后一个位置($j+1)要小,内层循环就直接结束了,因为$j之前位置的值也一定比$j+1位置的值要小
public function getInsertSort(){
for($i=1;$i<count($this->array);$i++){
for ($j=$i-1;$j>=0 && $this->array[$j]>$this->array[$j+1];$j--){
$this->swap($j,$j+1);
}
}
return $this->array;
}
}
$select=new Insert(array(2,1,4,7,6,5,2));
var_dump($select->getInsertSort());
以上就是时间复杂度为O(N^2)的几个排序算法了。