Sorting Algorithms Summary
Sorting Algorithms Summary Comparison-based Sorting: 4 Decision Tree Model: for study the limit of comparison-based sorting Prove: The lower bound of running time for any c-based sorting algorithm is nlogn --> omega(nlogn), both of Heap Sort and Merge Sort are almost the best of them. 1. Insertion sort: worst case theta(n^2) suitable for the small size of input data in-place sorting: 除待排序数组本身，仅有常数个元素需要存储 2. Merge sort: theta(nlogn) non-in-place sorting 3. Heap sort: O(nlogn) in-place sorting 4. Quicksort: in-place sorting worst case theta(n^2) expected running time theta(nlogn) in the real situation, it is faster than Heap Sort 与insertion sort类似，二者code紧凑，运行时间隐含常数系数很小 Suitable for the Large size of input data Non-Comparison-based Sorting --it may break the lower bound of nlogn. 1. 计数排序 Counting Sort 假定输入元素值均在集合{0，1，2，..., k}内，用数组索引作为确定相对次序的工具 running time: theta(k+n) k = O(n), linear time 2. 基数排序 Radix Sort 扩展计数排序的适用范围 n个整数，每个整数d位数字，每个数...