发一下牢骚和主题无关：
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.
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.
| 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.
After combining the above two facts, we get following relation.
Taking Log on both sides.
<= x
Since
=
, we can say
x =
Therefore, any comparison based sorting algorithm must make at least 
comparisons to sort the input array, and Heap Sort and Merge Sort are asymptotically optimal comparison sorts.
References
文章结束给大家分享下程序员的一些笑话语录：
那是习惯决定的，一直保持一个习惯是不好的！IE6的用户不习惯多标签，但是最终肯定还是得转到多标签的浏览器。历史（软件UI）的进步（改善）不是以个人意志（习惯）为转移的！
---------------------------------
原创文章 By
array和node
---------------------------------