PHP sorting algorithm Merging Sort (Merging Sort)

This article mainly introduces the Merging Sort of the PHP sorting algorithm. It analyzes the principles, definitions, usage methods and related operation precautions of PHP Merging Sort in detail with examples. Friends in need can refer to it

The example in this article describes the Merging Sort of the PHP sorting algorithm. Share it with everyone for your reference, the details are as follows:

Basic idea:

Merge sort: It is achieved by using the idea of ​​​​merging (merging) Sorting method. 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 Among the total functions, we only called one MSort() function. Because we want to use recursive calls, we encapsulate MSort().

Let’s take a look at 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]
  }
}

MSort()# above ## The function implements dividing the array in half and then in half (until the subsequence length is 1), and then merges 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 It's over. Let’s try calling:

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

Running result:

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:

Since the merge algorithm will group and compare regardless of whether the original sequence is ordered or not, its best, worst, and average time complexity are

O(nlogn).

The merge algorithm is a stable sorting algorithm.

This article is referenced from "Dahua Data Structure". It is only recorded here for future reference. Please don't criticize!

Related recommendations:

PHP sorting algorithm bubble sort (Bubble Sort)

PHP sorting algorithm simple selection sort (Simple Selection Sort)

PHP sorting algorithm Straight Insertion Sort(Straight Insertion Sort)

The above is the detailed content of PHP sorting algorithm Merging Sort (Merging Sort). For more information, please follow other related articles on the PHP Chinese website!