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

Data structure and algorithm Learning Notes are suitable for large-scale data sorting preface

In the data sorting algorithm, different data sizes should use appropriate sorting algorithm to achieve the best results, such as small-scale data sorting, we can use bubble sort, insert sort, select sort, their time complexity is O (N2), large-scale data sorting can use merge sort and fast sort, the time complexity is O (nlogn). Today we'll take a look at merge sort and quick sort.

The core idea of the principle of merging and sorting the text (divide and conquer):

Sort the array, divide the array into front and back parts from the middle, sort the front and back parts separately, and then put them together, the array is ordered.

Performance Analysis of merge sorting

1. Merge sorting is a stable sorting algorithm: in the process of merging, if there are the same elements between A [p. Q] and A [Q + 1. R], the elements in A [p. Q] are first put into the tmp array. This ensures that the order of elements with the same value remains the same before and after the merge.

two。 The time complexity of merge sorting is O (nlogn): when solving the recursive problem, we draw a conclusion: the recursive problem can be written as a recursive formula, and the time complexity of the recursive code can also be written as a recursive formula.

We assume that the time required for merging and sorting n elements is T (n), and the time for sorting into two subarrays is T (nprime 2). The formula for calculating the time complexity of merging sorting can be obtained by applying the conclusion:

When T (1) = C; nasty 1, only a constant order of magnitude of execution time is needed, so it is expressed as C. T (n) = 2mm T (nprime 2) + n; n > 1

Decompose the formula again:

T (n) = 2 ~ T (napace 2) + n = 2 * (2 ~ T (npx4) + n = 4 ~ T (nx4) + 2 ~ n = 4 * (2 ~ T (npach8) + nachp4) + 2 ~ n = 8 ~ T (nlap 8) + 3 ~ n = 8 * (2 ~ T (nlap 16) + nap8) + 3 ~ n = 16 ~ T (nhand 16) + 4 ~ n. = 2 ^ k * T (n / 2 ^ k) + k * n.

We can get T (n) = 2 ^ KT (n / 2 ^ k) + kn. When T (n / 2 ^ k) = T (1), that is, n / 2 ^ k = 1, we will get k=log2n and ask you to bring k into the formula to get

T (n) = Cn+nlog2n

Expressed as T (n) by the big O mark, it equals O (nlogn).

And the time complexity is very stable: the best case, the worst case, or the average case, the time complexity is O (nlogn)

3. The space complexity of merge sorting is O (n).

Fatal drawback of merge sorting: merge sorting is not an in-place sorting algorithm (extra storage space is needed when merging two ordered arrays)

The space complexity of recursive code cannot be as cumulative as time complexity, although additional memory space is required for each merge operation. However, after the merge is completed, the temporarily opened memory space is released, and the maximum temporary memory space will not exceed the size of n data.

The principle of quick sorting

If you want to sort a set of data in the array with subscript from p to r, we select any data between p and r as the pivot (partition point), traverse the data, see less than pivot on the right, greater than pivot on the left. In this way, the array is divided into three parts, recursively sorting the data from p to QMel 1 and the subscript from Qothers 1. The data between r and r until the interval is reduced to 1, indicating that the data are in order.

The time complexity of quick sorting is O (1): in the sorting process, if we encounter the need to move data, we can use the idea of exchange.

(the picture comes from the network, intruding and deleting)

The space complexity is O (1).

What is the difference between quick sort and merge sort?

Look at the picture:

(the picture comes from the network, intruding and deleting)

Differences in processing:

Recursive sorting: deal with sub-problems before merging

Quick sort: partition first, then deal with sub-problems

Although merge sorting is stable and has a time complexity of O (nlogn), it is not an in-situ sorting algorithm, and extra space is needed in the merging process.

Performance Analysis of Quick sort

The time complexity of recursive code is that if each partition operation can exactly divide the array into two equal sizes, then the recursive formula of fast sorting and recursive sorting are the same, so the time complexity of fast sorting is O (nlogn).

However, it is very difficult to achieve such a uniform distribution every time.

The time complexity of T (n) is O (nlogn) in most cases, and it will be reduced to O (N2) only in extreme cases.

Postscript

Recursion and fast arrangement are the idea of divide and conquer, the code is realized by recursion, and the process is very similar. The time complexity of merge sorting is very stable to O (nlogn), but each merge requires extra space, and the space complexity is very high. Although the worst time complexity of fast sorting algorithm is O (N2), but the average time complexity is O (nlogn), we can avoid the worst case.

Related articles

Data structure and algorithm to learn the correct posture of writing linked list codes for notes (part two)

Data structure and algorithm linked list of Learning Notes to improve Reading performance (part I)

Data structures and algorithms learn the 0-numbered array of notes

Data structure and algorithm "bucket" after learning notes

Data structure and algorithm first-in-first-out queue of learning notes

Data structure and algorithm Learning Note efficient and concise coding skills "Recursion"

Data structure and algorithm Learning Notes how to analyze a sorting algorithm?

The above are personal study notes and are used for learning and communication only.

Welcome to follow the official account, irregular practical information, only make valuable output.

Author: Dawnzhang

Source: https://www.cnblogs.com/clwydjgs/

The boat died and Jiang Hai spent the rest of his life. -- Fox

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.