“This is the 9th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

[B] [C] [D]

Given an integer array nums, please sort the array in ascending order.

Example 1:

Input: nums = [5,2,3,1] output: [1,2,3,5]Copy the code

Example 2:

Nums = [5,1,1,2,0,0] output: [0,0,1,1,2,5]Copy the code

Tip:

  1. 1 <= nums.length <= 50000
  2. -50000 <= nums[i] <= 50000

Nums = nums; nums = nums

About common sorting methods, I have a summary of the previous article, interested partners can go to the “common array sorting algorithm”, so here is no longer on the various sorting process and implementation of repeated statements

In this case, THE following sorting methods are used to submit, and the time records of each sorting algorithm are as follows:

Bubble sort 8480ms select sort 2576ms insert sort 6080ms Hill sort 136ms merge sort 4056ms quicksort 2944ms count sort 132ms array.sort 136msCopy the code

It should be noted that in this case, the quicksort algorithm uses the exchange elements to sort, while the quicksort algorithm splits the left and right arrays by reference values because of the high space complexity, resulting in stack explosion and cannot be submitted

It should be noted here that the user record above is only the time record of the submission, and the time of each submission of Leetcode will fluctuate due to network and other reasons. For example, shellSort and Array. Sort are all submitted over 110ms

But the data is still good enough to say which sorting algorithms are better

The shortest times are Hill sort, counting sort, and array.sort

Hill sort can reduce the moving distance of insertion sort by optimizing the step splitting of insertion sort, so as to achieve efficient sort

Count sort Uses the subscript array to record the values of the elements in the original array and the number of occurrences of this value. Then, the count array is iterated to obtain the sorted array. This process does not involve comparing sizes, and therefore is faster than any comparison sort algorithm.

Array.sort looks at the V8 source code and you can see that when the sort interval is less than or equal to 10, insert sort is used, whereas quicksort is used, and its quicksort is definitely more optimized than the quicksort in my article, so it achieves such a high efficiency of sorting

V8 array.js InnerArraySort 710 line

At this point, we are done with leetcode 912. Sorting arrays

If you have any questions or suggestions, please leave a comment!