What are the basic sorting methods?

Basic sorting methods include: 1. Selection sort, which is divided into "simple selection sort" and "heap sort"; 2. Insertion sort, which is divided into "simple insertion sort" and "Hill sort"; 3. Exchange sorting is divided into "bubble sort" and "quick sort"; 4. Merge sort; 5. Radix sort.

Basic sorting method

Sort

No A sorting algorithm is optimal under any circumstances, and the optimal algorithm must be selected according to the actual situation to solve the problem

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

• Selection Sort

Simple Selection Sort

Simple Selection Sort is an intuitive The sorting algorithm selects the smallest element in the unsorted sequence and exchanges it with the first element of the sequence, and then selects the smallest element in the remaining unsorted sequence and exchanges it with the second element of the sequence, and so on. Finally, a sorted sequence from small to large is formed

Time complexity: O(N2)

Heap sort

Generate the unordered sequence into a maximum heap, and put the top of the heap Swap the elements with the last element, and generate the maximum heap with the remaining elements. Exchange the elements in sequence and generate the maximum heap

Time complexity: O(NlogN) Space complexity: O(1)

• Insertion sort

Simple insertion sort

Divide a set of sequences to be sorted into sorted There are two parts, ordered and unsorted. In the initial state, the sorted sequence only contains the first element, and the elements in the unsorted sequence are N-1 elements except the first one; thereafter, the elements in the unsorted sequence are added one by one. Insert into sorted sequence. In this way, after N-1 insertions, the number of elements in the unsorted sequence is 0, then the sorting is completed

Time complexity: O(N2) Stable sorting

Hill sorting

Divide a set of elements to be sorted into several sequences at certain intervals, and perform insertion sorting respectively. The "interval" set at the beginning is larger, and the interval is gradually reduced in each round of sorting, until the "interval" is 1, that is, the last step is to perform simple insertion sorting

Time complexity: and increment The selection of sequences is related to non-stable sorting

• Exchange sorting

Bubble sorting

For elements When sorting N sequences to be sorted, a total of N-1 cycles are performed. In the k-th loop, the elements from the 1st to the N-kth are compared from front to back, and the two adjacent elements are compared each time. If the former element is greater than the latter element, the two exchange positions, otherwise they remain Position unchanged

Time complexity: O(N2)

Quick sort

Divides the unsorted elements into two subsequences based on a "pivot" as the basis, The records of one subsequence are all greater than the pivot, while the records of the other subsequence are smaller than the pivot, and then the two subsequences are sorted recursively using a similar method

Time complexity: O(Nlog2N)

• Merge sort

Treat a sequence of size N as N subsequences of length 1. Next Merge adjacent subsequences in pairs to form N/2 (1) ordered subsequences with a length of 2 (or 1); then continue to merge adjacent subsequences in pairs. If you keep looping, until If there is one sequence left with length N, then this sequence is the result of sorting the original sequence

Time complexity: O(Nlog2N) Space complexity: O(N)

• Radix sort

#Bucket sort

If it is known that the value range of N keywords is from 0 to M- 1, and M is much smaller than N, the bucket sorting algorithm creates a "bucket" for each value of the keyword, that is, M buckets are created, and when scanning N keywords, each keyword is placed into the corresponding bucket, and then collect them in the order of the buckets to be naturally ordered

radix sort

Radix sort is a generalization of bucket sort. The records to be sorted it considers include More than one keyword

The above is the detailed content of What are the basic sorting methods?. For more information, please follow other related articles on the PHP Chinese website!