冒泡、选择、插入、快速排序算法小解

左手的ㄟ右手 2022-05-30 02:05 162阅读 0赞

假设待排序数组$arr=array(9,5,3,6,7,1);（从小到大排序）

1、冒泡排序

冒泡排序的思想是每一趟找出最大的那个（最大的泡泡），经过count($arr)-1趟，得出最后的顺序

因为要得到最大的那个数，所以需要两层循环，外层表示进行的趟数，内层循环来进行比较、交换

即第一趟5,3,6,7,1,**9**

第二趟5,3,6,1,**7**,9

第三趟5,3,1,**6**,7,9

第四趟3,1,**5**,6,7,9

第五趟1,**3**,5,6,7,9

故代码为

function bubble\_sort($arr)\{

for($i=0;$i<count($arr)-1;$i++)\{

for($j=0;$j<count($arr)-$i;$j++)\{//因为每走一趟，最大的已经在最后面，所以要减去躺数（$i）

if($arr\[$j\]>$arr\[$j+1\])\{

$temp = $arr\[$j\];

$arr\[$j\] = $arr\[$j+1\];

$arr\[$j+1\] = $temp;

return $arr;

2、选择排序（打擂）

初始序列：\{9  5  3  6  7  1\}

第一趟1  \{5  3  6  7  9\}  9和1交换

第二趟1  3 \{5  6  7  9\}    5和3交换

第三趟1  3  5 \{ 6  7  9\}  5不动

第四趟1  3  5  6 \{ 7  9\}   6不动

第五趟1  3  5  6  7 \{9\}    7不动（完成）

选择排序的思想是先让9和其余数字进行比较，找出最小的，和9互换位置，然后让5和其余数字进行比较，找出最小的，互换位置，以此类推，直到最后两个数字比较完成后，就得到了排序完成的数组

用打擂的方式理解就是10个座位，分别对应十个人，先让第一个人和其余人比武，选出第一名，并交换位置（排名赛），然后第二个人和其余人比武，以此类推。。。

可以得出代码

function select\_sort($arr)\{

for($i=0;$i<count($arr)-1;$i++)\{

$m = $i;//记录当前位置（没有交换之前）

for($j=$i+1;$j<count($arr)-1-$i;$i++)\{//$j=$i+1，实现第i个人和它后面的每个人比较

if($arr\[$i\]>$arr\[$j\])\{

$m = $j;//记录循环比较完后（最大）的位置

if($i != $m)\{

$temp = $arr\[$i\];

$arr\[$i\] = $arr\[$m\];

$arr\[$m\] = $temp;

3、插入排序

初始序列  9  5  3  6  7  1

第一趟   \[9\]  5  3  6  7  1

第二趟   \[5  9\]  3  6  7  1

第三趟   \[3  5  9\]  6  7  1

第四趟   \[3  5  6  9\]  7  1

第五趟   \[3  5  6  7  9\]  1

第六趟   \[1  3  5  6  7  9\]

插入排序的思想是将未排序的数组插入到已经排好序的数组中（将数组中第一个元素作为初始的有序列表），和冒泡排序类似，需要和已排序的数组中的元素进行比较，确定插入元素的位置

代码为

function insert\_sort($arr)\{

for($i=1;$i<count($arr);$i++)\{

$temp = $arr\[$i\];//获取当前需要插入到有序列表的元素

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

if($temp<$arr\[$j\])\{

$arr\[$j\] = $arr\[$j+1\];

$arr\[$j+1\] = $temp;

\}else\{

break;

4、快速排序

快速排序的思想是先取出数组的第一个元素，和其余元素一一进行比较，得出两个数组，一个数组中的元素都小于它，另一个数组元素都大于它；然后分别对这两个数组继续使用这个函数（递归思想），得出排好序的数组

代码为

function  quick\_sort($arr)\{

$key = $arr\[0\];

$left = array();

$right = array();

for($i=1;$i<count($arr);$i++)\{

if($arr\[$i\]<$key)\{

$left\[\] = $arr\[$i\];

\}else\{

$right = $arr\[$i\];

$left = quick\_sort($left);

$right = quick\_sort($right);

return array\_merge($left,array($key),$right);

时间复杂度算法：

1、用常数1取代运行时间中的所有加法常数。  
2、在修改后的运行次数函数中，只保留高阶项。  
3、如果最高阶项存在且不是1，则去除与这个项相乘的常数。

例如：

1 int n = 100000; //执行了1次
     2 for(int i = 0; i < n; i++){  //执行了n+1次
     3   for(int j = 0; j < n; j++) //执行了n*(n+1)次
     4   {
     5       printf("i = %d, j = %d", i, j); //执行了n*n次
     6   }
     7 }
     8 
     9 for(int i = 0; i < n; i++){  //执行了n+1次
    10   printf("i = %d", i); //执行了n次
    11 }
    12 
    13 printf("Done"); //执行了1次

按上面推导"大O阶"的步骤我们先来第一步："用常数1取代运行时间中的所有加法常数"，则上面的算式变为:  
执行总次数 = 2n^2 + 4n + 1;

第二步："在修改后的运行次数函数中，只保留最高阶项"，这里的最高阶项是n的二次方  
所以算式变为：  
执行总次数 = 2n^2;

第三步："如果最高阶项存在且不是1，则去除与这个项相乘的常数"，这里n的二次方不是1所以  
要去除这个项相乘的常数算式变为:  
执行总次数 = n^2;

因此，最后我们得到上面的那段代码的算法时间复杂度表示为: O(n^2);

嵌套一层for循环的时间复杂度为:O(n),二层for循环为O(n^2)，二分的算法时间复杂度为:O(logn)，如果一个for循环套一个二分，那么时间复杂度为O(nlogn);

备注：这里只是通过一个数理化的形式来比较算法的时间执行效率，并不能真正推导出算法在特定机器的执行时间，这取决于具体的电脑和代码。

![70][]

[70]: /images/20220530/4fa2a910a8954b99901185ab8033ba5c.png