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

Today, I will talk to you about what basic sorting methods there are. Many people may not know much about them. In order to let you know more, Xiaobian summarized the following contents for you. I hope you can gain something according to this article.

Basic sorting methods are: 1, selection sort, divided into "simple selection sort" and "heap sort";2, insertion sort, divided into "simple insertion sort" and "hill sort";3, exchange sort, divided into "bubble sort" and "quick sort";4, merge sort;5, radix sort.

base sorting

sort

No sorting algorithm is optimal in any case, and the optimal algorithm must be selected according to the actual situation to solve the problem.

Algorithm stability: in a group of records to be sorted, if there are any two equal records R and S, and R is before S in the records to be sorted, if R is still before S after sorting, that is, their positions do not change before and after sorting, then the sorting algorithm is said to be stable.

selection sort

Simple selection sort

Simple Selection Sort is an intuitive sorting algorithm. In the unsorted sequence, select the smallest element and exchange the first element of the sequence, then select the smallest element in the remaining unsorted sequence and exchange the second element of the sequence, and so on, finally forming a sorted sequence from small to large.

Time complexity: O(N2)

heap sort

generating a maximum heap from an unordered sequence, swapping the top element of the heap with the last element, generating the maximum heap from the remaining elements, and sequentially swapping elements to generate the maximum heap

Time complexity: O(N logN) Space complexity: O(1)

insertion sort

Simple insertion sort

A sequence to be sorted is divided into ordered and unsorted parts. In the initial state, the ordered sequence only contains the first element, and the elements in the unsorted sequence are N-1 elements except the first element. Thereafter, the elements in the unsorted sequence are inserted into the ordered sequence one by one. After N-1 insertions, the number of elements in the unsorted sequence is 0, and the sorting is completed.

Time complexity: O(N2) stable sorting

Hill sort

A group of elements to be sorted is divided into several sequences according to certain intervals, and insertion sorting is carried out respectively. Start with a large Interval, and gradually decrease the Interval in each round of sorting until the Interval is 1, that is, the final step is to perform simple insertion sorting

Time Complexity: Selection of and Incremental Sequences Related to Unstable Sorting

exchange sort

bubble sort

When sorting a sequence with N elements, N-1 cycles are performed. in that kth cycle, compare the elements from the 1st to the N-k th from front to back, compare two adjacent elements each time, if the former element is larger than the lat element, then the two elements exchange positions, otherwise the positions remain unchanged

Time complexity: O(N2)

quick sort

The unsorted elements are divided into two sub-sequences according to a "principal element" as a reference, wherein the records of one sub-sequence are all larger than the principal element and the records of the other sub-sequence are all smaller than the principal element, and then the two sub-sequences are sorted recursively in a similar way.

Time complexity: O(Nlog2N)

merge sort

A sequence with size N is regarded as N sub-sequences with length 1, and then adjacent sub-sequences are merged two by two to form N/2(+1) ordered sub-sequences with length 2(or 1); and then adjacent sub-sequences are merged two by two, and if the cycle continues until one sequence with length N remains, the sequence is the result of the original sequence after sorting is completed.

Time complexity: O(N log 2N) Space complexity: O(N)

radix sort

bucket sort

If it is known that the value range of N keywords is between 0 and M-1, and M is much smaller than N, then the bucket sorting algorithm establishes a "bucket" for each value of the keyword, that is, M buckets are established. When scanning N keywords, each keyword is placed into the corresponding bucket, and then it is naturally ordered according to the order of the buckets.

radix sort

Cardinality sort is an extension of bucket sort, considering records containing more than one keyword

After reading the above, do you have any further understanding of what basic sorting methods are available? If you still want to know more knowledge or related content, please pay attention to the industry information channel, thank you for your support.

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.