Reference Book: 《Data Structures and Program Design in C++》
--------------------------------------------------------------------------------------------------------------------------------------------------- 1. Doubly_Linked_List 见文章《Doubly_Linked_List的代码实现》 2. Sortable_list #ifndef SORTABLE_LIST_H #define SORTABLE_LIST_H #include "Doubly_Linked_List.h" #include "Record.h" #define MAX_SIZE 128 template <class Key> class Sortable_list: public Doubly_Linked_List<Key> { public: //直接调用基类Doubly_Linked_List的初始化方法 // 插入排序 void insertion_sort(); // 选择排序 void selection_sort(); int max_key(int low, int high); void swap(int low, int high); // 希尔排序(不适用链式实现) void sort_interval(int start, int increment); void shell_sort(); // 归并排序 void merge_sort(); void recursive_merge_sort(Sortable_list<Key> &the_list); // 不用书中传入head指针的实现方式 Sortable_list<Key> divide_from(Sortable_list<Key> &the_list); void combine(Sortable_list<Key> &the_list, const Sortable_list<Key> &second_list); // 快速排序 void quick_sort(); void recursive_quick_sort(Sortable_list<Key> &the_list); Sortable_list<Key> partition(Sortable_list<Key> &the_list, Key pivot); void unite(Sortable_list<Key> &the_list, Sortable_list<Key> &second_list, Key pivot); // 堆排序 void heap_sort(); void build_heap(); void insert_heap(const Key &now, int low, int high); void insert_array(int position, const Key &data); void traverse_array(void (*visit)(Key &)); protected: private: Key entry[MAX_SIZE]; }; /************************************* * Insertion Sort * *************************************/ template <class Key> void Sortable_list<Key>::insertion_sort() /*Pre: Post: 从前向后遍历表, 将尚未排序的第一个键在已排序队列中找到合适的位置进行插入. */ { Node<Key> *first_unsorted, *last_sorted, *now, *trailing; if(Doubly_Linked_List<Key>::head != nullptr) // head是双链表类中的元素, 需要作用域符号 { last_sorted = Doubly_Linked_List<Key>::head; while(last_sorted->next != nullptr) { first_unsorted = last_sorted->next; // 插入到pos==0的位置 if(first_unsorted->entry <= Doubly_Linked_List<Key>::head->entry) { last_sorted->next = first_unsorted->next; if(first_unsorted->next != nullptr) // 当unsorted中至少有1个结点时 first_unsorted->next->back = last_sorted; Doubly_Linked_List<Key>::head->back = first_unsorted; first_unsorted->next = Doubly_Linked_List<Key>::head; first_unsorted->back = nullptr; Doubly_Linked_List<Key>::head = first_unsorted; } // 搜索正确的pos插入 else { trailing = Doubly_Linked_List<Key>::head; now = trailing->next; while(first_unsorted->entry > now->entry) { trailing = now; now = trailing->next; } if(first_unsorted==now) // 已经在正确的位置 last_sorted = first_unsorted; else { last_sorted->next = first_unsorted->next; first_unsorted->next->back = last_sorted; first_unsorted->next = now; now->back = first_unsorted; trailing->next = first_unsorted; first_unsorted->back = trailing; } } } } } /************************************* * Selection Sort * *************************************/ template <class Key> void Sortable_list<Key>::selection_sort() /*Pre: Post: */ { // pos从最后到1, 不用到0因为pos==1时已经比较过第一个键 for(int pos = Doubly_Linked_List<Key>::count-1; pos > 0; pos--) { int max = max_key(0, pos); swap(max, pos); } } template <class Key> int Sortable_list<Key>::max_key(int low, int high) /*Pre: Post: 遍历pos从low到high之间的所有键, 返回最大键的位置. */ { Key data, now_entry; Doubly_Linked_List<Key>::set_position(low); data = Doubly_Linked_List<Key>::current->entry; int now, pos = low; // 找到pos为low至high之间最大键的位置 for(now = low + 1; now <= high; now++) { Doubly_Linked_List<Key>::set_position(now); now_entry = Doubly_Linked_List<Key>::current->entry; if(data < now_entry) { data = now_entry; pos = now; } } return pos; } template <class Key> void Sortable_list<Key>::swap(int low, int high) /*Pre: Post: 若需要交换的pos相同者不进行操作; 否则通过insert和remove操作先将最大键插入到 pos==high的位置, 再删除对应结点, 再将要交换的键插入到pos==low的位置, 最后 remove该键注意该键在high+1的位置. */ { if(low==high)return; // 当前pos的键为最大键则不发生交换 Key data; Node<Key> *max, *pos; Doubly_Linked_List<Key>::set_position(low); max = Doubly_Linked_List<Key>::current; Doubly_Linked_List<Key>::set_position(high); pos = Doubly_Linked_List<Key>::current; // 利用insert和remove操作完成结点的交换 (*this).insert(high, max->entry); (*this).remove(low, data); (*this).insert(low, pos->entry); (*this).remove(high+1, data); } /********************************* * Shell Sort * *********************************/ template <class Key> void Sortable_list<Key>::sort_interval(int start, int increment) /*Pre: Post: */ { int first_unsorted; // position of first unsorted entry int position; // searches sorted part of list Key current; // holds the entry temporarily removed from list for (first_unsorted = start + increment; first_unsorted < Doubly_Linked_List<Key>::count; first_unsorted += increment ) if (entry[first_unsorted] < entry[first_unsorted - increment]) { position = first_unsorted; current = entry[first_unsorted]; // Pull unsorted entry out of the list. do { // Shift all entries until the proper position is found. entry[position] = entry[position - increment]; position -= increment; // position is empty. } while (position > start && entry[position - increment] > current); entry[position] = current; } } template <class Key> void Sortable_list<Key>::shell_sort() /*Pre: Post: */ { int increment, start; increment = Doubly_Linked_List<Key>::count; do { increment = increment/3+1; for(start = 0; start<increment; start++) sort_interval(start, increment); }while(increment > 1); } /********************************** * Merge Sort * **********************************/ template <class Key> void Sortable_list<Key>::merge_sort() /*Post: 对表中元素分组重新排列，最终得到一个升序序列. Uses: Doubly_Linked_List和recursive_merge_sort(). */ { recursive_merge_sort(*this); } template <class Key> void Sortable_list<Key>::recursive_merge_sort(Sortable_list<Key> &the_list) /*Post: 通过将the_list分为两个子表再递归调用recursive_merge_sort()并将其合并, 通过 修改the_list返回排序后的新表. Uses: */ { Sortable_list<Key> second_list; if(the_list.size() > 1) // 表中至少有两个键时进行归并排序 { second_list = divide_from(the_list); recursive_merge_sort(the_list); recursive_merge_sort(second_list); combine(the_list, second_list); } } template <class Key> Sortable_list<Key> Sortable_list<Key>::divide_from(Sortable_list<Key> &the_list) /*Post: 将the_list分割成两个list其中第一个list较长保存再the_list中, 另一个 返回为second_list. Uses: */ { int mid = (the_list.size()-1) / 2; // 中间元素(若偶数个元素则为左中)的pos值 int second_size = the_list.size() - (mid+1); Sortable_list<Key> second_list; for(int i = 0; i < second_size; i++) { Key data; the_list.remove(mid+1, data); // 始终删除的是pos为mid+1的键 second_list.insert(i, data); } return second_list; } template <class Key> void Sortable_list<Key>::combine(Sortable_list<Key> &the_list, const Sortable_list<Key> &second_list) /*Post: 将the_list和second_list中的键排序之后合并成新的list并返回. Uses: */ { Key data_the_list, data_second_list; Sortable_list<Key> temp_list; int pos_the_list = 0, pos_second_list = 0, pos_temp_list = 0; // the_list和second_list均非空时比较两者元素, 并按升序插入至temp_list while(pos_the_list < the_list.size() && pos_second_list < second_list.size()) { the_list.retrieve(pos_the_list, data_the_list); second_list.retrieve(pos_second_list, data_second_list); if(data_the_list <= data_second_list) { temp_list.insert(pos_temp_list, data_the_list); pos_the_list++; } else { temp_list.insert(pos_temp_list, data_second_list); pos_second_list++; } pos_temp_list++; } // 将仍有元素的表的剩余键按序插入temp_list while(pos_the_list < the_list.size()) { the_list.retrieve(pos_the_list, data_the_list); temp_list.insert(pos_temp_list, data_the_list); pos_the_list++; pos_temp_list++; } while(pos_second_list < second_list.size()) { second_list.retrieve(pos_second_list, data_second_list); temp_list.insert(pos_temp_list, data_second_list); pos_second_list++; pos_temp_list++; } the_list = temp_list; // 操作符=重载将temp_list赋值给the_list返回 } /********************************** * Quick Sort * **********************************/ template <class Key> void Sortable_list<Key>::quick_sort() /*Post: Uses: */ { recursive_quick_sort(*this); } template <class Key> void Sortable_list<Key>::recursive_quick_sort(Sortable_list<Key> &the_list) /*Post: 将the_list中的中间键作为pivot, 当the_list中的键的数目大于1时将其 按与键pivot的相对大小分为the_list和second_list两个子表. 然后分别执行 递归调用, 返回后将the_list, pivot, second_list进行合并. Uses: */ { // 中间元素(若偶数个元素则为左中)的pos值 int pivot_position = (the_list.size()-1) / 2; Key pivot; the_list.remove(pivot_position, pivot); Sortable_list<Key> second_list; if(the_list.size() > 1) { second_list = partition(the_list, pivot); recursive_quick_sort(the_list); recursive_quick_sort(second_list); unite(the_list, second_list, pivot); } else if(the_list.size()==1) { Key data; the_list.retrieve(0, data); if(data<pivot) the_list.insert(1, pivot); else the_list.insert(0, pivot); } else the_list.insert(0, pivot); } template <class Key> Sortable_list<Key> Sortable_list<Key>::partition(Sortable_list<Key> &the_list, Key pivot) /*Post: 将the_list中的键按与pivot的相对大小, 严格小于pivot的重新存入the_list, 其他键存入second_list并返回, 且保持原来键的相对位置不变. Uses: */ { Sortable_list<Key> second_list, temp_list; int i, pos_temp_list = 0, pos_second_list = 0; Key data; for(i = 0; i < the_list.size(); i++) { the_list.retrieve(i, data); if(data < pivot)temp_list.insert(pos_temp_list++, data); else second_list.insert(pos_second_list++, data); } the_list = temp_list; return second_list; } template <class Key> void Sortable_list<Key>::unite(Sortable_list<Key> &the_list, Sortable_list<Key> &second_list, Key pivot) /*Post: 将pivot和second_list中的键依序插入至the_list的最末端. Uses: */ { int i; int pos_the_list = the_list.size(); Key data; the_list.insert(pos_the_list++, pivot); // 插入pivot至the_list末 for(i = 0; i < second_list.size(); i++) { second_list.retrieve(i, data); the_list.insert(pos_the_list++, data); } } /******************************** * Heap Sort * ********************************/ template <class Key> void Sortable_list<Key>::heap_sort() /*Post: 先将顺序表构建成一个初始的大根堆, 再通过for循环, 每次将根元素移至未排序 部分的尾部, 并重新将未排序部分重新排列为一个大根堆. Uses: */ { Key now; int last_unsorted; build_heap(); // 构建初始堆 for(last_unsorted = Doubly_Linked_List<Key>::count-1; last_unsorted > 0; last_unsorted--) { now = entry[last_unsorted]; // 将堆的根上的键移至最后, 即进行键排序 entry[last_unsorted] = entry[0]; insert_heap(now, 0, last_unsorted - 1); // 重新排列堆 } } template <class Key> void Sortable_list<Key>::build_heap() /*Post: 将顺序表建成一个初始堆. Uses: */ { int low; // count/2-1即最后一个结点的父亲结点索引, 自下而上, 自右向左构建大根堆 for(low = Doubly_Linked_List<Key>::count/2-1; low >= 0; low--) { Key now = entry[low]; // insert丢弃low位置元素, 将low位置now用作插入 insert_heap(now, low, Doubly_Linked_List<Key>::count-1); } } template <class Key> void Sortable_list<Key>::insert_heap(const Key &now, int low, int high) /*Pre: 在索引low到high之间的键构成一个大根堆. 在索引low位置的键将被丢弃. Post: 键now将被插入至索引low到high之间, 并最终构成一个大根堆. Uses: */ { int large; large = 2*low+1; // low的左孩子结点 while(large <= high) { // 左孩子结点不是最后一个结点, 且左孩子结点小于右孩子结点 if(large<high && entry[large]< entry[large+1]) large++; // 已经是大根堆就跳出while循环 if(now >= entry[large]) break; else { entry[low] = entry[large]; low = large; large = 2*low+1; } } entry[low] = now; } template <class Key> void Sortable_list<Key>::insert_array(int position, const Key &data) /*Post: 用作顺序实现堆排序. Uses: */ { Doubly_Linked_List<Key>::count++; Doubly_Linked_List<Key>::current_position = position; Doubly_Linked_List<Key>::set_position(position); entry[position] = data; } template <class Key> void Sortable_list<Key>::traverse_array(void (*visit)(Key &)) /*Post: 对顺序表entry进行遍历, 并对其中的键执行visit的 Uses: */ { int position; for(position = 0; position < Doubly_Linked_List<Key>::count; position++) // 遍历列表的数组中所有元素并执行visit函数 (*visit)(entry[position]); } #endif // SORTABLE_LIST_H 3. main.cpp #include <iostream> #include "Sortable_list.h" using namespace std; void print(Key &x) { cout << x; } void test_insertion_sort() /*Post: 进行插入排序的测试. */ { Sortable_list<Key> the_list; for(int i = 0; i < 10; i++)the_list.insert(i, Key(10-i)); cout << "The list is:" << endl; the_list.traverse(print); cout << endl << "Use insertion_sort Method:" << endl; the_list.insertion_sort(); the_list.traverse(print); } void test_selection_sort() /*Post: 进行选择排序的测试. */ { Sortable_list<Key> the_list; for(int i = 0; i < 10; i++)the_list.insert(i, Key(10-i)); cout << "The list is:" << endl; the_list.traverse(print); cout << endl << "Use selection_sort Method:" << endl; the_list.selection_sort(); the_list.traverse(print); } void test_shell_sort() /*Post: 进行希尔排序的测试. */ { Sortable_list<Key> the_list; for(int i = 0; i < 10; i++)the_list.insert_array(i, Key(10-i)); cout << "The list is:" << endl; the_list.traverse_array(print); cout << endl << "Use shell_sort Method:" << endl; the_list.shell_sort(); the_list.traverse_array(print); } void test_merge_sort() /*Post: 进行归并排序的测试. */ { Sortable_list<Key> the_list; for(int i = 0; i < 10; i++)the_list.insert(i, Key(10-i)); cout << "The list is:" << endl; the_list.traverse(print); cout << endl << "Use merge_sort Method:" << endl; the_list.merge_sort(); the_list.traverse(print); } void test_quick_sort() /*Post: 进行快速排序的测试. */ { Sortable_list<Key> the_list; for(int i = 0; i < 10; i++)the_list.insert(i, Key(10-i)); cout << "The list is:" << endl; the_list.traverse(print); cout << endl << "Use quick_sort Method:" << endl; the_list.quick_sort(); the_list.traverse(print); } void test_heap_sort() /*Post: 进行堆排序的测试. */ { Sortable_list<Key> the_list; for(int i = 0; i < 10; i++)the_list.insert_array(i, Key(10-i)); cout << "The list is:" << endl; the_list.traverse_array(print); cout << endl << "Use heap_sort Method:" << endl; the_list.heap_sort(); the_list.traverse_array(print); } int main() { //test_insertion_sort(); //test_selection_sort(); //test_shell_sort(); //test_merge_sort(); //test_quick_sort(); //test_heap_sort(); return 0; }