排序算法实现(续)

③希尔排序

时间复杂度：n^1.25 ~ 1.6n^1.25。

优点：快，数据移动少。

缺点：不稳定，增量的选择无法确切知道，只能凭经验来取。

template <class Record>void Sortable_list<Record>::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);} ④归并排序
时间复杂度：O(nlgn)。
优点：稳定，快。
缺点：需要O(n)的辅助空间，空间复杂度高。
//链表template <class Record>void Sortable_list<Record>::merge_sort() {	recursive_merge_sort(head);}template <class Record>void Sortable_list<Record>::recursive_merge_sort(Node<Record>* &sub_list) {	if (sub_list != NULL && sub_list->next != NULL) {		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);	}}//将一个链表分成两半template <class Record>void Sortable_list<Record>::divide_from(Node<Record>* sub_list) {	Node<Record>* position,				* midpoint,				*second_half;	if ((midpoint = sub_list) == NULL) return NULL;	position = midpoint->next;	while (position != NULL) {		position = position->next;		if (position != NULL) {			midpoint = midpoint->next;			position = position->next;		}	}	second_half = midpoint->next;	midpoint->next = NULL;	return second_half;}//归并两个已排序的链表template <class Record>void Sortable_list<Record>::merge(Node<Record>* first, Node<Record>* second) {	Node<Record>* last_sorted;	Node<Record> combined;	last_sorted = &combined;	while (first != NULL && second != NULL) {		if (first->entry <= second->entry) {			last_sorted->next = first;			last_sorted = first;			first = first->next;		}		else {			last_sorted->next = second;			last_sorted = second;			second = second->next;		}	}	if (first == NULL) last_sorted->next = second;	else last_sorted->next = first;	return combined->next;}
⑤快速排序
时间复杂度：O(nlgn)。
优点：极快，数据移动少。
缺点：不稳定。
//快速排序 O(nlgn)template <class Record>void Sortable_list<Record>::quick_sort() {	recursive_quick_sort(0, count-1);}template <class Record>void Sortable_list<Record>::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 <class Record>void Sortable_list<Record>::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;}⑥堆排序
时间复杂度：O(nlgn)。
优点：空间复杂度小。
缺点：只适用于顺序表。
//堆排序 O(nlgn)//只适用于顺序表template <class Record>void Sortable_list<Record>::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 <class Record>void Sortable_list<Record>::insert_heap(const Record ¤t, 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 <class Record>void Sortable_list<Record>::build_heap() { //建立初始的堆	int low;	for (low = count/2-1; low >= 0; low--) {		Record current = entry[low];		insert_heap(current, low, count-1);	}}⑦冒泡排序
时间复杂度：O(n^2)。
优点：简单。
缺点：慢，每次只能移动相邻两个数据。
void bubble_sort(int[] unsorted) {	for (int i = 0; i < unsorted.Length; i++) {		for (int j = i; j < unsorted.Length; j++) {			if (unsorted[i] > unsorted[j]) {				int temp = unsorted[i];				unsorted[i] = unsorted[j];				unsorted[j] = temp;			}		}	}}