php常用的四种排序算法

作者: siediyer 分类: PHP 发布时间: 2015-10-14 11:44

1.插入排序

思想:

每次将一个待排序的数据元素插入到前面已经排好序的数列中,使数列依然有序,知道待排序数据元素全部插入完为止。

示例:

[初始关键字] [49] 38 65 97 76 13 27 49
J=2(38) [38 49] 65 97 76 13 27 49
J=3(65) [38 49 65] 97 76 13 27 49
J=4(97) [38 49 65 97] 76 13 27 49
J=5(76) [38 49 65 76 97] 13 27 49
J=6(13) [13 38 49 65 76 97] 27 49
J=7(27) [13 27 38 49 65 76 97] 49
J=8(49) [13 27 38 49 49 65 76 97]

时间复杂度:

如果目标是把n个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况。最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需(n-1)次即可。最坏情况就是,序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1)次。平均来说插入排序算法的时间复杂度为O(n^2)。因而,插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择。

代码:

function insert_sort($arr){   
    $count = count($arr);   
    for($i=1; $i<$count; $i++){   
        $tmp = $arr[$i];   
        $j = $i - 1;   
        while($arr[$j] > $tmp){   
            $arr[$j+1] = $arr[$j];   
            $arr[$j] = $tmp;   
            $j--;   
         }   
     }   
    return $arr;   
}

2.选择排序

思想:每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。

示例:

[初始关键字] [49 38 65 97 76 13 27 49]
第一趟排序后 13 [38 65 97 76 49 27 49]
第二趟排序后 13 27 [65 97 76 49 38 49]
第三趟排序后 13 27 38 [97 76 49 65 49]
第四趟排序后 13 27 38 49 [49 97 65 76]
第五趟排序后 13 27 38 49 49 [97 97 76]
第六趟排序后 13 27 38 49 49 76 [76 97]
第七趟排序后 13 27 38 49 49 76 76 [ 97]
最后排序结果 13 27 38 49 49 76 76 97

时间复杂度:

时间复杂度为o(n2),不稳定排序,适合规模比较小的

代码:

//选择排序(一维数组)   
function select_sort($arr){   
    $count = count($arr);   
    for($i=0; $i<$count; $i++){   
        $k = $i;   
        for($j=$i+1; $j<$count; $j++){   
            if ($arr[$k] > $arr[$j])   
                $k = $j;   
            if ($k != $i){   
                $tmp = $arr[$i];   
                $arr[$i] = $arr[$k];   
                $arr[$k] = $tmp;   
             }   
         }   
     }   
    return $arr;   
}

3.冒泡排序

思想:

两两比较待排序数据元素的大小,发现两个数据元素的次序相反时即进行交换,直到没有反序的数据元素为止。

示例:

 

49 13 13 13 13 13 13 13
38 49 27 27 27 27 27 27
65 38 49 38 38 38 38 38
97 65 38 49 49 49 49 49
76 97 65 49 49 49 49 49
13 76 97 65 65 65 65 65
27 27 76 97 76 76 76 76
49 49 49 76 97 97 97 97

时间复杂度:

该算法的时间复杂度为O(n2)。但是,当原始关键字序列已有序时,只进行一趟比较就结束,此时时间复杂度为O(n)。

代码:

//冒泡排序(一维数组)   
function bubble_sort($array){   
    $count = count($array);   
    if ($count <= 0) return false;   
    for($i=0; $i<$count; $i++){   
        for($j=$count-1; $j>$i; $j--){   
            if ($array[$j] < $array[$j-1]){   
                $tmp = $array[$j];   
                $array[$j] = $array[$j-1];   
                $array[$j-1] = $tmp;   
             }   
         }   
     }   
    return $array;   
}

4.快速排序

思想:

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

示例:

 

初始关键字 [49 38 65 97 76 13 27 49]
一趟排序之后 [27 38 13] 49 [76 97 65 49]
二趟排序之后 [13] 27 [38] 49 [49 65]76 [97]
三趟排序之后 13 27 38 49 49 [65]76 97
最后的排序结果 13 27 38 49 49 65 76 97

时间复杂度:

快速排序主体算法时间运算量约 O(log2n) ,划分子区函数运算量约 O(n) ,所以总的时间复杂度为 O(nlog2n) ,它显然优于冒泡排序 O(n2). 可是算法的优势并不是绝对的。试分析,当原文件关键字有序时,快速排序时间复杂度是 O(n2), 这种情况下快速排序不快。而这种情况的冒泡排序是 O(n), 反而很快。在原文件记录关键字无序时的多种排序方法中,快速排序被认为是最好的一种排序方法。

代码:

function quick_sort($array){   
  if (count($array) <= 1) return $array;    
  
  $key = $array[0];   
  $left_arr = array();   
  $right_arr = array();   
  for ($i=1; $i<count($array); $i++){   
    if ($array[$i] <= $key)   
      $left_arr[] = $array[$i];   
    else  
      $right_arr[] = $array[$i];   
  }   
  $left_arr = quick_sort($left_arr);   
  $right_arr = quick_sort($right_arr);    
  
  return array_merge($left_arr, array($key), $right_arr);   
}

几种排序算法的比较和选择
1. 选取排序方法需要考虑的因素:
(1) 待排序的元素数目n;
(2) 元素本身信息量的大小;
(3) 关键字的结构及其分布情况;
(4) 语言工具的条件,辅助空间的大小等。
2. 小结:
(1) 若n较小(n <= 50),则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多,因而当记录本身信息量较大时,用直接选择排序较好。
(2) 若文件的初始状态已按关键字基本有序,则选用直接插入或冒泡排序为宜。
(3) 若n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序。 快速排序是目前基于比较的内部排序法中被认为是最好的方法。
(4) 在基于比较排序方法中,每次比较两个关键字的大小之后,仅仅出现两种可能的转移,因此可以用一棵二叉树来描述比较判定过程,由此可以证明:当文件的n个关键字随机分布时,任何借助于”比较”的排序算法,至少需要O(nlog2n)的时间。
(5) 当记录本身信息量较大时,为避免耗费大量时间移动记录,可以用链表作为存储结构。

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!

Title - Artist
0:00