Shulou(Shulou.com)06/01 Report--

This article mainly introduces how to achieve web merger and sorting, has a certain reference value, interested friends can refer to, I hope you can learn a lot after reading this article, the following let the editor take you to understand it.

Merging sorting (MERGE-SORT) is a sorting method based on the idea of merging. The algorithm adopts the classical divide-and-conquer strategy (divide divides the problem into some small problems and then recursively solves them, while the stage of * * conquer) "patches" the answers obtained in different stages, that is, divide and conquer.

As a typical algorithm application of divide-and-conquer idea, merge sorting is realized by two methods:

Top-down recursion (all recursive methods can be rewritten by iteration, so there is a second method); bottom-up iteration

In "JavaScript description of data structures and algorithms", the author gives a bottom-up iterative method. However, for the recursive method, the author thinks that:

However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle. However, this approach is not feasible in JavaScript because the recursion depth of the algorithm is too deep for it.

To tell you the truth, I don't quite understand this sentence. Does it mean that the memory of the JavaScript compiler is too small and the recursion is too deep to cause memory overflow? I also hope that there are great gods who can give us some advice.

Like selective sorting, the performance of merge sorting is not affected by the input data, but it performs much better than selective sorting, because it is always O (nlogn) time complexity. The cost is that extra memory space is required.

The algorithm step applies for a space whose size is the sum of two sorted sequences, which is used to store the merged sequence, and sets two pointers whose initial position is the starting position of the two sorted sequences. compare the elements pointed to by the two pointers, select a relatively small element to put into the merge space, and move the pointer to the next position; repeat step 3 until a pointer reaches the end of the sequence Copy all the remaining elements of another sequence directly to the end of the merge sequence. Moving picture demonstration

Code implementation

JavaScript

Example

Function mergeSort (arr) {/ / uses a top-down recursive method var len = arr.length; if (len return arr;} var middle = Math.floor (len / 2), left = arr.slice (0, middle), right = arr.slice (middle); return merge (mergeSort (left), mergeSort (right));} function merge (left, right) {var result = [] While (left.length & & right.length) {if (left [0] else {result.push (right.shift ());}} while (left.length) result.push (left.shift ()); while (right.length) result.push (right.shift ()); return result;} Python

Example

Def mergeSort (arr): import math if (len (arr) return arr middle = math.floor (len (arr) / 2) left,right = arr [0:middle], arr [middle:] return merge (mergeSort (left), mergeSort (right)) def merge (left,right): result = [] while left and right: if left [0] else: result.append (right.pop (0)) While left: result.append (left.pop (0)) while right: result.append (right.pop (0)); return resultGo

Example

Func mergeSort (arr [] int) [] int {length: = len (arr) if length return arr} middle: = length / 2 left: = arr [0:middle] right: = arr [middle:] return merge (mergeSort (left), mergeSort (right))} func merge (left [] int) Right [] int) [] int {var result [] int for len (left)! = 0 & & len (right)! = 0 {if left [0] else {result = append (result) Right [0]) right = right [1:]} for len (left)! = 0 {result = append (result, left [0]) left = left [1:]} for len (right)! = 0 {result = append (result) Right [0]) right = right [1:]} return result} Java

Example

Public class MergeSort implements IArraySort {@ Override public int [] sort (int [] sourceArray) throws Exception {/ / A copy of arr without changing the parameter content int [] arr = Arrays.copyOf (sourceArray, sourceArray.length); if (arr.length return arr;} int middle = (int) Math.floor (arr.length / 2); int [] left = Arrays.copyOfRange (arr, 0, middle)) Int [] right = Arrays.copyOfRange (arr, middle, arr.length); return merge (sort (left), sort (right));} protected int [] merge (int [] left, int [] right) {int [] result = new int [left.length + right.length]; int I = 0 While (left.length > 0 & & right.length > 0) {if (left [0] else {result [ionization +] = right [0]; right = Arrays.copyOfRange (right, 1, right.length);}} while (left.length > 0) {result [ionization +] = left [0]; left = Arrays.copyOfRange (left, 1, left.length) } while (right.length > 0) {result [iTunes +] = right [0]; right = Arrays.copyOfRange (right, 1, right.length);} return result;}} PHP

Example

Function mergeSort ($arr) {$len = count ($arr); if ($len return $arr;} $middle = floor ($len / 2); $left = array_slice ($arr, 0, $middle); $right = array_slice ($arr, $middle); return merge (mergeSort ($left), mergeSort ($right);} function merge ($left, $right) {$result = [] While (count ($left) > 0 & & count ($right) > 0) {if ($left [0] $right [0]) {$result [] = array_shift ($left);} else {$result [] = array_shift ($right);}} while (count ($left)) $result [] = array_shift ($left); while (count ($right)) $result [] = array_shift ($right); return $result;}

C

Example

Int min (int x, int y) {return x for (seg = 1; seg for (start = 0; start while (start1 while (start2 if (a! = arr) {int i; for (I = 0; I)

Recursive version:

Example

Void merge_sort_recursive (int arr [], int reg [], int start, int end) {if (start > = end) return; int len = end-start, mid = (len > > 1) + start; int start1 = start, end1 = mid; int start2 = mid + 1, end2 = end; merge_sort_recursive (arr, reg, start1, end1); merge_sort_recursive (arr, reg, start2, end2); int k = start; while (start1 while (start2 for (k = start; kC++)

Iterative version:

Example

Template / / integers or floating point numbers can be used. To use an object (class), you must set "less than" (for (int seg = 1; seg for (int start = 0; start while (start1 while (start2 if (a! = arr) {for (int I = 0; I)

Recursive version:

Example

Void Merge (vector & Array, int front, int mid, int end) {/ / preconditions: / / Array [front...mid] is sorted / / Array [mid+1. End] is sorted / / Copy Array [front... Mid] to LeftSubArray / / Copy Array [mid+1... End] to RightSubArray vector LeftSubArray (Array.begin () + front, Array.begin () + mid + 1); vector RightSubArray (Array.begin () + mid + 1, Array.begin () + end + 1); int idxLeft = 0, idxRight = 0; LeftSubArray.insert (LeftSubArray.end (), numeric_limits::max ()); RightSubArray.insert (RightSubArray.end (), numeric_limits::max ()) / Pick min of LeftSubArray [idxLeft] and RightSubArray [idxRight], and put into Array [I] for (int I = front; i if (LeftSubArray [idxLeft] else {Array [I] = RightSubArray [idxRight]; idxRight++;}} void MergeSort (vector & Array, int front, int end) {if (front > = end) return; int mid = (front + end) / 2; MergeSort (Array, front, mid) MergeSort (Array, mid + 1, end); Merge (Array, front, mid, end);} C #

Example

Public static List sort (List lst) {if (lst.Count return lst; int mid = lst.Count / 2; List left = new List (); / / define left List List right = new List (); / / define right List / / divide lst into left and right List for (int I = 0; I for (int j = mid; j return merge (left, right)) } / two sorted List/ left List/// right List///static List merge (List left, List right) {List temp = new List (); while (left.Count > 0 & & right.Count > 0) {if (left [0] else {temp.Add (right [0]); right.RemoveAt (0) } if (left.Count > 0) {for (int I = 0; I if (right.Count > 0) {for (int I = 0; i return temp;} Ruby)

Example

Def merge list return list if list.size # Merge lambda {| left, right | final = [] until left.empty? Or right.empty? Final if left.first else right.shift end end final + left + right} .call merge (list [0.roomt]), merge (list [roomt..-1]) end

Thank you for reading this article carefully. I hope the article "how to merge and sort web" shared by the editor will be helpful to everyone. At the same time, I also hope you will support us and pay attention to the industry information channel. More related knowledge is waiting for you to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.