《算法导论课件第6讲.排序算法比较与基数排序》由会员分享，可在线阅读，更多相关《算法导论课件第6讲.排序算法比较与基数排序（26页珍藏版）》请在金锄头文库上搜索。
1、1,Comparison of Sorting Algorithms,Algorithm Worst case Average Space Usage Insertion n2/2 (n2) 1 Quicksort n2/2 (n log n) log n Mergesort n lg n (n log n) n Heapsort 2n lg n (n log n) 1 Ac.Heaps. n lg n (n log n) 1,Accelerated Heapsort currently is the method of choice.,2,比较排序的复杂度下界,下面我们证明所有基于比较的排序
2、算法的时间复杂度下界是(n log n)。于是在所有基于比较的排序算法中，归并排序、快速排序、堆排序和加速堆排序算法都是最优算法。 Comparison based sorting can be modeled by a binary tree that must have (n!) leaves. There are n! permutations, and at least 1 node for each permutation.,3,Lower Bounds for Sorting by Comparison of Keys,The Best possible! Lower Bound
3、for Worst Case Lower Bound for Average Behavior Use decision tree for analyzing the class of sorting algorithms (by comparison of keys) Assuming the keys in the array to be sorted are distinct. Each internal node associates with one comparison for keys xi and xj; labeled i :j Each leaf nodes associa
4、tes with one permutation (total n! permutations for problem size n) The action of Sort on a particular input corresponds to following one path in its decision tree from the root to a leaf.,4,Decision tree for sorting algorithms,n = 3,5,Decision Trees,The tree must be log n! levels deep. By Stirling
5、formula ：log n! = O(n log n) There are n! permutations, and at least 1 node for each permutation.,A1A0? (ZX?),A2A0? (ZX?),A2A1? (ZY?),A2A1? (ZY?),A1A0? (YX?),Yes,No,No,No,Yes,Yes,Yes,No,No,Yes,XYZ YZX XZY ZXY YXZ ZYX,XZY ZXY,XYZ,ZYX,YZX,YXZ,ZXY,XZY,YXZ YZX,6,Lower Bound for Worst Case,Lemma: Let L b
6、e the number of leaves in a binary tree and let h be its height. Then L = Ceiling lg L For a given n, L = n!, the decision tree for any algorithm that sorts by comparison of keys has height as least Ceiling lg n! . Theorem: Any algorithm to sort n items by comparisons of keys must do at least Ceilin
7、g lg n! , or approximately Ceiling n lg n 1.443 n , key comparisons in the worst case.,7,Lower Bound for Average Behavior,Theorem: The average number of comparisons done by an algorithm to sort n items by comparison of keys is at least lg n! or approximately n lg n 1.443 n The only difference from t
8、he worst-case lower bound is that there is no rounding up to an integer the average needs not be an integer, but the worst case must be.,8,Improvement beyond lower bound? Know more Do better,Up to now, only one assumption was make about the keys: They are elements of linearly ordered set. The basic
9、operation of the algorithms is a comparison of two keys. If we know more (or make more assumptions) about the keys, we can consider algorithms that perform other operations on them. / Recall algorithms for searching from unordered data vs. searching from ordered data,9,基数排序 Radix Sorting,对52张扑克牌按以下次
10、序排序： 23A23A 23A23A 两个关键字：花色（ ） 面值（23A） 并且“花色”地位高于“面值”,多关键字排序,10,基数排序 Radix Sorting,第一趟分配：按面值大小分成13堆 第一趟收集：按面值大小收集起来，即四张2，四张3，四张4 四张A 第二趟分配：按花色分成四堆（每堆里面值已经是从小到大排序好的） 第二趟收集：按花色大小收集。即得最终结果。,举例：,11,多关键字排序方法 最高位优先法（MSD)：先对最高位关键字k0（如花色）排序，将序列分成若干子序列，每个子序列有相同的k0值；然后让每个子序列对次关键字k1（如面值）排序，又分成若干更小的子序列；依次重复，直至就
11、每个子序列对最低位关键字kd-1排序；最后将所有子序列依次连接在一起成为一个有序序列。,基数排序 Radix Sorting,12,最低位优先法(LSD)：从最低位关键字kd-1起进行排序，然后再对高一位的关键字排序，依次重复，直至对最高位关键字k0排序后，便成为一个有序序列。 MSD与LSD不同特点 按MSD排序，必须将序列逐层分割成若干子序列，然后对各子序列分别排序。 按LSD排序，不必分成子序列，对每个关键字都是整个序列参加排序；并且可不通过关键字比较，而通过若干次分配与收集实现排序。,基数排序 Radix Sorting,13,该方法将排序关键字K看作是由多个关键字组成的组合关键字，即
12、K=k1k2kd。每个关键字ki表示关键字的一位，其中k1为最高位，kd为最低位，d为关键字的位数。 例如，对于关键字序列（101，203 567，231，478，352），可以将每个关键K看成由三个单关键字组成，即K= k1k2k3，每个关键字的取值范围为0ki9，所以每个关键字可取值的数目为10，通常将关键字取值的数目称为基数，用符号r表示，在这个例子中r=10。对于关键字序列（AB,BD,ED）可以将每个关键字看成是由二个单字母关键字组成的复合关键字，并且每个关键字的取值范围为“AZ”，所以关键字的基数r=26。,基数排序 Radix Sorting,14,Radix Sort,Init
13、ial List: 27 91 1 97 17 23 84 28 72 5 67 25,15,Radix Sort,Assume that the sorting data are positive integers, radix sort will distribute the numbers into 10 boxes according to the first digit, then collect the numbers in the way that keeps the order from the 10 boxes. Again distribute the numbers in
14、to 10 boxes according to the second digit, collect them in order, and so on, until the highest digit has been treated.,16,Radix Sort,0 1 2 3 4 5 6 7 8 9,0 1 2 3 4 5 6 7 8 9,Initial List: 27 91 1 97 17 23 84 28 72 5 67 25 Result of first pass: 91 1 72 23 84 5 25 27 97 17 67 28 Result of second pass:
15、1 5 17 23 25 27 28 67 72 84 91 97,First Pass (on right digit),Second Pass (on left digit),17,Radix Sort e.g Start from least significant digit,18,链式基数排序 基数排序：借助“分配”和“收集”对单逻辑关键字进行排序的一种方法。 链式基数排序：用链表作存储结构的基数排序。,基数排序 Radix Sorting,19,链式基数排序步骤 设置10个队列，fi和ei分别为第i个队列的头指针和尾指针。 第一趟分配对最低位关键字（个位）进行，改变记录的指针值，将
16、链表中记录分配至10个链队列中，每个队列记录的关键字的个位相同。 第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列链成一个链表。 重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到一个有序序列。,基数排序 Radix Sorting,20,例,21,22,23,Radix Sort: Algorithm,List radixSort (List L, int radix, int numFields) List buckets = new Listradix; int field; / filed number within the k
