Detailed explanation of the steps to implement the merge sort algorithm in PHP

This time I will bring you a detailed explanation of the steps to implement the merge sort algorithm in PHP. What are the precautions for PHP to implement the merge sort algorithm? The following is a practical case, let's take a look.

Basic idea:

Merge sort: It is a sorting method implemented using the idea of ​​​​merging (merging). Its principle is that assuming that the initial sequence contains n elements, it can be regarded as n ordered subsequences, each subsequence has a length of 1, and then merged in pairs to obtain ⌈ n / 2⌉ (⌈ x ⌉ means not The smallest integer less than 2-way merge sort.

1. The process of merging:

a[i] takes the first part of array a (already sorted), a[j] takes the last part of array a Part (already sorted)

r array stores the sorted a array

Compare the sizes of a[i] and a[j], if a[i] ≤ a[j ], then copy the element a[i] in the first ordered list to r[k], and add 1 to i and k respectively; otherwise, copy the element a[j] in the second ordered list Copy it to r[k], and add 1 to j and k respectively. This cycle continues until one of the ordered lists is fetched, and then copies the remaining elements in the other ordered list to r from the subscript k to the element of subscript t. We usually use recursion to implement the merge sorting algorithm. First, divide the interval to be sorted [s, t] into two at the midpoint, then sort the left sub-range, then sort the right sub-range, and finally perform a merge operation on the left and right intervals. Merge into ordered intervals [s,t].

2. Merge operation:

Merge operation (merge), also called merging algorithm, refers to the method of merging two sequential sequences into one sequential sequence.

If there is a sequence {6, 202, 100, 301, 38, 8, 1}

Initial state: 6, 202, 100, 301, 38, 8, 1

After the first merge: {6,202}, {100,301}, {8,38}, {1}, number of comparisons: 3;

After the second merge: {6,100,202,301}, {1 ,8,38}, number of comparisons: 4;

After the third merge: {1,6,8,38,100,202,301}, number of comparisons: 4;

The total number of comparisons is: 3 4 4=11,;

The reverse number is 14;

3. Algorithm description:

The working principle of the merge operation is as follows:

Step 1: Apply for space so that its size is the sum of the two sorted sequences. This space is used to store the merged sequence

Step 2: Set two pointers, the initial position They are the starting positions of the two sorted sequences respectively

Step 3: Compare the elements pointed to by the two pointers, select the relatively small element and put it into the merge space, and move the pointer to the next position

Repeat step 3 until a pointer exceeds the end of the sequence

Copy all the remaining elements of the other sequence directly to the end of the merged sequence

Algorithm implementation:

Let’s take a look at the main function part first:

//交换函数
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);
}

In the total function, we only called one MSort() Function, because we want to use recursive calling, MSort() is encapsulated.

Let’s take a look at the MSort() function:

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]
  }
}

The above MSort() function implements dividing the array in half and then in half ( until the subsequence length is 1), and then merge the subsequences.

Now is our merge operation function 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];
  }
}

At this point, our merge algorithm is finished. Let’s try calling:

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

Running results:

array(9) {
 [0]=>
 int(1)
 [1]=>
 int(2)
 [2]=>
 int(3)
 [3]=>
 int(4)
 [4]=>
 int(5)
 [5]=>
 int(6)
 [6]=>
 int(7)
 [7]=>
 int(8)
 [8]=>
 int(9)
}

Complexity analysis:

Due to the merging algorithm, regardless of the original Whether the sequence is ordered or not, it will be grouped and compared, so its best, worst, and average time complexity are all O(nlogn).

The merge algorithm is a stable sorting algorithm.

I believe you have mastered the method after reading the case in this article. For more exciting information, please pay attention to other related articles on the php Chinese website!

Recommended reading:

Detailed explanation of PHP singleton mode use cases

php receivemail has the function of sending and receiving emails

The above is the detailed content of Detailed explanation of the steps to implement the merge sort algorithm in PHP. For more information, please follow other related articles on the PHP Chinese website!