Data Structure Ch.10 Sort(2)

Presentation on theme: "Data Structure Ch.10 Sort(2)"— Presentation transcript:

1 Data Structure Ch.10 Sort(2)
Dr. He Emil Huang School of Computer Science and Technology Soochow University 苏州大学计算机科学与技术学院网络工程系

2 选择排序 (简单选择排序、堆排序)

3 §10.4 选择排序 §10.4.1 直接选择排序(简单选择) 基本思想：
基本思想：每一趟从待排序的记录中选出最小(或最大)key的记录(简称最小元)，放在已排好序的子区间最后 § 直接选择排序(简单选择) 基本思想： 第1趟，无序区为R[1..n]，选最小者放在R[1]，无序区变为[2..n]. 第i趟，有序区为R[1..i-1]，无序区为R[i..n] 显然R[1..i-1].keys≤R[i..n].keys 选无序区中最小者R[k]，交换R[i]和R[k]后使R[1..i].keys ≤R[i+1..n].keys //有序区长度加1，无序区长度减1 第n-1趟之后，R[1..n-1].keys ≤R[n].keys，结束 3 3

4 §10.4 Selection Sort Basic Idea：Repeatedly find the next largest (or smallest) element in the array and move it to its final position. § Direct Selection Sort Algorithm： In the first round, where the unsorted subarray is R[1..n]，find the smallest element and exchange it with R[1], then the unsorted subarray becomes R[2..n]. In the i-th round, the sorted subarray is R[1..i-1], and the unsorted subarray is [i..n]. Then find the smallest element in the unsorted subarray and exchange it with R[i]. After that, the sorted subarray extended to R[1..i], and the unsorted subarray reduced to R[i+1..n]. In the (n-1)-th round, the selection sort is terminated, and the list is inorder. 4 4

5 §10.4 Selection Sort 我们的算法是每次选最小元，Kruse教材每次选最大元 5 5

6 §10.4 Selection Sort 6 6

7 § 10.4.1 Selection Sort 7 算法 void SelectSort (SeqList R){ int i, j, k;
for (i=1; i<n; i++){ //外循环，第i趟排序，1≤i ≤n-1 k = i; //用于存放某次循环的最大或最小元下标 for (j=i+1; j<=n; j++) //在当前无序区R[i..n]中选key最小的记录R[k] if (R[j].key<R[k].key) k=j; if (k!=i) R[i]↔R[k]; //可用R[0]做交换单元 } 7 7

8 SELECTION SORT P331 Kruse book
template <class Record> void Sortable_list<Record> :: selection_sort( ) /* Post: The entries of the Sortable_list have been rearranged so that the keys in all the entries are sorted into non_decreasing order. Uses: max_key ,swap . */ { for (int position = count - 1; position > 0; position--) { int max = max_ key(0, position); //if (max!=position) swap(max, position); }

9 SELECTION SORT Find maximum key: template <class Record>
int Sortable_list<Record> :: max_key(int low, int high) /* Pre: low and high are valid positions in the Sortable_list and low <= high . Post: The position of the entry between low and high with the largest key is returned. Uses: The class Record . The contiguous List implementation of Chapter 6.*/ { int largest, current; largest = low; for (current = low +1; current <= high; current++) if (entry[largest] < entry[current]) largest = current; return largest; }

10 SELECTION SORT Swap entries template <class Record>
void Sortable_list<Record> :: swap(int low, int high) /* Pre: low and high are valid positions in the Sortable_list . Post: The entry at position low is swapped with the entry at position high . Uses: The contiguous List implementation of Chapter 6. */ { Record temp; temp = entry[low]; entry[low] = entry[high]; entry[high] = temp; }

11 § 10.4.1 直接选择排序（简单选择） 时间 比较： 无论文件状态为何，第i趟排序中需比较n-i次（内循环次数） //Cmax=Cmin
移动： 状态正序：Mmin=0 状态逆序：每趟交换1次，Mmax=3(n-1) 就地，不稳定，检验反例[2, 2, 1] O(n),较少 11 11

12 § 10.4.1 Direct Selection Sort
Time Complexity Comparisons： No matter how the elements in the original list is distributed, the i-th round of selection sort takes n-1 times of comparisons, we could calculate the total times of comparisons: //Cmax=Cmin Exchange： Best case (in order)：Mmin=0 Worst case (in reverse order)：Mmax= (n-1) In place，Unstable O(n) 12 12

13 SELECTION SORT 选择排序的效率与初始状态无关。比较次数为n（n-1）/2，移动次数为3（n-1）。
Analysis and comparison 选择排序的效率与初始状态无关。比较次数为n（n-1）/2，移动次数为3（n-1）。 插入排序的效率与初始状态有关，最好情况是当原始数据基本有序时，(n-1次比较，0次移动）。 由于减少了移动次数，当记录元素较大时，选择排序比插入排序更为合适。而记录元素较小，移动花费时间不多时，插入排序由于比较次数少，会更好。 选择排序适用于顺序结构。

14 § 10.4.2 堆排序（Floyd &Williams）
直接选择的比较次数多是因为后一趟未利用前一趟的比较结构，树形选择可克服此缺点，但它耗费的空间大，故实用的树形选择是堆排序。 思想 将R[1..n]看作是1棵完全二叉树的顺序存储结构，利用完全二叉树的双亲和孩子之关系，在当前无序区里选择最小（大）元扩充至有序区。 二叉堆（快速选择最大/小元） n个keys序列K1, K2, …，Kn称为堆，当且仅当满足如下性质（堆性质，堆序）： （1） 或 （2） 这里， 。即i结点不是叶子(存在孩子)

15 § 10.4.2 堆排序 堆性质 将R[1..n]看作是完全二叉树的顺序存储结构时，堆性质实质上是满足如下性质的完全二叉树：
树中任一非叶结点的key均不大/小于其左右孩子(若存在)结点的key。即：从根到任一叶子的路径上的结点序列是一个有序序列，堆中任一子树仍是堆。它适合查找吗? 70 30 25 56 15 10 堆顶 10 15 25 30 56 70 堆顶 小根堆(顶) 大根堆(顶)

16 § 10.4.2 Heapsort (Floyd &Williams)
Min-heap Property Max-heap Property

17 § 10.4.2 Heapsort Heap Property
If R[1..n] is viewed as an array which stores a complete binary tree, the heap property is a complete binary tree that satisfies the following property: All nodes are either [greater than or equal to] or [less than or equal to] each of its children. If the parent nodes are greater than or equal to their children, the heap is called Max-heap, if the parent nodes are less than or equal to their children, the heap is called Min-heap. In another word, any path from root to the leaf node is in order, and any subtree of the heap is also a heap. 70 30 25 56 15 10 Heap Root 10 15 25 30 56 70 Heap Root Min-heap Max-heap

18 § Heapsort

19 § 10.4.2 堆排序 算法思想 1、初始化 将R[1..n]建成大根堆，即初始无序区。 2、排序
交换：设当前无序区是大根堆R[1..i]，交换其中的首尾记录，即最大元R[1]（堆顶）交换到无序区尾部（有序区头部），使有序区在R的尾部逐渐扩大： R[1..i-1].keys≤R[i..n].keys //前者为无序区，后者为有序区 显然，i＝n,n-1,…,2，即n-1趟排序即可完成。 调整：将新无序区R[1..i-1]调整为堆。注意：只有R[1]可能违反堆性质。

20 § Heapsort Algorithm 1、Initialization Build a heap from the input data R[1..n], that is the unsorted block. 2、Sorting Swap：Assume that R[1..i] is the max-heap，since the largest element is stored at the root of the max-heap, i.e. R[1], and then replace it with the last item of the heap, i.e. R[i] followed by reducing the size of heap by 1. After that, R[1..i-1].keys≤R[i..n].keys Note that, the former is the unsorted block, the latter is the sorted block. The algorithm takes n-1 iterations to assign each element to its correct position. Maintaining：Maintaining the heap property of the unsorted block R[1..i-1] after swap by sifting the new first element to its appropriate index in the heap.

21 § 10.4.2 Heapsort 算法实现 void HeapSort( SeqList R ) { int i;
BuildHeap( R ); //将R[1..n]建成初始堆 for ( i=n; i>1; i-- ) { //进行n-1趟堆排序，当前无序区为R[1..i] R[1] R[i]; //无序区首尾记录交换，R[0]做暂存单元 Heapify( R,1,i-1 ); //将R[1..i-1]重新调整为堆 } 如何调整堆和构造初始堆？

22 § 堆排序 调整（重建）堆 设调整区间为R[low..high]，因为只有根R[low]违反堆序，它的两子树（若存在，则根为R[2low]，R[2low+1]）均是堆。 无须调整 若R[low].key不小于两孩子的Keys，则R[low]不违反堆序 必须调整 将R[low]和它的两孩子中较大者交换： 设R[large].key=max{ R[2low].key, R[2low+1].key } 令R[low] R[large] 交换后R[large]可能违反堆序，重复上述过程，直至被调整的结点已满足堆序，或该结点已是叶子。 20 10 56 25 30 15 56 10 20 25 30 15 56 10 25 20 30 15

23 R[low] R[large] =max{ R[2low].key, R[2low+1].key }
§ Heapsort Heapify Assume that the max-heap to be manipulated is stored in R[low..high] and rooted at R[low]. Note that, after the swap operation, the children of R[low] are still heaps, but R[low] itself may violate the heap property. Satisfy heap property: If R[low].key is no less than the keys of its children, the heap property is still satisfied. Violate heap property: Exchange the greatest child with the root： R[low] R[large] =max{ R[2low].key, R[2low+1].key } Since R[large] may violate the heap property after the swap, the procedure continues recursively down the tree until the swapped node satisfies the heap property or it is a leaf node. 20 10 56 25 30 15 56 10 20 25 30 15 56 10 25 20 30 15

24 § 10.4.2 Heapsort 调整堆算法 void Heapify( SeqList R, int low, int high ) {
int large; //只有R[low]可能违反堆序 RecType temp=R[low]; for ( large=2*low; large<=high; large*=2 ) { //R[low]是当前调整结点，若large>high，则R[low]是叶子，结束； //否则，先令large指向R[low]的左孩子 if (large<high && R[large].key<R[large+1].key ) large++; //若R[large]有右兄弟，且右兄弟大，则令large指向右兄弟 if ( temp.key>=R[large].key ) break; //满足堆序 R[low]=R[large]; //交换，小的筛下 low=large; //令low指向新的调整结点 } R[low]=temp; //将被调整结点放到最终的位置

25 § 10.4.2 堆排序 构造初始堆算法 void BuildHeap( SeqList R ) { int i;
将R[1..n]建成堆，须将其每个结点为根的子树均调整为堆。对叶子(i> )无须调整，只要依次将以序号为 , , … , 2, 1的结点为根的子树均调整为堆即可。按此次序调整每个结点时，其左右子树均已是堆 void BuildHeap( SeqList R ) { int i; for ( i=n/2; i>0; i-- ) Heapify( R, i, n); //将R[i..n] 调整为堆 } 时间：最坏及平均皆为O(nlgn) (2nlgn+O(n)) 特点：就地，不稳定

26 § Heapsort

27 § Heapsort

28 § 10.4.2 Heapsort-Main function(C++ Version)
Main function for heapsort template <class Record> void Sortable_ list<Record> :: heap_ sort( ) { Record current; // temporary storage for moving entries int last_ unsorted; build_ heap( ); // First phase: Turn the list into a heap. for (last_ unsorted = count - 1; last_ unsorted > 0;last_ unsorted--) { current = entry[last_unsorted]; // Extract last entry from list. entry[last _ unsorted] = entry[0]; // Move top of heap to the end Insert_ heap(current, 0, last _unsorted - 1); // Restore the heap }

29 § 10.4.2 Heapsort-Insertion(C++ Version)
Insertion into a heap template <class Record> void Sortable_ list<Record> :: insert_ heap(const Record &current, int low, int high) { int large; // position of child of entry[low] with the larger key large = 2 * low + 1; // large is now the left child of low. while (large <= high) { if (large < high && entry[large] < entry[large +1]) // large is now the child of low with the largest key. large++; if (current >= entry[large]) // current belongs in position low. break;

30 § 10.4.2 Heapsort-Insertion(C++ Version)
else { // Promote entry[large] and move down the tree. entry[low] = entry[large]; low = large; large = 2 * low +1; } entry[low] = current;

31 Building the initial heap
template <class Record> void Sortable_ list<Record> :: build_ heap( ) /* Post: The entries of the Sortable_list have been rearranged so that it becomes a heap. Uses: The contiguous List implementation of Chapter 6, and insert heap . */ { int low; //All entries beyond the position low form a heap. for (low = count/2 - 1; low >= 0; low--) { Record current = entry[low]; insert_ heap(current, low, count - 1); }

32 § Heapsort

33 大根堆排序示例 91 16 88 23 42 24 05 13 【 】 13 16 88 23 42 24 05 91 【 】91 第一趟排序:交换后 初始堆R[1..8] 88 16 24 23 42 13 05 91 【 】91 05 24 42 23 13 16 88 1st趟:重建堆R[1..7]后 91 第二趟排序:交换后 【 】88 91

34 归并排序 (顺序实现、链表上的实现)

35 § Mergesort Basic Idea： We chop the list into two sublists of size as nearly equal as possible and then sort them separately. Afterward, we carefully merge the two sorted sublists into a single sorted list.

36 § Mergesort 初始关键字 [49] [38] [65] [97] [76] [13] [27] 第一趟归并后 [ ] [ ] [ ] [ 27 ] 第二趟归并后 [ ] [ ] 第三趟归并后 [ ]

37 § 10.5 Mergesort Two-way Mergesort：
void Merge( SeqList R, int low, int m, int high ) { //将2个有序表R[low..m]和R[m+1..high]归并为1个有序表R[low..high] int i=low, j=m+1, p=0; //i,j指向输入子表头，p指向输出子表 RecType *R1=(RecType *)malloc(high-low+1)*sizeof(RecType));//输出 if ( !R1 )Error( “存储分配失败” ) while( i<=m && j<=high ) //2子表非空时，取其头上较小者输出到R1[p]上 R1[p++]=( R[i].key<=R[j].key ) ? R[ i++]: R[ j++] ; while ( i<=m ) //第1子表非空，将剩余记录copy到R1中 R1[p++]=R[ i++ ]; while ( j<=high ) //第2子表非空，将剩余记录copy到R1中 R1[p++]=R[ j++ ]; R=R1; //将R1copy回R，R[low..high] R1[0..high-low] }

38 § 10.5 归并排序 排序算法 自底向上：见Fig10.13 自上而下：分治法设计 (1)分解：将当前区间一分为二，分裂点mid＝
§ 归并排序 排序算法 自底向上：见Fig10.13 自上而下：分治法设计 (1)分解：将当前区间一分为二，分裂点mid＝ (2)求解：递归地对2个子表R[low..mid]和R[mid+1..high]进行归并排序，出口是当前区间长度为1。 (3)组合：将上述两有序的子表归并成1个有序表R[low..high] void MergeSort( SeqList R, int low, int high ) { int mid; if ( low<high ){ //区间长度>1 mid=( low+high )/2; //分解 MergeSort( R, low, mid ); //解子问题1，结束时R[low..mid]有序 MergeSort( R, mid+1, high ); //解子问题2，结束时R[mid+1..high]有序 Merge( R, low, mid, high ); //组合 }//endif }

39 Mergesort for Linked Lists 链表的归并排序
Interface method template <class Record> void Sortable_list<Record> :: merge_sort( ) { /* Post: The entries of the sortable_list have been rearranged so that their keys are sorted into non_decreasing order. Uses: Linked List implementation of Chapter 6 and recursive merge sort . */ recursive_merge_sort(head); }

40 Mergesort for Linked Lists
Recursive function template <class Record> void Sortable_list<Record> :: recursive_merge_sort(Node<Record> * &sub_list){ if (sub_list != NULL && sub_list->next != NULL) {//more than one Node<Record> *second_half = divide_from(sub_list); recursive_merge_sort(sub_ list); recursive_merge_sort(second_half); sub_list = merge(sub_list, second_half); }

41 Mergesort for Linked Lists
Divide Linked List in Half template <class Record> Node<Record> *Sortable_list<Record> :: divide_from(Node<Record> *sub_list){ Node<Record> *position, // traverses the entire list *midpoint, // moves at half speed of position to midpoint *second_ half; if ((midpoint = sub_list) == NULL) return NULL; // List is empty position = midpoint->next; while (position != NULL) { // Move position twice for midpoint 's one move position = position->next; if (position != NULL) { midpoint = midpoint->next; }

42 second_ half = midpoint->next;
midpoint->next = NULL; return second_half; }

43 § 10.5 Mergesort for Linked Lists

44 Mergesort for Linked Lists
Merge Function template <class Record> Node<Record> *Sortable_list<Record> :: merge(Node<Record> *first, Node<Record> *second) { Node<Record> *last_sorted; // points to the last node of sorted list Node<Record> combined; // dummy first node, points to merged list Last_sorted = &combined;

45 while (first != NULL && second != NULL) {
// Attach node with smaller key if (first->entry <= second->entry) { last_sorted->next = first; last_sorted = first; first = first->next; // Advance to the next unmerged node. } else { last_sorted->next = second; last_ sorted = second; second = second->next; } // After one list ends, attach the remainder of the other. if (first == NULL) else return combined.next;

46 DIVIDE-AND-CONQUER SORTING
Mergesort（归并排序）

47 § Mergesort

48 树的高度体现了最坏情况下的比较次数 平均查找次数=树的外部路径长度/叶结点数 叶结点数至少为n！ 根据lemma 7.5,Theorem 7.6 the height of the tree is at least ,外部路径长度至少n! 最坏情况， 平均情况：lgn! lgn! ≈ nlgn 以关键字比较为基础的排序，关键字的比较次数的数量级起码为O(nlgn)

49 分配排序 (基数排序)

50 § 10.6 分配排序 基于比较的排序时间下界: 分配排序正是如此，它通过“分配”和“收集”过程实现排序，时间为O(n)。
§ 分配排序 基于比较的排序时间下界: 由Stirling公式知：lgn!＝nlgn-1.44n+O(lgn) 要突破此界，就不能通过keys的比较。 分配排序正是如此，它通过“分配”和“收集”过程实现排序，时间为O(n)。 § 箱排序 基本思想 分配：扫描R[0..n-1],将key等于k的记录全装入kth箱子里 收集：按序号将各非空箱子首尾连接起来 多趟：每个关键字1趟，例如:扑克牌 时间： 分配：O(n)； 收集：设箱子数为m(与key相关)，时间为O(m)或O(m+n) 总计：O(m+n)=O(n) if m=O(n)

51 §10.6.2 基数排序 基本思想 例子 将2位整数看作2个keys，先对个位，后对十位做箱排序。因此，无须100个箱子，只要10个箱子。
例如，若m＝O(n2), 则时间和空间均为O(n2)。 基数排序是通过分析key的构成，用多趟箱排序实现的。 例子 设n＝10，ki∈[0..99], 1≤i ≤10 输入:（36,5,10,16,98,95,47,32,36,48） 将2位整数看作2个keys，先对个位，后对十位做箱排序。因此，无须100个箱子，只要10个箱子。

52 §10.6.2 基数排序 （36,5,10,16,98,95,47,32,36,48） 第1趟箱排序 第2趟箱排序 分配： 0 10
0 10 1 2 32 3 4 5 5,95 6 36,16,36 7 47 8 98,48 9 收集： 10,32,5,95,36,16,36,47,98,48 （36,5,10,16,98,95,47,32,36,48） 第2趟箱排序 0 05 1 10,16 2 3 32,36,36 4 47,48 5 6 7 8 9 95,98 05,10,16,32,36,36,47,48,95,98 各趟排序前要求清空箱子，分配和收集须按FIFO进行，箱子用链队列表示。 除第1趟外，其余各趟一定要是稳定的排序，否则结果可能有错。 m不再在数量级上大于O(n)，故上述排序时间是O(n)

53 §10.6.2 基数排序 一般情况 排序算法 设任一记录R[i]的key均由d个分量 Ki0 , Ki1 , …, Kid-1 构成
多关键字文件：d个分量皆为独立的key 单关键字文件：每个分量是key中的1位，只讨论这种情况。 设每位取值范围相同： C0≤Kj≤Crd-1 (0≤j﹤d) 这里，rd称为基数，d为key的位数。 若key为十进制整数，按位分解后rd＝10，C0＝0，C9＝9 排序算法 从低位到高位依次对Kj（j＝d-1,d-2,…,0）进行d趟箱排序，所需的箱子数为基rd。 #defin KeySize 4 //设d＝4 #define Radix 10 //基rd为10 typedef RecType DataType; //各箱子用链队列表示，其中的结点数据类型改为与本章的记录类型一致

54 §10.6.2 基数排序 void RadixSort( SeqList R ){
//对R[0..n-1]做基数排序，设keys为非负整数， //且位数不超过KeySize LinkQueue B[Radix]; //10个箱子 int i； for ( i=0; i<Radix; i++ ) //初始化 InitQueue(&B[i]); //清空箱子 for( i=KeySize-1; i>=0; i-- ) { //对位i箱排序，从低位到高位进行d趟箱排序 Distribute( R,B,i ); //分配 Collect( R,B ); //收集 }

55 §10.6.2 基数排序 void Distribute( SeqList R, LinkQueue B[ ], int j ){
int i，k，t； //按关键字jth分量分配，进入此过程时各箱子为空 j=KeySize - j; //将 j 换算为从个位起算，个位是第1位 for ( i=0; i<n; i++ ) { //扫描R，装箱 k=R[i].key; for( t=1; t<j; t-- ) k=k/10; //去掉key的后j-1位 k=k%10; //取key的第j位数字k EnQueue( &B[k],R[i] ); //将R[i]装入箱子B[k] } void Collect( SeqList R, LinkQueue B[ ] ){ int i=0, j; //依次连接各非空箱子，完成后使各箱子变空 for ( j=0; j<Radix; j++ ) //将jth箱子的内容依FIFO序收集到R中 while ( !QueueEmpty (&B[ j ]) ) //若是链队列，只需首尾链接 R[i++]=DeQueue( &B[ j ]);

56 §10.6.2 基数排序 链式基数排序：文件R不是以向量形式，而是以单链表形式给出。 时间：线性阶 箱子初始化：O(rd)
分配时间：O(n)，不计求第j位数字的时间 收集收集：O(n+rd)，链式为O(rd) d趟总时间：O( d(2n+rd) )，链式为O( d(n+rd) ) T(n)=O(n) if d=O(1) and rd=O(1) ～ O(n) 设key是十进制整数，d是常数吗？ 若n个keys的取值范围是0 ～nk，(常数k>1)，则key的位数是： d＝log10nk＝klog10n＝O(klgn) 因此，基数排序的时间是O(nlgn)。但是可将其改为n进制表示： rd＝n， d＝lognnk＝k，T(n)＝O( k(n+n) )=O(n) 辅助空间：O(n+rd) 对key的要求： 稳定排序：要求第1趟稳定，其余各趟必须稳定。

57 §10.6.2 基数排序 链式基数排序：文件R不是以向量形式，而是以单链表形式给出。 时间：线性阶 箱子初始化：O(rd)
分配时间：O(n)，不计求第j位数字的时间 收集收集：O(n+rd)，链式为O(rd) d趟总时间：O( d(2n+rd) )，链式为O( d(n+rd) ) T(n)=O(n) if d=O(1) and rd=O(1) ～ O(n) 设key是十进制整数，d是常数吗？ 若n个keys的取值范围是0 ～nk，(常数k>1)，则key的位数是： d＝log10nk＝klog10n＝O(klgn) 因此，基数排序的时间是O(nlgn)。但是可将其改为n进制表示： rd＝n， d＝lognnk＝k，T(n)＝O( k(n+n) )=O(n) 辅助空间：O(n+rd) 对key的要求： 稳定排序：要求第1趟稳定，其余各趟必须稳定。

58 § Distribution Sort

59 §10.6.2 Radix Sort Basic Idea Example
When the range of elements is large, the bucket sort will loss its efficiency both in time and space. The idea of radix sort is to do digit by digit sort starting from the less significant digit to the most significant digit using the bucket sort or counting sort as a subroutine to sort. Example n＝10, ki∈[0..99], 1≤i ≤10 Input:(36,5,10,16,98,95,47,32,36,48) Sorting by least significant digit (1s place) gives: (10,32,5,95,36,16,36,47,98,48) Sorting by the next digit (10s place) gives: (05,10,16,32,36,36,47,48,95,98) Since a digit ranges from 0 to 9, that requires less buckets to perform bucket sort on individual digit contrasted with directly performing bucket sorting.

60 §10.6.2 Radix Sort (36,5,10,16,98,95,47,32,36,48) 1st pass 2nd pass
Scatter： 0 10 1 2 32 3 4 5 5,95 6 36,16,36 7 47 8 98,48 9 Gather： 10,32,5,95,36,16,36,47,98,48 (36,5,10,16,98,95,47,32,36,48) 2nd pass 0 05 1 10,16 2 3 32,36,36 4 47,48 5 6 7 8 9 95,98 05,10,16,32,36,36,47,48,95,98 The buckets should be cleared before each round of sorting, and the elements should be scattered and gathered in FIFO manner. It is preferred that the bucket is implemented using linked list. The sort algorithm of each pass should be stable if it starts from LSD.

61 § Radix Sort

62 §10.6.2 Radix Sort(C++ Version)
Definition template <class Records> class Sortable_list: public List<Record>{ public: void radix_sort(); private: void rethread(Queue queues[]); }; class Record{ char key_letter(int position) const; Record(); operator Keu()const;

63 §10.6.2 Radix Sort(C++ Version)
Sorting Method const int max_chars=28; template <class Record> void Sortable_list<Record>::radix_sort() { Record data; Queue queues[max_chars]; for(int position=key_size-1;position>=0;position--){ while(remove(0,data)==success){ int queue_number=alphabetic_order(data.key_letter(position)); queues[queue_number].append(data); } rethread(queues);

64 §10.6.2 Radix Sort(C++ Version)
Selecting & Connecting Queues int alphabetic_order(char c) { if(c==' ') return 0; if('a'<=c && c<='z') return c-'a'+1; if('A' <=c && c<= 'Z') return c-'A'+1; return 27; } template <class Record> void Sortable_list<record>::rethread(Queue queues[]) Redord data; for(int i=0;i<max_chars;i++) while(!queues[i].empty()){ queues[i].retrieve(data); insert(size(),data); queues[i].serve();

65 § Radix Sort Linked Radix Sort：The records are stored in linked list. Time Complexity：Linear Initialization of buckets：O(rd) Scatter：O(n) Gather：O(n+rd) for array, O(rd) for linked list Total Time：O( d(2n+rd) ) for array, O( d(n+rd) ) for linked list T(n)=O(n) if d=O(1) and rd=O(1) ～ O(n) If key are decimal integers, is d a constant? Assume that the keys range from 0 to nk, (k is a constant greater than 1), the # of digits of the key is ： d＝log10nk＝klog10n＝O(klgn) The time complexity is O(nlgn). We could improve the performance by transforming radix from 10 to n： rd＝n， d＝lognnk＝k，T(n)＝O( k(n+n) )=O(n) Space Complexity：O(n+rd) Require fixed size keys and some standard ways of breaking the keys into pieces. Stable, not in place.

66 §10.7 各种排序方法的比较和选择 选择因素：实例规模，记录大小，key的结构及初始状态，对稳定性的要求，存储结构，时间和辅助空间的要求，语言工具(指针)。 比较 n 直接插入 直接选择 冒泡排序 堆排序 快速排序 随 4000 8000 10000 15000 机 20000 增 20000 减 20000 5.67 23.15 35.43 80.23 143.67 0.05 286.92 17.30 29.43 46.02 103.00 185.05 185.78 199.00 15.78 64.03 99.10 223.28 399.47 0.03 584.67 0.13 0.28 0.35 0.58 0.77 0.75 0.80 0.07 0.17 0.22 0.33 0.47 0.23 说明 直接选择无论k和i是否相等，均交换；快排用中间元做划分元。