北大数据结构讲义sort.ppt

目录 1、概述 Simple sorts Straight selection sort Bubble sort Insertion sort More complex sorts Quick sort Merge sort Heap sort 4、选择排序 Selection Sort: Pass One Selection Sort: End Pass One Selection Sort: Pass Two Selection Sort: End Pass Two Selection Sort: Pass Three Selection Sort: End Pass Three Selection Sort: How Many Comparisons? For Selection Sort in General The number of comparisons when the array contains N elements is Sum = (N-1) + (N-2) + . . . + 2 + 1 = O(n2) 4、选择排序 4、选择排序 4、选择排序 Heap Sort Approach 4、选择排序 4、选择排序 4、选择排序 4、选择排序 4、选择排序 4、选择排序 4、选择排序 4、选择排序 4、选择排序 4、选择排序 5、归并排序 5、归并排序 5、归并排序 5、归并排序 5、归并排序 5、归并排序 5、归并排序 5、归并排序 5、归并排序 5、归并排序 5、归并排序 5、归并排序 5、归并排序 5、归并排序 5、归并排序 5、归并排序 5、归并排序 5、归并排序 5、归并排序 5、归并排序 6、基数排序 6、基数排序 6、基数排序 6、基数排序 6、基数排序 6、基数排序 6、基数排序 6、基数排序 6、基数排序 6、基数排序 6、基数排序 6、基数排序 6、基数排序 6、基数排序 6、基数排序 6、基数排序 6、基数排序 6、基数排序 6、基数排序 6、基数排序 6、基数排序 6、基数排序 6、基数排序 6、基数排序 6、基数排序 6、基数排序 6、基数排序 6、基数排序 6、基数排序 6、基数排序 6、基数排序 6、基数排序 6、基数排序 7、各种内部排序方法的比较讨论 7、各种内部排序方法的比较讨论 7、各种内部排序方法的比较讨论 1、基数排序： e.g: B = 5 、2、9、7、18、17、52 用基数排序法进行排序。 B = 2、52、5、7、17、8、9 （第一次收集的结果） B0 B1 B2 B3 B4 B5 B6 B7 B8 B9 口袋 根据 所指向的 数，进行分配动作， 将其分配到相应的口 袋。和第一次不同， 这次根据右起第二位 数字（十位数字）进 分配。 2 1、基数排序： e.g: B = 5 、2、9、7、18、17、52 用基数排序法进行排序。 B = 2、52、5、7、17、8、9 （第一次收集的结果） B0 B1 B2 B3 B4 B5 B6 B7 B8 B9 口袋 根据 所指向的 数，进行分配动作， 将其分配到相应的口 袋。和第一次不同， 这次根据右起第二位 数字（十位数字）进 分配。 2 1、基数排序： e.g: B = 5 、2、9、7、18、17、52 用基数排序法进行排序。 B = 2、52、5、7、17、8、9 （第一次收集的结果） B0 B1 B2 B3 B4 B5 B6 B7 B8 B9 口袋 根据 所指向的 数，进行分配动作， 将其分配到相应的口 袋。和第一次不同， 这次根据右起第二位 数字（十位数字）进 分配。 2 52 1、 实现： Merging sort: 思想来源于合并两个已排序的顺序表。 e.g: 将下属两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。 0 1 2 3