Shulou(Shulou.com)05/31 Report--

This article shows you the difference between arrays and linked lists in the database. The content is concise and easy to understand. It will definitely brighten your eyes. I hope you can get something through the detailed introduction of this article.

What's the difference between arrays and linked lists?

From the perspective of logical structure, the array must achieve a fixed length, which can not adapt to the dynamic increase or decrease of data, that is, the size of the array cannot be changed once it is defined. When data increases, it may exceed the number of previously defined elements; when data decreases, memory is wasted; dynamic storage allocation of linked lists can adapt to the dynamic increase and decrease of data, and data items can be easily inserted and deleted.

From the perspective of memory storage, the array allocates space from the stack (created on the heap with new), which is convenient and fast for programmers, but the degree of freedom is small; the linked list allocates space from the heap with a large degree of freedom, but the application management is more troublesome.

From the point of view of the access mode class, the array is continuously stored in memory, so it can be accessed by using the subscript index; the linked list is a linked storage structure, which can only be accessed in a linear manner from front to back when accessing elements. so the access efficiency is lower than the array.

A brief introduction to the process of quick sorting

Master the handwritten implementation of all common sorting algorithms, as well as the details of complexity.

Select a base element, usually the first or last element

The records to be sorted are divided into two independent parts by one sorting, and the element values of some records are smaller than those of the benchmark elements. The element value of the other part of the record is larger than the reference value.

At this point, the base element is in the correct position after it has been sorted.

Then the two parts of the records are sorted in the same way until the whole sequence is ordered.

Comparison of all kinds of sorting algorithms (proficiency)

In terms of time complexity

(1) order of square order (O (N2))

All kinds of simple sorting: direct insertion, direct selection and bubbling sorting

(2) order of linear logarithmic order (O (nlog2n))

Quick sort, heap sort, and merge sort

(3) O (N1 + §) sort, §is a constant between 0 and 1.

Hill ranking

(4) order of linear order (O (n))

Cardinal sort, in addition to bucket, box sort.

Description:

When the original table is ordered or basically ordered, directly inserting sorting and bubbling sorting will greatly reduce the number of comparisons and moving records, and the time complexity can be reduced to O (n).

On the contrary, when the original table is basically ordered, it will be degenerated into bubble sorting, and the time complexity will be increased to O (N2).

The order of the original table has little effect on the time complexity of simple selection sort, heap sort, merge sort and cardinality sort.

The above is what is the difference between arrays and linked lists in the database. Have you learned any knowledge or skills? If you want to learn more skills or enrich your knowledge reserve, you are welcome to follow the industry information channel.

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.