排序算法实现

以下是各种排序算法的C++实现，摘自《C++数据结构与程序设计》，总结起来写成博客来用于温习。

①插入排序 

时间复杂度：O(n^2)。

优点：稳定，快。

缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题。

数组版实现如下：

//数组版template <class Record>void Sortable_list<Record>::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 <class Record>void Sortable_list<Record>::insertion_sort() {	Node<Record>* 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;				}			}		}	}}以上两种版本的基本方法是一致的，仅有的真正的区别在于数组版本一逆序查找已排序的子表，而链式版本以表中位置的升序查找已排序的子表。
②选择排序 
时间复杂度：O(n^2)。
优点：移动数据的次数已知(n-1次)。
缺点：比较次数多。
//顺序实现template <class Record>void Sortable_list<Record>::selection_sort() {	for (int position = count-1; position > 0; position--) {		int max = max_key(0, position);		swap(max, position);	}}template <class Record>void Sortable_list<Record>::max_key(int low, int high) {	int largest, current;这种表中这种表中这种表中这种表中这种表中这种表中这种表中这种表中这种表中这种表中zhezhongbiaozhog	largest = low;	for (current = low+1; current <= high; current++) {		if (entry[largest] < entry[current]) largest = current;	}	return largest;}template <class Record>void Sortable_list<Record>::swap(int low, int high) {	Record temp;	temp = entry[low];	entry[low] = entry[high];	entry[high] = temp;}选择排序在每一趟都会至少将一个元素放在其最终位置上，从而使数据的移动最少。这个算法主要对大元素的顺序表有用，在这种表中移动元素往往代价太大。