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

This article introduces the relevant knowledge of "what are the sorting algorithms commonly used in Java". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

One: the concept of sorting

1. Sorting: the so-called sorting is the operation of arranging a string of records according to the size of one or some of the keywords.

two。 Stability: assuming that there are multiple records with the same keywords in the sequence to be sorted, the relative order of these records remains unchanged, that is, in the original sequence, r [I] = r [j], and r [I] is before r [j], while in the sorted sequence, r [I] is still before r [j], the sorting algorithm is said to be stable; otherwise, it is called unstable.

3. Internal sort: a sort in which all data elements are placed in memory.

4. External sorting: there are too many data elements to be placed in memory at the same time, and the sorting of data cannot be moved between internal and external memory according to the requirements of the sorting process.

Second, common sorting methods:

Third, the implementation principle of various sorting algorithms: `

(1) the basic idea of insertion sorting:

Direct insertion sorting is a simple insertion sorting method, and its basic idea is to insert the records to be sorted into an ordered sequence one by one according to the value of its key code, until all the records have been inserted. Get a new ordered sequence.

**

When inserting the I (I > = 1) element, the preceding array [0], array [1],... , Array [I-1] has been sorted, then use the sorting code of array [I] and Array [I-1], Array [I-2],... The order of the sorting code is compared to find that the insertion position is to insert array [I], and the order of the elements in the original position is moved back.

A summary of the features of the direct insertion sort:

The closer the set of elements is to order, the more time-efficient the direct insertion sorting algorithm is.

Time complexity: O (N ^ 2)

Space complexity: O (1), which is a stable sorting algorithm.

Stability: stability

(2) Hill sort (reduced incremental sort)

Hill sorting method is also known as shrinking incremental method. The basic idea of Hill sorting method is to select an integer first, divide all the records in the file to be sorted into a group, divide all the records with distance into the same group, and sort the records in each group. Then, fetch and repeat the above grouping and sorting work. When it reaches = 1, all records are sorted within the unified group.

Summary of the characteristics of Hill sorting:

Hill sorting is an optimization of direct insertion sorting.

When gap > 1, it is pre-sorted in order to make the array more ordered. When gap = 1, the array is nearly ordered, so

It will be soon. In this way, on the whole, the optimization effect can be achieved. After we implement it, we can compare the performance test.

The time complexity of Hill sorting is difficult to calculate, so it needs to be deduced, and the average time complexity is derived: O (N ^ 1.3-N ^ 2)

Stability: instability

(3) Select sort

Basic ideas:

Each time, the smallest (or largest) element is selected from the data elements to be sorted, and stored at the beginning of the sequence until all the elements to be sorted

The data elements are finished.

Directly select sort:

Select the data element with the largest (smallest) key in the set of elements Array [I]-Array [n-1]

If it is not the last (first) element in the group, swap it with the last (first) element in the group

Repeat the above steps in the remaining Array [I]-Array [n-2] (Array [I + 1]-- Array [n-1]) set until there is 1 element left in the set

A summary of the characteristics of the direct selection sort:

Direct selection sorting thinking is very easy to understand, but the efficiency is not very good. Seldom used in practice

Time complexity: O (N ^ 2)

Space complexity: O (1)

Stability: instability

(4) Heap sorting

Heap sorting (Heapsort) is a sort algorithm designed by using the data structure of heap tree (heap). It is a kind of selective sorting. It selects data through the heap. It should be noted that large piles should be built in ascending order and small piles should be built in descending order.

Heap sorting uses heap to select numbers, which is much more efficient.

Time complexity: O (N*logN)

Space complexity: O (1)

Stability: instability

(5) Bubble sorting

The basic idea: the so-called exchange is to change the position of the two records in the sequence according to the comparison results of the key values of the two records in the sequence. the characteristic of exchange sorting is to move the records with larger key values to the tail of the sequence. records with smaller key values move to the front of the sequence.

Summary of the characteristics of bubble sorting:

Bubble sort is a sort that is very easy to understand.

Time complexity: O (N ^ 2)

Space complexity: O (1)

Stability: stability

(6) Quick sort

Quick sorting is a kind of exchange sorting method with binary tree structure proposed by Hoare in 1962. Its basic idea is: take an element in the sequence of elements to be sorted as the reference value, divide the set to be sorted into two subsequences according to the sorting code, all elements in the left subsequence are less than the reference value, all elements in the right subsequence are greater than the reference value, and then the leftmost and right subsequence repeats the process. Until all the elements are arranged in the corresponding position.

Summary of the characteristics of quick sorting:

The overall performance and usage scenarios of quick sort are good, so it is dared to call it quick sort.

Time complexity: O (N*logN)

Space complexity: O (logN)

Stability: instability

(7) merge and sort

Basic ideas:

Merge sorting (MERGE-SORT) is an effective sorting algorithm based on merge operation, which is a very typical application of divide-and-conquer (Divide andConquer). The ordered subsequences are merged to get a completely ordered sequence, that is, each subsequence is ordered first, and then the subsequence segments are ordered. If two ordered tables are merged into one ordered table, it is called two-way merging.

Summary of the characteristics of merge sorting:

The disadvantage of merging is that the space complexity of O (N) is needed, and the thinking of merging sorting is more to solve the problem of external sorting in disk.

Time complexity: O (N*logN)

Space complexity: O (N)

Stability: stability

Fourth: the comparison of time complexity, space complexity and stability of various sorting algorithms.

This is the end of the content of "what sort algorithms are commonly used in Java". Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.