Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

This article also participated in the “Digitalstar Project” to win a creative gift package and creative incentive money

preface

In the previous two articles, we have analyzed the ideas of bubble sort and insertion sort in classical sorting algorithms, as well as the optimization scheme of bubble sort. Next we will continue to learn a new sorting algorithm – quicksort (binary sort).

Thought analysis

Quicksort uses dichotomy and recursion to pick up the middle of the array and then use two additional arrays. Iterate over each element in the array and compare it to the middle value (reference value), placing the elements less than the middle value in a new array, and placing the elements greater than the middle value in a new array. So all the elements in one new array must be less than the middle, and all the elements in the other new array must be greater than the middle. Similarly, two new arrays are broken up in the same way (perhaps recursively) until there is only one element left in the array. Finally, all the small arrays plus all the intermediate numbers plus all the large arrays are splicing together to get the desired result. The array nums: [12,1,8,10,21,25,4,30,6]

  • Computes the middle element in the current array, mid: 21, midIndex: 4
  • Nums puts elements greater than 21 in the new array right and elements less than 21 in the new array left, leaving left:[12,1,8,10,4,6], right :[25,30]
  • Continue with the binary split of the new array left and right as described above
    • Left array middle value: 10, left1: [1,8,4,6], right1: [12] (no splitting when only one element is left)
    • Middle value of right array: 30, lefT2: [25], right2: []
  • Now only left1 has more than one element, so keep splitting
    • Left1 array middle value: 4, left3: [1] (no longer split), right3: [8,6]
  • Median: 6, lefT4: [], right4: [8]
  • At this point, we’ve split all of them, and finally we want to merge all of the left, mid, and right together
  • Let’s use a picture to show the stitching process more intuitively:

Fast line of code

var midSort = function midSort(nums){
	if(nums.length <=1) return nums;
	let mid = Math.floor(nums.length/2),
		midNum = nums.splice(mid,1) [0];
	let left = [], right = [];
	nums.forEach(item= >{
		item < midNum ? left.push(item): right.push(item)
	})
	return midSort(left).concat(midNum,midSort(right));// Continue splitting the left and right arrays using recursion
}
Copy the code

conclusion

In this paper, we learned the fast sorting method in the classical sorting algorithm, which is relatively more efficient than bubble and insertion sorting, but it is still not the optimal algorithm. Welcome your favorite old iron to like, comment, add attention oh.