“This is the sixth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”
Algorithm thought
Merge sort is a stable sort, is the application of the idea of divide and conquer, divide is to first divide the problem into small problems, conquer is to merge the answers of the various problems in stages
Images from www.cnblogs.com/chengxiao/p…
The process of grading
I’m going to deal with the left and right
Conclusion thought
- I’m going to do the left-hand side, and I’m going to get the left-hand side
- I’ll do it on the right, and I’ll get the information on the right
- And then finally, we’re dealing with information across both sides
Code demo
var mergeSort = function (sum, l, r) {
if (l >= r) return
var mid = Math.floor((l + r) / 2) / / midpoint
mergeSort(sum, l, mid) // Recurse to the left
mergeSort(sum, mid + 1, r) // Recurse to the right
// Become an ordered array
var temp = new Array(r - l + 1) // With storage space
var k = l,
p1 = l,
p2 = mid + 1
// Add smaller values to temp
while (p1 <= mid || p2 <= r) {
if (p2 > r || (p1 <= mid && sum[p1] <= sum[p2])) {
temp[k++] = sum[p1++]
} else {
temp[k++] = sum[p2++]
}
}
for (var i = l; i <= r; i++) sum[i] = temp[i] // Copy the storage space back to the original array
return
}
var arr = [8.1.5.6.3.2.7.4.9]
mergeSort(arr, 0, arr.length - 1)
console.log(arr) // [1, 2, 3, 4, 5, 6, 7, 8, 9]
Copy the code
Merge sort can solve the problem
148. Sort linked lists
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
* @return {ListNode}* /
var sortList = function (head) {
var count = 0 // List length
var p = head
while (p) {
p = p.next
count++
}
return mergeSort(head, count)
};
// merge sort
var mergeSort = function (head, n) {
if (n <= 1) return head
var left_cnt = n >> 1.// The left and right list lengths
right_cnt = n - left_cnt
var l = head,/ / the left list
r = l,/ / right list
p = l,
ret = new ListNode()// Virtual header pointing to the list to be returned
for (var i = 1; i < left_cnt; i++) {
p = p.next
}
r = p.next
p.next = null// Break the linked list
// Sort the list recursively
l = mergeSort(l, left_cnt)
r = mergeSort(r, right_cnt)
p = ret
while(l || r) {
if(r == null || (l && l.val <= r.val)){
// Point the virtual header to the smaller list
p.next = l;
p = l;
l = l.next;
}else{
p.next = r;
p = r;
r = r.next
}
}
return ret.next
}
Copy the code
To be continued