数据结构和算法--常见排序

数据结构和算法--常见排序

排序算法

在选择排序算法的时候,通常会根据以下几个维度来考虑

时间复杂度
空间复杂度(对内存空间的消耗)
算法的稳定性(如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变)

冒泡排序(只会操作相邻的两个数据)

冒泡排序只会操作相邻的两个数据。

每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求,如果不满足就让它俩互换。由于在排序过程中总是小数往前放,大数往后放,相当于气泡往上升,所以称作冒泡排序。

但其实在实际过程中也可以根据自己需要反过来用,大树往前放,小数往后放。

$numbers = [4, 5, 6, 3, 2, 1];
$cnt = count($numbers);
for ($i = 0; $i < $cnt; $i++) {
for ($j = 0; $j < $cnt - $i - 1; $j++) {
if ($numbers[$j] > $numbers[$j + 1]) {
$temp = $numbers[$j];
$numbers[$j] = $numbers[$j + 1];
$numbers[$j + 1] = $temp;
}
}
}
var_dump($numbers);

冒泡排序的性能和稳定性

时间复杂度: O(n^2) (n的平方)
空间复杂度:只涉及相邻元素的交换,是原地排序算法
算法稳定性:元素相等不会交换,是稳定的排序算法

总结:时间复杂度是 O(n^2),看起来性能并不是很好,所以我们在实践中基本不会选用冒泡算法。

插入排序

将数组中的数据分为两个区间,已排序区间和未排序区间。

初始已排序区间只有一个元素,就是数组的第一个元素。

插入算法的核心思想是取未排序区间中的元素,在已排序区间中找到合适的插入位置将其插入,并保证已排序区间数据一直有序。重复这个过程,直到未排序区间中元素为空,算法结束。

其实就是:将插入的数据保存在变量中,与数组中的每个数比较 找到合适的位置 进行插入

$nums = [4, 5, 6, 3, 2, 1];

for ($i = 0; $i < count($nums); $i++) {

$value = $nums[$i]; //在这里把值赋值给一个变量

$j = $i - 1;
for (;$j >= 0; $j--) {

if ($nums[$j] > $value) {
#通过这些注释掉的代码,可以知道运行原理.
#echo '<pre>';
#var_dump($nums[$j+1],$nums[$j]);
#echo '<pre>';
$nums[$j+1] = $nums[$j];
#echo '<pre>';
#var_dump($nums);
#echo '<pre>';
} else {
break;
}
}
$nums[$j+1] = $value;
}

var_dump($nums);

插入排序的性能和稳定性

时间复杂度: O(n^2) (n的平方)

空间复杂度:只涉及相邻元素的交换,是原地排序算法

算法稳定性:元素相等不会交换,是稳定的排序算法

插入排序的时间复杂度和冒泡排序一样,也不是很理想,但是插入排序不涉及数据交换,从更细粒度来区分,性能要略优于冒泡排序。

选择排序

选择排序主要是将假设数组中的第一个是最小的,循环与数组中的第一个进行比较 如果比其还小 则记录下标 进行数值交换 效率相对冒泡来说比较高

function selection_sort($nums)
{
if (count($nums) <= 1) {
return $nums;
}

for ($i = 0; $i < count($nums); $i++) {
$min= $i;
for ($j = $i + 1; $j < count($nums); $j++) {
if ($nums[$j] < $nums[$min]) {
$min = $j;
}
}
if ($min != $i) {
$temp = $nums[$i];
$nums[$i] = $nums[$min];
$nums[$min] = $temp;
}
}

return $nums;
}

$nums = [4, 5, 6, 3, 2, 1];
$nums = selection_sort($nums);
print_r($nums);

插入排序的性能和稳定性

选择排序的时间复杂度也是 O(n^2);
由于不涉及额外的存储空间,所以是原地排序;
由于涉及非相邻元素的位置交换,所以是不稳定的排序算法。

总结

综合比较上面介绍的三个排序算法,时间复杂度都是一样的,也都是原地排序,但是选择排序是不稳定的排序算法,此外,插入排序和冒泡排序相比较,插入排序只需要一条语句,而冒泡排序需要三条,在同等条件下,或者数据量很大的情况下,插入排序性能是要优于冒泡排序的.

所以综合比较下来,三者的优先级是 插入排序 > 冒泡排序 >> 选择排序。
但是三者的时间复杂度都是 O(n^2),数据量很大的情况下性能表现并不是很理想.(还有两种好于插入排序)

归并排序

要排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了.

undefined

$nums = [4, 5, 6, 3, 2, 1];
function merge_sort($nums)
{
if (count($nums) <= 1) {
return $nums;
}

merge_sort_c($nums, 0, count($nums) - 1);
return $nums;
}

function merge_sort_c(&$nums, $p, $r)
{
if ($p >= $r) {
return;
}

$q = floor(($p + $r) / 2);
merge_sort_c($nums, $p, $q);
merge_sort_c($nums, $q + 1, $r);

merge($nums, ['start' => $p, 'end' => $q], ['start' => $q + 1, 'end' => $r]);
}
function merge(&$nums, $nums_p, $nums_q)
{
$temp = [];
$i = $nums_p['start'];
$j = $nums_q['start'];
$k = 0;
while ($i <= $nums_p['end'] && $j <= $nums_q['end']) {
if ($nums[$i] <= $nums[$j]) {
$temp[$k++] = $nums[$i++];
} else {
$temp[$k++] = $nums[$j++];
}
}

if ($i <= $nums_p['end']) {
for (; $i <= $nums_p['end']; $i++) {
$temp[$k++] = $nums[$i];
}
}

if ($j <= $nums_q['end']) {
for (; $j <= $nums_q['end']; $j++) {
$temp[$k++] = $nums[$j];
}
}

for ($x = 0; $x < $k; $x++) {
$nums[$nums_p['start'] + $x] = $temp[$x];
}
}


$nums = [4, 5, 6, 3, 2, 1];
$nums = merge_sort($nums);
print_r($nums);

归并排序的性能和稳定性

归并排序不涉及相等元素位置交换,是稳定的排序算法.
时间复杂度是 O(nlogn).
需要额外的空间存放排序数据,不是原地排序.
最多需要和待排序数组同样大小的空间,所以空间复杂度是 O(n)。

快速排序(快排)

如果要排序数组中下标从 p 到 r 之间的一组数据,我们选择 p 到 r 之间的任意一个数据作为 pivot(分区点)。

我们遍历 p 到 r 之间的数据,将小于 pivot 的放到左边,将大于 pivot 的放到右边,将 pivot 放到中间。经过这一步骤之后,数组 p 到 r 之间的数据就被分成了三个部分,前面 p 到 q-1 之间都是小于 pivot 的,中间是 pivot,后面的 q+1 到 r 之间是大于 pivot 的。

undefined

首先要找到分区点 pivot,一般是取第一个或最后一个称为基准,然后就是比基准小的在左边,比基准大的放到右边,如何放做,就是和基准进行交换,这样交换完左边都是比基准小的,右边都是比较基准大的,这样就将一个数组分成了两个子数组,然后再按照同样的方法把子数组再分成更小的子数组,直到不能分解为止。
function quick_sort($nums)
{
if (count($nums) <= 1) {
return $nums;
}

quick_sort_c($nums, 0, count($nums) - 1);
return $nums;
}

function quick_sort_c(&$nums, $p, $r)
{
if ($p >= $r) {
return;
}

$q = partition($nums, $p, $r);
quick_sort_c($nums, $p, $q - 1);
quick_sort_c($nums, $q + 1, $r);
}
function partition(&$nums, $p, $r)
{
$pivot = $nums[$r];
$i = $p;
for ($j = $p; $j < $r; $j++) {
// 原理:将比$pivot小的数丢到[$p...$i-1]中,剩下的[$i..$j]区间都是比$pivot大的
if ($nums[$j] < $pivot) {
$temp = $nums[$i];
$nums[$i] = $nums[$j];
$nums[$j] = $temp;
$i++;
}
}

// 最后将 $pivot 放到中间,并返回 $i
$temp = $nums[$i];
$nums[$i] = $pivot;
$nums[$r] = $temp;

return $i;
}

$a = array(2,13,42,34,56,23,67,365,87665,54,68,3);
var_dump(quick_sort($a));

快速排序的性能和稳定性

时间复杂度是 O(nlogn).
快速排序因为涉及到数据的交换,有可能破坏原来相等元素的位置排序,所以是不稳定的排序算法.
尽管如此,现在各种语言中自带的排序库很多使用的都是快速排序.

希尔排序

希尔排序是基于插入排序的,区别在于插入排序是相邻的一个个比较(类似于希尔中h=1的情形),而希尔排序是距离h的比较和替换。

希尔排序中一个常数因子n,原数组被分成各个小组,每个小组由h个元素组成,很可能会有多余的元素。当然每次循环的时候,h也是递减的(h=h/n)。第一次循环就是从下标为h开始。希尔排序的一个思想就是,分成小组去排序。

function shell_sort(array $arr){
// 将$arr按升序排列
$len = count($arr);
$f = 3;// 定义因子
$h = 1;// 最小为1
while ($h < $len/$f){
$h = $f*$h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
}
while ($h >= 1){ // 将数组变为h有序
for ($i = $h; $i < $len; $i++){ // 将a[i]插入到a[i-h], a[i-2*h], a[i-3*h]... 之中 (算法的关键
for ($j = $i; $j >= $h; $j -= $h){
if ($arr[$j] < $arr[$j-$h]){
$temp = $arr[$j];
$arr[$j] = $arr[$j-$h];
$arr[$j-$h] = $temp;
}
//print_r($arr);echo '<br/>'; // 打开这行注释,可以看到每一步被替换的情形
}
}
$h = intval($h/$f);
}
return $arr;
}


$arr = array(14, 9, 1, 4, 6, -3, 2, 99, 13, 20, 17, 15, 3);

$shell = shell_sort($arr);

堆排序

堆排序分为两个步骤:建堆和排序
创建一个大顶堆或小顶堆。然后移出最上面的元素。然后依次重复这个过程。

什么是堆

堆是一种特殊的二叉树,它满足以下两点:
堆是一个完全二叉树
堆中每个节点都必须大于等于(或小于等于) 其子树的每个节点

每个节点的值都大于等于子树中每个节点值的堆叫最大堆,反之为最小堆。
function sortHeap(&$arr)
{
//先建堆
buildHeap($arr);
//把第一个节点和最后一个节点交换,直到节点数为1
$count = count($arr);
while ($count > 1) {
swap($arr, $count - 1, 0); //交换第一个和最后一个元素
$count--; //去掉最后一个元素后剩余元素再进行调整
adjustHeap($arr, $count, 0);
}
}

function buildHeap(&$arr)
{
$node = floor(count($arr) / 2) - 1; //非叶子节点的最大节点,下标从0开始
for ($i = $node; $i >= 0; $i--) { //从最大非叶子节点循环调整每个节点
adjustHeap($arr, count($arr), $i);
}
}

//调整堆,接受maxLen为当前堆需要调整的元素最大值,node为当前要调整的节点
function adjustHeap(&$arr, $maxLen, $node)
{
$lchild = 2 * $node + 1; //左子树
$rchild = 2 * $node + 2; //右子树

$max = $node; //设置当前节点为最大值的节点,方便后边最大值节点变化时与当前节点比较,确认是否需要交换

while ($lchild < $maxLen || $rchild < $maxLen) { //左子树和右子树任一个符合条件就进入循环

if ($lchild < $maxLen && $arr[$lchild] > $arr[$max]) { //左子树大于当前节点值得话设置设置$max
$max = $lchild;
}

if ($rchild < $maxLen && $arr[$rchild] > $arr[$max]) {
$max = $rchild;
}

if ($max != $node) {
swap($arr, $max, $node);
$node = $max; //把当前节点切换为最大值的那个节点,迭代使其符合堆特性
$lchild = 2 * $node + 1;
$rchild = 2 * $node + 2;
} else {
break; //没有发生交换就退出
}
}
}

function swap(&$arr, $m, $n)
{
$arr[$m] = $arr[$m] ^ $arr[$n];
$arr[$n] = $arr[$n] ^ $arr[$m];
$arr[$m] = $arr[$m] ^ $arr[$n];
}
$arr = [49, 38, 65, 97, 76, 13, 27, 50];
sortHeap($arr);
print_r($arr);

计数排序

计数排序不是基于比较的排序算法,其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。  
找出待排序的数组中最大和最小的元素; 统计数组中每个值为i的元素出现的次数,存入数组C的第i项; 对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加); 反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1。  
$arr = [5,69,4,32,14,8,74,95,23,56,41,5,31,63];
$length = count($arr);
$maxValue = $arr[0];

// 找出数组中的最大值
for ($i=1; $i<$length; $i++) {
if ($arr[$i]>$maxValue) {
$maxValue = $arr[$i];
}
}

$frequency = new SplFixedArray($maxValue + 1);

for ($i=0; $i<$length; $i++) {
if(empty($frequency[$arr[$i]]))
$frequency[$arr[$i]] = 0;
$frequency[$arr[$i]] += 1;
}


// 清空$arr
$arr = [];

for ($i=0; $i<count($frequency); $i++) {
if (!empty($frequency[$i])) {
for ($j=0; $j<$frequency[$i]; $j++) {
$arr[] = $i;
}
}
}

print_r($arr);

桶排序

桶排序或桶排序是一种排序算法,它通过将数组元素分配到多个桶中来工作。
然后,使用不同的排序算法或递归应用桶排序算法,将每个桶单独排序。

function bucketSort($nonSortArray){
//选出桶中最大值和最小值
$min = min($nonSortArray);
$max = max($nonSortArray);

//生成桶,默认每个桶中数据只有0个
$bucket = array_fill($min, $max-$min+1, 0);

//数据入桶
foreach ($nonSortArray as $value){
$bucket[$value]++;//对应桶的个数计增
}

//数据出桶
$sortArray = array();
foreach ($bucket as $k=>$v){
for($i=1;$i<=$v;$i++){
//每个桶中的数据个数
$sortArray[]=$k;
}
}
return $sortArray;
}


$array = array(1000,1,2,3,4,1000,5000,9000);
$arr = bucketSort($array);
var_dump($arr);

基数排序

假如现在有以下这么一些数:

2 343 342 1 128 43 4249 814 687 654 3

使用基数排序将他们从小到大排序。

第一步、首先根据个位数的数值,在走访数值(从前到后走访,后面步骤相同)时将它们分配至编号0到9的桶子中:

0 :
1 : 1
2 : 2 342
3 : 343 43 3
4 : 814 654
5 :
6 :
7 : 687
8 : 128
9 : 4249

第二步、接下来将这些桶子中的数值重新串接起来,成为以下的数列:

1 2 342 343 43 3 814 654 687 128 4249

第三步、根据十位数的数值,在走访数值(从前到后走访,后面步骤相同)时将它们分配至编号0到9的桶子中:

0 : 1 2 3
1 : 814
2 : 128
3 :
4 : 342 343 43 4249
5 : 654
6 :
7 :
8 : 687
9 :

第四步、接下来将这些桶子中的数值重新串接起来,成为以下的数列:

1 2 3 814 128 342 343 43 4249 654 687

第五步、根据百位数的数值,在走访数值(从前到后走访,后面步骤相同)时将它们分配至编号0到9的桶子中:

0 : 1 2 3 43
1 : 128
2 : 4249
3 : 342 343
4 :
5 :
6 : 654 687
7 :
8 : 814
9 :

第六步、接下来将这些桶子中的数值重新串接起来,成为以下的数列:

1 2 3 43 128 4249 342 343 654 687 814
然后一直重复上面的做法
//交换函数
function swap(array &$arr,$a,$b){
$temp = $arr[$a];
$arr[$a] = $arr[$b];
$arr[$b] = $temp;
}
//获取数组中的最大数
//就像上面的例子一样,我们最终是否停止算法不过就是看数组中的最大值:4249,它的位数就是循环的次数
function getMax(array $arr){
$max = 0;
$length = count($arr);
for($i = 0;$i < $length;$i ++){
if($max < $arr[$i]){
$max = $arr[$i];
}
}
return $max;
}
//获取最大数的位数,最大值的位数就是我们分配桶的次数
function getLoopTimes($maxNum){
$count = 1;
$temp = floor($maxNum / 10);
while($temp != 0){
$count ++;
$temp = floor($temp / 10);
}
return $count;
}
/**
* @param array $arr 待排序数组
* @param $loop 第几次循环标识
* 该函数只是完成某一位(个位或十位)上的桶排序
*/
function R_Sort(array &$arr,$loop){

//第一维是 0-9 十个数
//第二维这样定义是因为有可能待排序的数组中的所有数的某一位上的只是一样的,这样就全挤在一个桶里面了
$tempArr = array();
$count = count($arr);
//初始化$tempArr数组
for($i = 0;$i < 10;$i ++){
$tempArr[$i] = array();
}
//求桶的index的除数
//如798个位桶index=(798/1)%10=8
//十位桶index=(798/10)%10=9
//百位桶index=(798/100)%10=7
//$tempNum为上式中的1、10、100
$tempNum = (int)pow(10, $loop - 1);
for($i = 0;$i < $count;$i ++){
//求出某位上的数字
$row_index = ($arr[$i] / $tempNum) % 10;
for($j = 0;$j < $count;$j ++){
if(@$tempArr[$row_index][$j] == NULL){
$tempArr[$row_index][$j] = $arr[$i]; //入桶
break;
}
}
}
//还原回原数组中
$k = 0;
for($i = 0;$i < 10;$i ++){
for($j = 0;$j < $count;$j ++){
if(@$tempArr[$i][$j] != NULL){
$arr[$k ++] = $tempArr[$i][$j]; //出桶
$tempArr[$i][$j] = NULL; //避免下次循环的时候污染数据
}
}
}
}
//最终调用的主函数
function RadixSort(array &$arr){
$max = getMax($arr);
$loop = getLoopTimes($max);
//对每一位进行桶分配(1 表示个位,$loop 表示最高位)
for($i = 1;$i <= $loop;$i ++){
R_Sort($arr,$i);
}
}

$arr = array(2, 343, 342, 1, 128, 43, 4249, 814, 687, 654, 3);
RadixSort($arr);
var_dump($arr);

最后附上一张图片

undefined