常宝宝 北京大学计算机科学与技术系 chbb@pku.edu.cn 数据结构（七） 常宝宝 北京大学计算机科学与技术系 chbb@pku.edu.cn

内容提要 基本概念 插入排序（直接插入排序、希尔排序） 选择排序（简单选择排序、堆排序） 交换排序（快速排序、冒泡排序） 归并排序 基数排序

关键字 关键字是记录（数据元素）中的一个（或多个）字段。通常用作检索和排序记录的依据。 关键字通常可以进行比较操作。

什么是排序? 排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。 一般情况下，假设含n个记录（元素）的序列为 { R1, R2, …， Rn } 其相应的关键字序列为 { K1, K2, …，Kn } 且这些关键字相互之间可以进行比较。 确定1, 2, …, n的一种排列p1, p2, …, pn，使其相应的关键字满足如下的非递减关系： Kp1≤Kp2≤…≤Kpn 即将记录序列重新排列为 { Rp1, Rp2, …，Rpn } 这种操作称作排序。

排序方法的稳定性 待排序的记录中可能存在两个或两个以上的关键字相等的记录。假设Ki = Kj (1≤i≤n，1≤j≤n，i≠j)，且在排序前的序列中Ri领先于Rj(即i<j)。若排序方法可以保证在排序后的序列中Ri仍然领先于Rj，则称所用的排序方法是稳定的；反之，若排序方法可能使排序后的序列中Rj领先于Ri，则称所用的排序方法是不稳定的。

内排序和外排序 由于待排序的记录的数量不同，排序过程涉及的存储器可能不同。 若待排序的记录数量相对较少，则可将所有待排序记录存放在内存中完成排序，这种排序称为内排序。 若待排序的记录数量很大，不可能将所有待排序的记录放在内存中进行排序，排序过程中需要不断访问外存(如：磁盘、磁带等)，这中排序称做外排序。 目前我们只探讨内排序。

排序方法的分类 内部排序的方法很多，每一种方法都有各自的优缺点，不存在在任何情况下都最好的排序方法，在不同的环境下（记录的原始排列顺序），应使用不同的排序方法。 内排序的分类： （1）插入排序 （2）交换排序 （3）选择排序 （4）归并排序 （5）基数排序

排序方法的评价 排序过程中要进行的基本操作： （1） 关键字大小的比较 （2） 记录位置的移动 排序算法的性能可以通过基本操作的执行次数予以评价。

复杂记录和关键字的C++实现 关键字应能支持比较操作，需要定义关系运算符重载函数。 class Key { public: ... private: ... }; bool operator==(const Key&x, const Key&y); bool operator>(const Key&x, const Key&y); bool operator<(const Key&x, const Key&y); bool operator>=(const Key&x, const Key&y); bool operator<=(const Key&x, const Key&y); bool operator!=(const Key&x, const Key&y); class Record { public: operator Key(); private: Key k; ... }; 关键字应能支持比较操作，需要定义关系运算符重载函数。 记录类型提供到关键字类型的类型转换函数，因而对记录类型也可以比较大小，等同于按关键字进行比较。

具有排序功能的顺序线性表 template <typename Record, int max_list=100> //顺序存储的线性表 class List { public: enum error_code { success, range_error, overflow, underflow}; protected: int count; //线性表中元素个数 Record entry[max_list]; //线性表存储空间 public: //操作 List(); ... int size() const; bool empty() const; void clear(); void XXX_sort(); ... error_code remove(int i, Record& x); error_code insert(int i, const Record& x); void traverse( void (*visit)(Record&)); };

具有排序功能的链式线性表 template <typename Record> class List { public: enum error_code { success, range_error, overflow, underflow}; protected: struct node { Record entry; //数据域 node *next; //指针域 node():next(0) {} node(const Record &le, node* link= NULL):entry(le), next(link) {} }; int count; //线性表中元素个数 node *head; //链表头指针 node *set_position(int i) const; public: //操作 List(); ... void XXX_sort(); void traverse( void (*visit)(Record&)); };

直接插入排序 向一个有序表中插入一个记录

直接插入排序 首先将线性表中第1个记录看成一个有序表，然后从第2个记录起逐个进行插入，直到整个线性表有序。

直接插入排序（顺序表实现） 直接插入排序（顺序表实现） template <typename Record, int max_list > void List<Record, max_list>::insertion_sort() { int first_unsorted; int position; Record current; for(first_unsorted=1;first_unsorted<count;first_unsorted++) if (entry[first_unsorted]<entry[first_unsorted-1]) { position = first_unsorted; current = entry[first_unsorted]; do { entry[position] = entry[position-1]; position--; } while (position>0 && entry[position-1]>current); entry[position]=current; } }

直接插入排序（顺序表实现）

template <typename Record> void slist<Record>::insertion_sort() { node *first_unsorted, *last_sorted, *current, *trailing; if ( head!=NULL ) { last_sorted = head; while ( last_sorted->next != NULL ) { first_unsorted = last_sorted->next; if ( first_unsorted->entry < head->entry ) { last_sorted->next = first_unsorted->next; first_unsorted->next = head; head = first_unsorted; } else { trailing = head; current = trailing->next; while (first_unsorted->entry > current->entry) { trailing = current; current = trailing->next;} if ( first_unsorted == current) last_sorted= first_unsorted; else { last_sorted->next = first_unsorted->next; first_unsorted->next = current; trailing->next = first_unsorted;} } } } } 直接插入排序（单链表实现）

直接插入排序（单链表实现）

希尔排序 希尔排序又称缩小增量排序。 希尔排序是一种插入排序法。

希尔排序

希尔排序（顺序表实现） template <typename Record, int max_list > void List<Record, max_list>::shell_sort() { int increment, start; increment = count; do { increment = increment/3 + 1; for (start = 0; start < increment; start++) sort_interval(start, increment); } while (increment > 1); }

希尔排序（顺序表实现） template <typename Record, int max_list > void List<Record, max_list>::sort_interval(int start, int increment) { int first_unsorted; int position; Record current; for ( first_unsorted=start+increment; first_unsorted<count; first_unsorted+=increment ) if(entry[first_unsorted]<entry[first_unsorted-increment]) { position = first_unsorted; current = entry[first_unsorted]; do { entry[position] = entry[position-increment]; position-=increment; } while(position>start&&entry[position-increment]>current); entry[position]=current; } }

简单选择排序

简单选择排序（顺序表实现） template <typename Record, int max_list > void List<Record, max_list>::selection_sort() { for (int position = count-1; position > 0; position--) { int max = max_key(0, position); swap(max, position); } } zzx template <typename Record, int max_list > int List<Record, max_list>::max_key(int low, int high) { int largest, current; largest = low; for (current = low+1; current <= high; current++) if (entry[largest] < entry[current]) largest = current; return largest; }

简单选择排序（顺序表实现） template <typename Record, int max_list > void List<Record, max_list>::swap(int low, int high) { Record temp; temp = entry[low]; entry[low] = entry[high]; entry[high] = temp; }

堆排序 什么是堆？ n个记录的序列，其所对应的关键字的序列为｛k0, k1, k2, …, kn-1｝，若有如下关系成立时，则称该记录序列构成一个堆。 ki≥k2i+1且 ki≥k2i+2, 其中i=0, 1, …, 例如,下面的关键字序列构成一个堆。 96 83 27 38 11 9 y r p d f b k a c

堆排序 若把堆看作顺序存储的二叉树，则堆的含义表明二叉树中所有非终端结点的值均不小于其左右子结点的值。根结点对应堆中第0个元素（堆顶元素），且必为序列中的最大值。 堆排序的思路是首先将待排序记录组织成一个堆，将堆顶元素放入有序表中，然后将余下的记录再组织成堆，继续将堆顶元素放入有序表中，直到所有记录都进入有序表。

堆排序 实现堆排序需要解决两个问题： （1）如何由一个无序序列建成一个堆？build_heap() （2）如何在输出堆顶元素之后，调整剩余元素成为一个新堆？insert_heap()

堆排序（顺序表实现） template <typename Record, int max_list > void List<Record, max_list>::heap_sort() { Record current; int last_unsorted; build_heap( ); for(last_unsorted=count-1; last_unsorted>0;last_unsorted--){ current = entry[last_unsorted]; entry[last_unsorted] = entry[0]; insert_heap(current, 0, last_unsorted-1); } }

堆排序（顺序表实现） template <typename Record, int max_list > void List<Record, max_list>::insert_heap(const Record& current, int low, int high) { int large; large = 2*low+1; while (large <= high) { if (large<high && entry[large]<entry[large+1]) large++; if (current >= entry[large]) break; else { entry[low] = entry[large]; low = large; large = 2*low+1; } } entry[low] = current; }

堆排序（顺序表实现） template <typename Record, int max_list > void List<Record, max_list>::build_heap() { int low; for (low = count/2-1; low >= 0; low--) { Record current = entry[low]; insert_heap(current, low, count-1); } }

快速排序 分而治之 选择一个记录，并按照该记录将待排记录分割成两个独立的部分,其中一部分记录的关键字均小于所选择记录的关键字，另一部分记录的关键字均大于所选记录的关键字。所选记录通常称为枢轴或支点。 然后分别对这两部分记录继续进行排序，以达到整个序列有序。

快速排序（顺序表实现） template <typename Record, int max_list > void List<Record, max_list>::quick_sort() { recursive_quick_sort(0, count-1); } template <typename Record, int max_list > void List<Record, max_list>::recursive_quick_sort(int low, int high) { int pivot_position; if (low < high) { pivot_position = partition(low, high); recursive_quick_sort(low, pivot_position-1); recursive_quick_sort(pivot_position+1, high); } }

快速排序（顺序表实现） template <typename Record, int max_list > int List<Record, max_list>::partition(int low, int high) { Record pivot; int i, last_small; swap(low, (low+high)/2); pivot = entry[low]; last_small = low; for (i = low+1; i <= high; i++) if (entry[i] < pivot) { last_small = last_small+1; swap(last_small, i); } swap(low, last_small); return last_small; }

快速排序（顺序表实现）

小结