[数据结构]九大基础排序算法总结_entry pivot

九大基础排序算法小结

一直想做份总结，总是抽不出时间，趁着周末闲着直接用了一整天做一份，一些内容参考了网上的一些博主的总结，还有网络上的一些图片。

好了，接下来就看看内容吧！

排序算法：

注：Radix Sort中n=数字个数; r=分配后链表的个数;d=数字或字符串的位数.

1.插入排序（Insertion Sort）

1）算法描述：

 

2）适用情况分析：

 

3）参考代码：

顺序版本↓：

template<class List_entry>
void Sortable_List<List_entry>::insertion_sort()
{
	List_entry current;
	if (count == 0)return;
	for (int first_unsorted = 1; first_unsorted < count; first_unsorted++) {
		if (entry[first_unsorted] >= entry[first_unsorted - 1])continue;
		current = entry[first_unsorted];
		int position = first_unsorted;
		do {
			entry[position] = entry[position - 1];
			position--;
		} while (position > 0 && entry[position - 1] > current);
		entry[position] = current;
	}
}

链式版本↓：

template<class List_entry>
void Sortable_list<List_entry>::insertion_sort()
{
	Node<List_entry> *first_unsorted, *last_sorted, *current, *previous;
	if (head == NULL)return;
	last_sorted = head;
	while (last_sorted->next){
		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 {
			previous = head;
			current = previous->next;
			while (current->entry < first_unsorted->entry) {
				previous = current;
				current = current->next;
			}
			if (current == first_unsorted)last_sorted = first_unsorted;
			else {
				last_sorted->next = first_unsorted->next;
				first_unsorted->next = current;
				previous->next = first_unsorted;
			}
		}
	}
}

2.选择排序（selection Sort）

1）算法描述：

 

2）适用情况分析：

 

3）参考代码：

template<class List_entry>
void Sortable_List<List_entry>::selection_sort()
{
	for (int i = 0; i < count - 1; i++) {
		int min = min_key(i, count - 1);
		swap(min, i);
	}
}
 
template<class List_entry>
int Sortable_List<List_entry>::min_key(int low, int high)
{
	int min = low;
	for (int i = low + 1; i <= high; i++) {
		if (entry[min] > entry[i])min = i;
	}
	return min;
}
 
template<class List_entry>
void Sortable_List<List_entry>::swap(int low, int high)
{
	List_entry tmp = entry[low];
	entry[low] = entry[high];
	entry[high] = tmp;
}

 

3. 冒泡排序（Bubble Sort）

1）算法描述：

 

2）适用情况分析：

 

3）参考代码：

 

template<class List_entry>
void Sortable_List<List_entry>::bubble_sort()
{
	for(int i=0;i<count;i++)
		for (int j = 0 ; j < count-i-1; j++) 
			if (entry[j] > entry[j+1]) {
				List_entry tmp = entry[j];
				entry[j] = entry[j + 1];
				entry[j + 1] = tmp;
			}
}

 

4.希尔排序（Shell Sort）---插入排序的优化

1）算法描述：

 

2）适用情况分析：

 

3）参考代码：

template<class List_entry>
void Sortable_List<List_entry>::shell_sort()
{
	int increment = count;
	do {
		increment = increment / 3 + 1;
		for (int start = 0; start < increment; start++) 
			sort_interval(start, increment);
	} while (increment > 1);
}
 
template<class List_entry>
void Sortable_List<List_entry>::sort_interval(int start, int increment)
{
	List_entry current;
	int position;
	for (int first_unsorted = start + increment; first_unsorted < count;
		first_unsorted += increment) {
		if (entry[first_unsorted] < entry[first_unsorted - increment]) {
			position = first_unsorted;
			current = entry[position];
			do {
				entry[position] = entry[position - increment];
				position -= increment;
			} while (position > start&&entry[position - increment] > current);
			entry[position] = current;
		}
	}
}

在网络上看到了简化版本的shell sort，也可作参考：

void shellsort3(int a[], int n)
{
	int i, j, gap;
 
	for (gap = n / 2; gap > 0; gap /= 2)
		for (i = gap; i < n; i++)
			for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap)
				swap(a[j], a[j + gap]);
}

5.快速排序（Quick Sort）

1）算法描述：

 

2）适用情况分析：

 

3）参考代码：

template<class List_entry>
void Sortable_List<List_entry>::quick_sort()
{
	do_quick_sort(0, count - 1);
}
 
template<class List_entry>
void Sortable_List<List_entry>::do_quick_sort(int low, int high)
{
	int pivot_position;
	if (low < high) {
		pivot_position = partition(low, high);
		do_quick_sort(low, pivot_position - 1);
		do_quick_sort(pivot_position + 1, high);
	}
}
 
template<class List_entry>
int Sortable_List<List_entry>::partition(int low, int high)
{
	List_entry pivot;
	swap(low, (low + high) / 2);					//将pivot放置到第一位
	pivot = entry[low];
	int last_small = low;
	for (int i = low + 1; i <= high; i++)
		if (entry[i] < pivot)  swap(last_small++, i);		//比pivot小的元素前移
	swap(low, last_small);						//将pivot放回
	return last_small;
}

6.归并排序（Merge Sort）

1）算法描述：

 

2）使用情况分析：

 

3）参考代码：

template<class List_entry>
void Sortable_list<List_entry>::mergesort(Sortable_list<List_entry> & list)
{
	Sortable_list secondlist;
	if (list.size() > 1) {
		mergedivide(list, secondlist);
		mergesort(list);
		mergesort(secondlist);
		mergecombine(list, secondlist);
	}
}
 
template<class List_entry>
void Sortable_list<List_entry>::mergecombine(Sortable_list<List_entry> & firstlist, const Sortable_list<List_entry> & secondlist)
{
	Sortable_list tmp;
	List_entry x, y;
	int n = 0, m = 0, i = 0;
	while (n < firstlist.size() && m < secondlist.size()) {
		firstlist.retrieve(n, x);
		secondlist.retrieve(m, y);
		if (x <= y) {
			tmp.insert(i++, x);
			n++;
		}
		else {
			tmp.insert(i++, y);
			m++;
		}
	}
	while (n < firstlist.size()) {
		firstlist.retrieve(n++, x);
		tmp.insert(i++, x);
	}
	while (m < secondlist.size()) {
		secondlist.retrieve(m++, y);
		tmp.insert(i++, y);
	}
	firstlist = tmp;
}
 
template<class List_entry>
void Sortable_list<List_entry>::mergedivide(Sortable_list<List_entry>& firstlist, Sortable_list<List_entry>& secondlist)
{
	int mid = (firstlist.size() - 1) / 2 + 1;
	List_entry x;
	for (int i = 0; firstlist.retrieve(mid, x)==success; i++) {
		secondlist.insert(i, x);
		firstlist.remove(mid, x);
	}
}

7.堆排序（Heap Sort）

1）算法描述：

 

2）使用情况分析：

 

3）参考代码：

template<class List_entry>
void Sortable_List<List_entry>::heap_sort()
{
	build_heap();		//建堆
	for (int last_unsorted = count - 1; last_unsorted > 0; last_unsorted--) {
		List_entry current = entry[last_unsorted];				
		entry[last_unsorted] = entry[0];
		insert_heap(current, 0, last_unsorted - 1);				//将最后一个元素插入堆中，获取下一个最值
	}
}
 
template<class List_entry>
void Sortable_List<List_entry>::insert_heap(const List_entry & current, int low, int high)
{
	int large = 2 * low + 1;
	while (large <= high) {
		if (large < high&&entry[large] < entry[large + 1])
			large++;		//将下标large调整为最大孩节点
		if (entry[large] < current)break;
		else {				//promote entry[large]
			entry[low] = entry[large];
			low = large;
			large = 2 * low + 1;
		}
	}
	entry[low] = current;
}
 
template<class List_entry>
void Sortable_List<List_entry>::build_heap()
{
	for (int low = count / 2 - 1; low >= 0; low--) {
		List_entry current = entry[low];
		insert_heap(current, low , count - 1);
	}
}

8.基数排序（Radix Sort）

1）算法描述：

 

 

2）使用情况分析：

 

3）参考代码：

MSD：

int alphabetic_order(char c)
{
	if (c == ' ' || c == '\0') return 0;
	if (c >= 'a'&&c <= 'z')return (c - 'a' + 1);
	if (c >= 'A'&&c <= 'Z')return (c - 'A' + 1);
	return 27;
}
 
void Sortable_list::rethread(queue<Record> queues[])
{
	Record x;
	for (int i = 0; i < max_char; i++)
	while (!queues[i].empty()) {
		x = queues[i].front();
		insert(size(), x);
		queues[i].pop();
	}
}
void Sortable_list::MSD_radix_sort()
{
	Record data;
	queue<Record> queues;
	while(remove(0,data)==success){
		queues.push(data);
	}
	sort(queues, key_size);
}

LSD：

void Sortable_list::LSD_radix_sort()
{
	Record data;
	queue<Record> queues[max_char];
	for (int position = key_size - 1; position >= 0; position--) {
		// Loop from the least to the most significant position.
		while (remove(0, data) == success) {
			int queue_number = alphabetic_order(data.key_letter(position));
			queues[queue_number].push(data); // Queue operation.
		}
		rethread(queues); // Reassemble the list.
	}
}

9.树排序（Tree Sort）

1）算法描述：

 

2）适用情况分析：

 

3）参考代码：

template<class Record>
Error_code Binary_search_tree<Record>::c_insert(const Record & item)
{
	Binary_node<Record> *&tmp=root;
	if(!tmp)root = new Binary_node<Record>(item);
	else {
		while (tmp != NULL) {
			if (tmp->data > item)tmp = tmp->left_child;
			else if (tmp->data < item)tmp = tmp->right_child;
			else return duplicate_error;
		}
		tmp = new Binary_node<Record>(item);
		return success;
	}
}
 
template<class Entry>
void Binary_tree<Entry>::recursive_inorder(Binary_node<Entry>* sub_root, void(*visit)(Entry &))
{
	if (sub_root) {
		recursive_inorder(sub_root->left_child,visit);
		(*visit)(sub_root->data);
		recursive_inorder(sub_root->right_child, visit);
	}
}
 
template<class Entry>
void Binary_tree<Entry>::recursive_inorder(Binary_node<Entry>* sub_root, void(*visit)(Entry &))
{
	if (sub_root) {
		recursive_inorder(sub_root->left_child,visit);
		(*visit)(sub_root->data);
		recursive_inorder(sub_root->right_child, visit);
	}
}

 

 做的有些仓促，还望大家指正错误。