Comparison of Several Sorting Algorithms

Overall comparison between the first and eighth sorting algorithms

Second, the characteristics of each algorithm (see the blog at the back for specific implementation)

1. Quick line

(1) algorithm idea

Select a reference element, put the element smaller than the reference element in the front and the element larger than the reference element in the back, and then sort the subsequence of the element smaller than the reference value and the subsequence larger than the reference element according to the original method until the whole sequence is orderly;

(2) Advantages and disadvantages

Advantages: the data movement speed is extremely fast;

Disadvantages: instability;

(3) Efficiency analysis

When the sequence is chaotic, this sorting algorithm is more efficient. When the data is in order, it will degenerate into bubble sorting;

(4) Selection of benchmarks

A. take the middle value of three numbers

The specific idea is: sort the data in the low, middle and high positions in the sequence to be sorted, take the data as the fulcrum, and store the fulcrum with the subscript element of 0;

B. Random selection of benchmarks

Reasons for introduction: when the column to be sorted is partially sorted, the fixed selection of pivot makes the quick sorting inefficient;

The specific idea is: take any element in the column to be sorted as the benchmark;

(5) Optimization method

A. When the length of the sequence to be sorted is divided into certain sizes, insert sorting is used;

Reason: For very small and partially ordered arrays, quick sorting is not as good as inserting. When the length of the sequence to be sorted is divided to a certain size, the efficiency of continuous segmentation is worse than that of insertion sorting, so interpolation can be used instead of fast sorting.

B. After one division, elements equal to keys can be grouped together, and it is unnecessary to divide elements equal to keys when continuing the next division;

(6) Application scenarios

A. Find the k smallest number in the array.

Take an element m in the array as the basis of division, that is, m=arr[0]. If the number of elements in front of m is greater than k, then the k-th smallest number must be in the elements in front of m, then we only need to continue to look for the k-th smallest number in the elements in front of m; If the element before m is less than k, then the k-th smallest number must be in the element after m, then we only need to find the k-th smallest number in the element after m;

2. Bubble classification

(1) basic principle

In a set of numbers to be sorted, compare all the numbers in the current unsorted range from top to bottom, so that the larger number sinks and the smaller number rises. That is, whenever two adjacent numbers are compared and their ordering is found to be contrary to the ordering requirements, they are exchanged.

(2) Advantages and disadvantages

Advantages: stability

Disadvantages: slow, only two adjacent data can be moved at a time;

3. Insert sort

(1) basic idea

Insert a record into the sorted ordered table and get a new ordered table with the number of records increased by 1. That is, the first record of the sequence is regarded as an ordered subsequence, and then the second record is inserted one by one until the whole sequence is ordered.

(2) Advantages and disadvantages

Advantages: stable and fast.

Disadvantages: the number of comparisons is not necessarily the same. The fewer comparisons, the more data will be moved after the insertion point, especially when the amount of data is huge.

4. Heap sorting

4. 1, binary heap definition:

Binary heap is a complete binary tree or an approximate complete binary tree. Binary heap satisfies two characteristics:

(1) The key value of the parent node is always greater than or equal to (less than or equal to) the key value of any child node;

(2) The left subtree and the right subtree of each node are a binary heap;

When the key value of the parent node is always greater than or equal to the key value of any child node, it is a big root heap. When the key value of the parent node is always less than or equal to the key value of any child node, it is a small root heap;

4.2, heap storage:

Generally, the heap is represented by an array, and the parent subscript of the I node is (i- 1)/2. The subscripts of its left and right child nodes are 2*i+ 1 and 2*i+2 respectively.

4.3, the insertion of the heap:

Each insert puts new data at the end of the array. We can find that this new data must be an ordered sequence from the parent node to the root node, and then insert this new data into this ordered data.

(1) The basic idea of sorting by big piles

Firstly, the initial array is built into a big root heap, which is the initial disordered area;

Then, the largest element is exchanged with the last record of the disordered region, so as to obtain new disordered region and ordered region, and satisfy the following requirements.

Because the new root may violate the heap attribute after the exchange, the current unordered area is adjusted to the heap. Then, the largest element is exchanged with the last record of the interval again, and new disordered areas and ordered areas are obtained, which still meet the relationship values.

..........

Until there is only one element left in the disordered area;

4.4: Application

Find out the first k smallest numbers among the m numbers and arrange them in order;

Time complexity: O(K)[ time complexity of creating the maximum heap of k elements] +(M-K)*log(K)[ compare the remaining m-k data, and heap the maximum heap from the new maximum heap at a time]

5. Hill sort

(1) basic idea

Firstly, the whole sequence of elements to be sorted is divided into several subsequences (composed of elements separated by certain increments) for direct insertion sorting, and then the increments are successively decreased before sorting. When the elements in the whole sequence are basically orderly (the increment is small enough), all the elements are directly inserted and sorted once (because it is very efficient to directly insert and sort when the elements are basically orderly);

(2) Applicable scenarios

The most important operation in Hill sorting is comparison, not exchange. Hill sorting with the best known step sequence is faster than direct insertion sorting, even faster than fast sorting and heap sorting in small arrays, but when a large number of data are involved, Hill sorting is still not as fast as fast sorting.

6. Merge and sort

(1) basic idea

Firstly, the n records of the initial sequence are regarded as n ordered subsequences, and the length of each subsequence is 1. Then, n/2 ordered subsequences of length 2 are merged in pairs, and several ordered subsequences of length 4 are merged in pairs, and so on until an ordered sequence of length n is obtained.

(2) Applicable scenarios

If n is large and the sorting is stable, you can choose merge sorting;

7. Just select the sort.

(1) basic idea

First pass: starting from the first record, compare the following n- 1 records, and find out the smallest record to exchange with the first record;

Second pass: starting from the second record, compare the next n-2 records and find out the smallest record to exchange with the second record;

...........

Pass I: starting from the record I, compare the following n-i records and find out the smallest record to exchange with the record I;

By analogy, after n- 1 times of comparison, n- 1 records are in place, and the remaining largest record is directly ranked last;