PHP implements several common sorting algorithms

Exchange sorting: The basic idea of ​​exchange sorting is to compare the sizes of the key values ​​​​of the two records. If the sizes of the key values ​​​​of the two records appear in reverse order, exchange the two records, so that the record with the smaller key value is moved to Move to the front of the sequence, and records with larger key values ​​move to the back of the sequence.

# 1. Bubble sort

Introduction:

Bubble Sort (Bubble Sort, Taiwanese translation: Bubble Sorting or bubble sort) is a simple sorting algorithm. It repeatedly walks through the sequence to be sorted, comparing two elements at a time and swapping them if they are in the wrong order. The work of visiting the array is repeated until no more exchanges are needed, which means that the array has been sorted. The name of this algorithm comes from the fact that smaller elements will slowly "float" to the top of the array through swapping.

Steps:

1. Compare adjacent elements. If the first one is bigger than the second one, swap them both.

2. Do the same for each pair of adjacent elements, starting with the first pair and ending with the last pair. At this point, the last element should be the largest number.

3. Repeat the above steps for all elements except the last one.

4. Continue repeating the above steps for fewer and fewer elements each time until there are no pairs of numbers to compare.

##Bubble sort is the simplest to understand, but the time complexity is ( O(n^2)) is also one of the largest. The implementation code is as follows:

<br/>

1. $arr=array(1,43,54,62,21,66 ,32,78,36,76,39);

2. ##function getpao($arr)

3. ##{

4. ##$len

   =count($arr);

5. //Set an empty array to receive bubbles that pop up

6. //This layer loop controls the number of rounds that need to bubble

7. for

   ($i=1;$i<$ len;$i++)

   ## {
//This layer of loop is used to control the number of times a number needs to be compared in each round

9.     for($k=0;$k<$len-$i;$k++)  

10.     {  

11.        if($arr[$k]>$arr[$k+1])  

12.         {  

13.             $tmp=$arr[$k+1];  

14.             $arr[$k+1]=$arr[$k];  

15.              $arr[$k]=$tmp;

16. ##                                                 

# }
##return

18. $ arr

;

19. }

2. Quick sort

Introduction:

Quick sort was developed by Tony HallA sorting algorithm developed. Under average circumstances, sorting n items requires

Ο

(n log

n

) comparisons. In the worst case, Ο(n2) comparisons are required, but this situation is uncommon. In fact, quicksort is often significantly faster than other Ο(n log n) algorithms because its inner loop can be used in most The architecture is implemented very efficiently, and in most real-world data, it is possible to determine the design choices and reduce the time required by the quadratic term. step:

1. Pick out an element from the sequence, called the "pivot",

2. Reorder the sequence , all elements smaller than the base value are placed in front of the base, and all elements larger than the base value are placed behind the base (the same number can go to either side). After this partition exits, the base is in the middle of the sequence. This is called a partition operation.

3. Recursively sort the subarray of elements smaller than the base value and the subarray of elements greater than the base value.

Quick sort is also an efficient sorting algorithm, and its time complexity is also O( nlogn). The code is as follows:

1. ##function

   quick_sort($arr) {

2. //First determine whether you need to continue

3. $length

   = count($arr);

##if

4. ($length <= 1 ) {

5.                                                                                             ## }   //If there is no return, it means that the number of elements in the array is more than 1 and needs to be sorted

7. //Select a ruler

8. //Select the first element

9. # #$base_num

   = $arr[0];

10. ##​ //Traverse all elements except the ruler and put them into two arrays according to their size relationship

    # #//Initialize two arrays

11. ##$left_array

=

12. array();//Less than the ruler

13. $right_array = array();//Greater than the ruler

15. for($i=1; $i<$length; $i++) {

16.                                                                                              ​ #[$i]) { ##             //Put it into the left array

##            
17. $left_array

    [] = $arr[

    $i
18. ];

    #                                                                                              { ##                                                                                   

19.             $right_array[] = $arr[$i];

20. //Then perform the same sorting process on the left and right arrays respectively

//Recursively call this function and record the result
$left_array

23. = quick_sort($left_array);

24. ##$right_array = quick_sort($right_array);

25. //Merge the left ruler and the right

26. ##​ return array_merge($left_array , array($base_num), $right_array);

27. }

##Select sort

Selection sorting includes two types, namely direct selection sorting and heap sorting. The basic idea of ​​selection sorting is that each time n-i+ Select the record with the smallest key value among 1 (i=1,2,3,...,n-1) records as the i-th record in the ordered sequence

三、Selection sort

Introduction:

Selection sort is a simple and intuitive

sorting algorithm. Here's how it works. First, find the smallest element in the unsorted sequence and store it at the beginning of the sorted sequence. Then, continue to find the smallest element from the remaining unsorted elements, and then put it at the end of the sorted sequence. And so on until all elements are sorted.

<br/> Selection sorting is relatively simple to understand, and the time complexity is O(n^2). The implementation code is as follows:

<br/>

<br/>

[php]

view plain copy

<br/>

##

1. function select_sort($arr) {

2. //Implementation idea: The double loop is completed, the outer layer controls the number of rounds, and the current minimum value. The number of comparisons controlled by the inner layer

3. ##//$i The position of the current minimum value, which needs to participate in the comparison Element

4. ##for($i =0, $len=count($arr) ; $i<$len-1; $i++ ) {

#                                                                                             

5.           $p =

   $i
6. ;

                 //What elements does $j currently need to be compared with, the ones after $i.

7.             for($j=$i+1; $j<$len; $j++) {

8. ##                                                                                             ##             if

(

9. $arr[$ p] > $arr[$j]) { //Compare, find the smaller one, record the position of the minimum value; and in the next comparison,

10. // The known minimum value should be used for comparison.

11. ##                                  $p

    =
12. $j

    ;

13.           //The current minimum value position has been determined and saved to $p.

14. //If it is found that the position of the minimum value is different from the current assumed position $i, then the positions are mutually exclusive Just change it

15. ##if($p != $i) {

16. ##                                  

    ## = $arr[$p];

                  
$arr

17. [$p] = $arr [$i]; ##         

    $arr
18. [

    $i] = $tmp; } }

19. }

20. //Return the final result

21. ## return $arr;

22. }

4. Heap sort <br/>

Introduction:

Stacking sort (Heapsort) refers to a sorting algorithm designed using the data structure of heap. The heap is a structure that approximates a complete binary tree, and simultaneously satisfies the heap properties: that is, the A key or index is always smaller (or larger) than its parent node.

Steps:

Heap sorting refers to a sorting algorithm designed using the data structure of a stacked tree (heap) , using the characteristics of arrays to quickly locate the element at the specified index. The heap is divided into a large root heap and a small root heap, which is a complete binary tree. The requirement of a large root heap is that the value of each node is not greater than the value of its parent node, that is, A[PARENT[i]] >= A[i]. In non-descending sorting of an array, a large root heap needs to be used, because according to the requirements of a large root heap, the largest value must be at the top of the heap.

Sort effect:

<br/>

堆排序是一种高效的排序算法，它的时间复杂度是O(nlogn)。原理是：先把数组转为一个最大堆，然后把第一个元素跟第i元素交换，然后把剩下的i-1个元素转为最大堆，然后再把第一个元素与第i-1个元素交换，以此类推。实现代码如下：

function heapSort($arr) {
    $len = count($arr);    // 先建立最大堆
    for ($i = floor(($len - 1) / 2); $i >= 0; $i--) {        $s = $i;        $childIndex = $s * 2 + 1;        while ($childIndex < $len) {            // 在父、左子、右子中 ，找到最大的
            if ($childIndex + 1 < $len && $arr[$childIndex] < $arr[$childIndex + 1]) $childIndex++;            if ($arr[$s] < $arr[$childIndex]) {                $t = $arr[$s];                $arr[$s] = $arr[$childIndex];                $arr[$childIndex] = $t;                $s = $childIndex;                $childIndex = $childIndex * 2 + 1;
            } else {                break;
            }
        }
    }    // 从最后一个元素开始调整
    for ($i = $len - 1; $i > 0; $i--) {        $t = $arr[$i];        $arr[$i] = $arr[0];        $arr[0] = $t;        // 调整第一个元素
        $s = 0;        $childIndex = 1;        while ($childIndex < $i) {            // 在父、左子、右子中 ，找到最大的
            if ($childIndex + 1 < $i && $arr[$childIndex] < $arr[$childIndex + 1]) $childIndex++;            if ($arr[$s] < $arr[$childIndex]) {                $t = $arr[$s];                $arr[$s] = $arr[$childIndex];                $arr[$childIndex] = $t;                $s = $childIndex;                $childIndex = $childIndex * 2 + 1;
            } else {                break;
            }
        }
    }    return $arr;
}$arr = [3,1,13,5,7,11,2,4,14,9,15,6,12,10,8];
print_r(bubbleSort($arr));

• <br/>

<br/>

插入排序

五、插入排序

介绍：

插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

步骤：

1. 从第一个元素开始，该元素可以认为已经被排序

2. 取出下一个元素，在已经排序的元素序列中从后向前扫描

3. 如果该元素（已排序）大于新元素，将该元素移到下一位置

4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

5. 将新元素插入到该位置中

6. 重复步骤2

<br/>感觉插入排序跟冒泡排序有点相似，时间复杂度也是O(n^2)，实现代码如下：

<br/>

[php] view plain copy

<br/>

1. ##function insert_sort($arr) {

2. //Distinguish which part has been sorted

3. ##/ /Which part is not sorted

4. ##//Find one of the elements that needs to be sorted

##//This element starts from the second element and ends with the last element that needs to be sorted
//You can mark it by using a loop
//i loop controls the elements that need to be inserted each time. Once the elements that need to be inserted are controlled,
//Indirectly the array has been divided into 2 parts, the subscript is smaller than the current one (left one), it is the sorted sequence

9. for($i=1, $len=count($arr); $i< ;$len; $i++) {

10. ##         //Get the current element value that needs to be compared.

11. $tmp = $arr [$i];

12. #         

    //Inner loop control Compare and insert

13. ##for

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

14. //$arr[$i];//Elements that need to be inserted; $arr[$j];//Elements that need to be compared

15. ##                  if($tmp < $arr[$j]) {

16. //It is found that the inserted element should be smaller, swap the position

    ##                                                                                                                        Swap with the previous element

17. ##                                                      #$j

    +1] =
18. $arr

    [$j]; ##                      //Set the previous number to the number that currently needs to be exchanged

19.           

    $arr[$j] =

$tmp

20. ;

21. } else {

22. //如果碰到不需要移动的元素

23. //由于是已经排序好是数组，则前面的就不需要再次比较了。

24. break;

25. }

26. }

27. }

28. //将这个元素 插入到已经排序好的序列内。

29. //返回

30. return $arr;

31. }

<br/>

六、希尔排序

介绍：

希尔排序，也称递减增量排序算法，是插入排序的一种高速而稳定的改进版本。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

1、插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率

2、但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位>

排序效果：

<br/>希尔排序其实可以理解是插入排序的一个优化版，它的效率跟增量有关，增量要取多少，根据不同的数组是不同的，所以希尔排序是一个不稳定的排序算法，它的时间复杂度为O(nlogn)到O(n^2)之间，实现代码如下：

function shellSort($arr) {
    $len = count($arr);    $stepSize = floor($len / 2);    while ($stepSize >= 1) {        for ($i = $stepSize; $i < $len; $i++) {            if ($arr[$i] < $arr[$i - $stepSize]) {                $t = $arr[$i];                $j = $i - $stepSize;                while ($j >= 0 && $t < $arr[$j]) {                    $arr[$j + $stepSize] = $arr[$j];                    $j -= $stepSize;
                }                $arr[$j + $stepSize] = $t;
            }
        }        // 缩小步长，再进行插入排序
        $stepSize = floor($stepSize / 2);
    }    return $arr;
}$arr = [3,1,13,5,7,11,2,4,14,9,15,6,12,10,8];
print_r(bubbleSort($arr));

<br/>

七、归并排序

介绍：

归并排序（Merge sort，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（pide and Conquer）的一个非常典型的应用

步骤：

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置

3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

4. 重复步骤3直到某一指针达到序列尾

5. 将另一序列剩下的所有元素直接复制到合并序列尾

排序效果：

<br/>归并排序的时间复杂度也是O(nlogn)。原理是：对于两个排序好的数组，分别遍历这两个数组，获取较小的元素插入新的数组中，那么，这么新的数组也会是排序好的。代码如下：

我们先来看看主函数部分：

//交换函数function swap(array &$arr,$a,$b){
    $temp = $arr[$a];    $arr[$a] = $arr[$b];    $arr[$b] = $temp;
}//归并算法总函数function MergeSort(array &$arr){
    $start = 0;    $end = count($arr) - 1;
    MSort($arr,$start,$end);
}

在总函数中，我们只调用了一个 MSort() 函数，因为我们要使用递归调用，所以将 MSort() 封装起来。

下面我们来看看 MSort() 函数：

function MSort(array &$arr,$start,$end){    //当子序列长度为1时，$start == $end，不用再分组    if($start < $end){        $mid = floor(($start + $end) / 2);	//将 $arr 平分为 $arr[$start - $mid] 和 $arr[$mid+1 - $end]        MSort($arr,$start,$mid);			//将 $arr[$start - $mid] 归并为有序的$arr[$start - $mid]        MSort($arr,$mid + 1,$end);			//将 $arr[$mid+1 - $end] 归并为有序的 $arr[$mid+1 - $end]        Merge($arr,$start,$mid,$end);       //将$arr[$start - $mid]部分和$arr[$mid+1 - $end]部分合并起来成为有序的$arr[$start - $end]
    }
}

上面的 MSort() 函数实现将数组分半再分半（直到子序列长度为1），然后将子序列合并起来。

现在是我们的归并操作函数 Merge() :

//归并操作function Merge(array &$arr,$start,$mid,$end){
    $i = $start;    $j=$mid + 1;    $k = $start;    $temparr = array();    while($i!=$mid+1 && $j!=$end+1)
    {       if($arr[$i] >= $arr[$j]){           $temparr[$k++] = $arr[$j++];
       }       else{           $temparr[$k++] = $arr[$i++];
       }
    }    //将第一个子序列的剩余部分添加到已经排好序的 $temparr 数组中
    while($i != $mid+1){        $temparr[$k++] = $arr[$i++];
    }    //将第二个子序列的剩余部分添加到已经排好序的 $temparr 数组中
    while($j != $end+1){        $temparr[$k++] = $arr[$j++];
    }    for($i=$start; $i<=$end; $i++){        $arr[$i] = $temparr[$i];
    }
}

到了这里，我们的归并算法就完了。我们调用试试：

$arr = array(9,1,5,8,3,7,4,6,2);
MergeSort($arr);
var_dump($arr);

相关推荐：

php冒泡、选择、插入和快速排序算法分享

PHP多维数组排序算法分析

PHP排序算法系列之直接选择排序详解

The above is the detailed content of PHP implements several common sorting algorithms. For more information, please follow other related articles on the PHP Chinese website!