Graphic programmers must master 8 common sorting algorithms in Java

This article mainly introduces how Java implements eight common sorting algorithms: insert sort, bubble sort, select sort, Hill sort, quick sort, merge sort, heap sort and LST cardinal sort. Let's share them with you.

Classification 1) insert sort (direct insert sort, Hill sort) 2) exchange sort (bubble sort, quick sort) 3) select sort (direct select sort, heap sort) 4) merge sort 5) allocate sort (cardinal sort)

Maximum auxiliary space required: minimum auxiliary space required for merge sort: fastest average heap sort: quick sort

Unstable: quick sort, Hill sort, heap sort.

Let's take a look at the relationship between 8 sorts:

1. Insert sorting directly

(1) Basic idea: in a group of numbers to be sorted, it is assumed that the first (n-1) [n > = 2] numbers are already rows

Good order, now I want to insert the nth number into the previous ordinal number so that this n number

It's also in order. Repeat this cycle until all are in order.

(2) Instance

(3) Implemented in Java

2. Hill sort (minimum incremental sort)

(1) Basic idea: the algorithm first divides a group of numbers to be sorted into several groups according to a certain increment D (n / 2, n is the number of numbers to be sorted), and the subscript difference of records in each group is d. all elements in each group are directly inserted and sorted, and then a smaller increment is used (D / 2) group it, and then perform direct insertion sorting in each group. When the increment is reduced to 1, the sorting is completed after direct insertion sorting.

(2) Example:

(3) Implemented in Java

3. Simple selection and sorting

(1) Basic idea: in a group of numbers to be sorted, select the smallest number to exchange with the number in the first position;

Then, among the remaining numbers, find the smallest number to exchange with the number in the second position, and cycle until the penultimate number is compared with the last number.

(2) Example:

(3) Implemented in Java

4. Heap sorting

(1) Basic idea: heap sort is a tree selection sort, which is an effective improvement on direct selection sort.

The definition of heap is as follows: a sequence with n elements (H1, H2,..., HN) is called heap if and only if it satisfies (HI > = h2i, hi > = 2I + 1) or (HI < = h2i, hi < = 2I + 1) (I = 1,2, n / 2). Only the heap satisfying the former condition is discussed here. As can be seen from the definition of heap, The top element (i.e. the first element) must be the largest item (large top heap). A complete binary tree can intuitively represent the structure of the heap. The top of the heap is the root, and the others are the left and right subtrees. Initially, the sequence of numbers to be sorted is regarded as a binary tree stored in sequence. Adjust their storage order to make it a heap. At this time, the number of root nodes of the heap is the largest. Then, exchange the root node with the last node of the heap. Then The previous (n-1) number is readjusted to make it a heap. And so on, until the heap with only two nodes, exchange them, and finally get an ordered sequence with n nodes. From the description of the algorithm, heap sorting requires two processes: one is to establish the heap, and the other is to exchange the position between the top of the heap and the last element of the heap. So heap sorting consists of two functions. One is the penetration function of heap building, and the other is the function of repeatedly calling the penetration function to realize sorting.

(2) Example:

Initial sequence: 46,79,40,84

Build up:

Swap, kicking the maximum number from the heap

The remaining nodes rebuild the heap and exchange the maximum number of kicks

And so on: the last two remaining nodes in the last heap are exchanged, one is kicked out, and the sorting is completed.

(3) Implemented in Java

5. Bubble sorting

(1) Basic idea: in a group of numbers to be sorted, compare and adjust the two adjacent numbers from top to bottom for all the numbers within the range that have not been sorted, so that the larger number sinks and the smaller number rises. That is, whenever the two adjacent numbers are compared and found that their sorting requirements are opposite, they will be exchanged.

(2) Example:

(3) Implemented in Java

6. Quick sort

(1) Basic idea: select a reference element, usually the first element or the last element. Through one scan, the sequence to be arranged is divided into two parts, one is smaller than the reference element, and the other is greater than or equal to the reference element. At this time, the reference element is in the correct position after it is arranged, and then recursively sort the divided two parts in the same way.

(2) Example:

(3) Implemented in Java

7. Merge sort

(1) Basic sorting: merge sorting method is to merge two (or more) ordered tables into a new ordered table, that is, divide the sequence to be sorted into several subsequences, each subsequence is ordered, and then merge the ordered subsequences into an overall ordered sequence.

(2) Example:

(3) Implemented in Java

8. Cardinality sort

(1) Basic idea: unify all the values to be compared (positive integers) into the same digit length, and fill zero in front of the number with shorter digits. Then, start from the lowest bit and sort in turn. In this way, after sorting from the lowest bit to the highest bit, the sequence will become an ordered sequence.

(2) Example:

(3) Implemented in Java

The above is the whole content of this article. I hope it will be helpful to your study.