6 years ago (2014-12-30)  Algorithm language |   First to comment  10 
post score 0 times, average 0.0

1. Insert sorting: Each time a record to be scheduled is inserted into the proper queue in the previous queue.

1. Direct insertion sort

The direct sorting method is in the best case (the sorting sequence has been key-ordered), and only one comparison is needed for each sorting without moving elements.Therefore, n elements are compared by n-1 and the number of movements is 0. In the worst case (reverse order), the ith element must be compared with the previous element i times, the number of shifts is i+1, so the total number of comparisons is relatively large, and the summary is not written: it is a kind of stability. The sorting method, the time complexity O(n^2), only one auxiliary space in the sorting process, so the space complexity O(1)

2. Hill sorting

Reduced incremental sorting, an improved insert insertion method for insert sorting. Summary: It is an unstable sorting method with time complexity O(n^1.25) and space complexity O(1)

2. Exchange sorting

Bubble sort

In the best case, it is a positive sequence, so as long as it is compared once, the worst case of the complexity O(n) is the reverse order, which is compared to n^2 times, and the complexity O(n^2) is summarized. : Stable sorting method, time complexity O(n^2), space complexity O(1), when the sequence to be ordered is ordered, the effect is better.

2. Quick sort

The records to be arranged are divided into two independent parts by one sort. Among them, some of the records have keywords that are smaller than those of the other part, and then the records of these two parts are further sorted to achieve the entire sequence. . Summary: In all ranking methods with the same order of magnitude O (nlogn), fast sorting is the best method of performance, and is best when the sequence to be ordered is disordered.The time complexity of the algorithm is O(nlogn), the worst time complexity O(n^2), and the space complexity O(nlogn)

3 choose to sort

1 direct selection

It has nothing to do with the initial state of the sequence. Summary: Time complexity O(n^2), best or worst

2. Heap sorting

Improvements in Direct Selection Ordering Summary: Time complexity O(nlogn), O(nlogn) in both the best and worst case

4. Merge sort

Summary: time complexity O(nlogn), space complexity O(n)

5. Cardinal sort

Sorting by the values ​​of the various digits that make up the key is a sort of allocation sort.It is possible to sort without having to compare the code values. Summary: Time complexity O(d(n+rd))

Overall summary:

When n is relatively small, it is suitable for insert sorting and sorting when the sorting is basically orderly. It is suitable for direct insert sorting and bubbling sorting when n is large, but when the number of keywords is small, it is suitable when the chain radix sorting n is large. Suitable for quick sorting Heap sorting Merge sorting Disordered, suitable for quick sorting Stable sorting: bubble sort insert sorting merge sorting cardinality sorting complexity O(nlogn): quick sorting heap sorting merge sorting auxiliary space (large size): Merge Sort Quick Sort Good or bad: same as simple selection (n^2), heap sort (nlogn), merge sort (nlogn) O(n): insert sort bubble sort




转载注明原文出处:Baiyuan's Blog>>https://wangbaiyuan.cn/en/data-summary-several-time-and-space-complexity-of-sorting-algorithms-2.html

Post comment


No Comment


Forget password?