PHP基础加强系列三之排序

胡三金 2017-06-12 13:21:01 225 0 comments

序言:这篇文章主要讲解三个排序,用PHP代码实现;排序速度:冒泡<选择<插入<快速;

快速排序运用递归思想;效率秒杀前三个排序;有兴趣的可以去了解一下,这里我就介绍前三种简单的;

(1)冒泡排序

冒泡排序是的核心:先确定要排序的数组的元素个数,然后循环个数-1次大循环,每一次大循环确定一个最大的数放在最后,然后在大循环中循环个数-大循环次循环确定相邻两个数的大小;

小例子:

image.png

arr = [10,7,1,11];

image.png

输出结果如上;

通俗的理解如上例子:在数组arr中有4个数;

所以一共会进行3次大循环;

//7,10,1,11 7,1,10,11 7,1,10,11

//1,7,10,11 1,7,10,11

//1,7,10,11

然后第一次大循环进行3次小循环(即数组个数-大循环次数=4-1)

//7,10,1,11

//7,1,10,11

//7,1,10,11

第二次大循环进行2次

//1,7,10,11 这里是7和1比较

//1,7,10,11 这里是7和10比较

第三次大循环进行一次比较

//1,7,10,11 1和7比较

这样就完成了冒泡排序

但是有一个小问题,如果传入的数组已经有序了,它还会照样执行排序,这样会有另外的开销;

例如传入一个有序数组:

image.png

输出结果:

image.png

可以看出当一个10000个数据的数组进行排序时,明明已经是有序了,它还会傻乎乎的执行一遍,所以开销很大;

所以来小小的优化一下这个代码;

image.png

优化后的冒泡排序在效率上要高于没有优化的冒泡的,因为如果传入的数组有的已经有序了,则不需要进行比较了;你可以用我说的测试运行时间的方法来测试当传入一个有序数组时,两个的区别;前提是数据量很大的时候,当然小数据量差别不明显;

这个时候再次传入同样一个有序数组;

image.png

从结果可以看到差别,因为对数组进行了判断,所以不会进入排序循环;执行效率高;

在判断里的理解是:当标志flag = 0时,则不会进入循环,如果不等于0,说明数组无序,进行了排序,然后将它置为0,接着排序,这是为了解决一个升序数组只有几个元素顺序不同的情况做的处理方法;

(2).选择排序

选择排序的核心是先假定一个最小的值,然后依次和后面的数比较,如果后面有比它小的值就替换,没有就不替换,一共会进行数组个数-1次大循环,第一次大循环就确定了整个数组的最小数,然后将它放在第一位,然后再将第二位和后面的数进行比较,依次类推,就对整个数组进行了升序排序;

image.png

上面的代码的min就是最小数;min_index是记录最小数的下标;

同样用上面的冒泡排序的数组arr做解释

第一次大循环

//1,7,10,11

第二次大循环

//1,7,10,11 这里是将7和后面的数做比较

第三次大循环

//1,7,10,11 这里是将10和后面的数做比较

它不同于冒泡的地方是:冒泡是将相邻两个数做比较然后交换,而选择排序则是将一个值与后面的数依次比较,直到找到最小的值,然后再交换;

输出:

image.png

这两个排序都是升序,如果要降序,只需要将冒泡中的image.png>改为<;

将选择排序的image.png>改为<就行;


(3)插入排序

核心是从第二个数开始和第一个数做比较,假定第一个数是一个单独的有序数组,第二个数到最后一个数是无序数组,然后依次从无序数组中取第一个数同有序数组的数做比较,然后插入到有序数组的合适位置;

小例子:

image.png

arr = [10,7,1];

用这个数组简单的解释一下:

首先从第二个数开始和第一个数做比较

此时insert=7,index=0;满足while循环条件,进入循环

因为满足条件,所以将第一个数向后移动一位,下标向前一位

所以现在的数组是10,10,1

然后再将7插入到第一位

因为index=-1;不满足条件,退出while循环

此时再将7插入到下标所指的位置,即第一位

此时数组变为7,10,1


接着i++;所以此时insert=1;index=1;满足while循环条件,进入循环

因为满足条件,所以将第一个数向后移动一位,下标向前一位

所以现在的数组是7,10,10

此时index=0;满足while循环条件,进入循环

因为满足条件,所以将第一个数向后移动一位,下标向前一位

所以现在的数组是7,7,10

此时$index=-1;不满足条件,退出while循环

此时再将1插入到下标所指的位置,即第一位

此时数组变成1,7,10

至此完成了对整个数组的升序排序

输出:

image.png


转载请注明出处,谢谢!




标签
评论一下

评论列表

暂时没有评论,快来评论吧..