Sorting

阅读量：4151 次

发布时间：2019-05-25

本文共 4763 字，大约阅读时间需要 15 分钟。

A sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order. There are two mainly kind of sorting algorithms.

1) comparison based sorting algorithms.

Insertion Sort - A simple and slow sorting algorithm that repeatedly takes the next element from the un-sorted section and inserts it into the sorted section at the correct position.

Selection Sort - A simple and slow sorting algorithm that repeatedly selects the lowest or highest element from the un-sorted section and moves it to the end of the sorted section.

Bubble Sort - A simple and slow sorting algorithm that repeatedly steps through the collection, compares each pair of adjacent elements and swaps them if they are in the wrong order.

Quick Sort - A complex and fast sorting algorithm that repeatedly divides an un-sorted section into a lower order sub-section and a higher order sub-section by comparing to a pivot element.

Merge Sort - A complex and fast sorting algorithm that repeatedly divides an un-sorted section into two equal sub-sections, sorts them separately and merges them correctly.

Heap Sort - A complex and fast sorting algorithm that organizes original collection into a heap which is a binary tree with every node higher that its children in order, then repeatedly takes the root node to the end of the sorted section and rebuilds the heap with remaining notes.

Shell Sort - A complex and fast sorting algorithm that repeatedly divides the entire collection into sub-collections by taking every h-th element for a fixed gap h and performs an insertion sort each sub-collection.

2) distribution based sorting algorithms.

Counting Sort - A simple and fast sorting algorithm that creates an integer array of size |S| and using the ith bin to count the occurrences of the ith member of S in the input. Each input is then counted by incrementing the value of its corresponding bin. Afterward, the counting array is looped through to arrange all of the inputs in order.

Bucket Sort - A complex and fast sorting algorithm that divides an array into a finite number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. Bucket sort is a generalization of Counting Sort and is a cousin of Radix Sort.

Radix Sort - A complex and fast sorting algorithm that sorts the array by the least significant radix first and then do the same process to second-least significant radix, until we get to the most significant radix, at which point the final result is a properly sorted list.

**Comparison Table Of Different Sorting Algorithms**
Soring Algorithm	Stability	Space Complexity	Time Complexity (Ave.)	Time Complexity (Worst.)	Time Complexity (Best.)
Insertion Sort	Yes	O(1)	O(n^2)	O(n^2)	O(n)
Selection Sort	Yes	O(1)	O(n^2)	O(n^2)	O(n^2)
Bubble Sort	Yes	O(1)	O(n^2)	O(n^2)	O(n)
Quick Sort	No	O(logn)	O(nlogn)	O(n^2)	O(nlogn)
Merge Sort	Yes	O(n)	O(nlogn)	O(nlogn)	O(n)
Heap Sort	No	O(1)	O(nlogn)	O(nlogn)	O(nlogn)
Shell Sort	No	O(1)	NIL	O(n^2)	O(n^1.3), n in some range
Counting Sort	NIL	O(k)	O(n+k)	NIL	NIL
Bucket Sort	NIL	O(n*k)	NIL	O(n^2)	O(n+k)
Radix Sort	Yes	O(r) r is the radix	O(d(n+r)) d is the length of max digit	NIL	NIL

Lower bound for comparison based sorting algorithms

The problem of sorting can be viewed as following.

Input: A sequence of n numbers <a1, a2, . . . , an>.

Output: A permutation (reordering) <a‘1, a‘2, . . . , a‘n> of the input sequence such that a‘1 <= a‘2 ….. <= a‘n.

A sorting algorithm is comparison based if it uses comparison operators to find the order between two numbers. Comparison sorts can be viewed abstractly in terms of decision trees. The execution of the sorting algorithm corresponds to tracing a path from the root of the decision tree to a leaf. At each internal node, left subtree dictates subsequent comparisons for ai < aj, and the right subtree dictates subsequent comparisons for ai > aj. When we come to a leaf, the sorting algorithm has established the ordering. So we can say following about the decison tree.

1) Each of the n! permutations on n elements must appear as one of the leaves of the decision tree for the sorting algorithm to sort properly.

2) Let x be the maximum number of comparisons in a sorting algorithm. The maximum height of the decison tree would be x. A tree with maximum height x has at most 2^x leaves.

After combining the above two facts, we get following relation.

n! <= 2^x

Taking Log on both sides.

<= x

Since   = ,  we can say

x =

$\Omega(nLog_2n)$

Therefore, any comparison based sorting algorithm must make at least $\Omega(Log_2n)$ comparisons to sort the input array, and Heap Sort and Merge Sort are asymptotically optimal comparison sorts.

References

转载地址：http://ghxti.baihongyu.com/

你可能感兴趣的文章