数据结构：排序算法总结_数据结构实验排序总结

常用排序算法时空复杂度及稳定性：

      线性表的冒泡排序采用双层循环迭代的方式，排序方式由大到小，内循环每次冒出一个最大数到待排序数的表头，外循环控制当前待排序数表的长度。这个过程像是水中的气泡冒出的过程，小的气泡在下向上冒出的过程中慢慢变大最后大的气泡冒出水面。

算法过程：（由大到小排序，从前往后遍历）

1. 每次遍历前后两个数，遇到前一个数小于后一个数交换两个数的位置。

2. 循环一次结束，下次循环的长度减1。

3. 直到遍历完整个数组。

#include "sort.h"
 
vector<int> popSort(vector<int>& src)
{
	int n = src.size();
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n - i - 1; ++j)
		{
			if (src[j] < src[j + 1])
				SWAP(src[j], src[j + 1]);
		}
	}
	return src;
}

改进的冒泡排序：

       对冒泡的过程进行排序（由大到小排序），在进行表的遍历的过程，采用来回遍历的方式，从左往右遍历的过程中冒出最小值到表尾部，右端标记向左滑动一位，再从右往左遍历的过程中冒出最大值到表头，左端的标记向右滑动一位。直到最后左端的标记等于右端的标记结束。

算法过程：

1. 从左端往右端遍历线性表，对比前后数据，当左边数据比右边小时调换两个数据，直到右端标记遍历结束，右端标记向左移动一位。

2. 再从右端标记向左端标记遍历，对比前后数据，当左边数据比右边小时调换两个数据，直到左端标记遍历结束，左端标记向右移动一位。

3. 当左端标记等于右端标记时，排序结束。

#include "sort.h"
 
vector<int> advancePopSort(vector<int>& src)
{
	int left = 0, right = src.size() - 1;
	while (left < right)
	{
		for (int i = left; i < right; ++i)
		{
			if (src[i] < src[i + 1])
				SWAP(src[i], src[i + 1]);
		}
		right--;
		for (int j = right; j > left; --j)
		{
			if (src[j] > src[j - 1])
				SWAP(src[j], src[j - 1]);
		}
		left++;
	}
	return src;
}

选择排序：

       数据排列从大到小的选择排序，线性表选择排序的基本思想是：从一堆数据中选择出一个最大的数和表头的数据进行调换，然后再在剩下的数中选择次大的数和从表头开始的第二个数进行调换，依此向下，直到遍历完整个表。

算法过程：

1. 循环遍历数据从中找到最大的数据和当前表头位置的数进行调换。

2. 调换完成后，表头标记为已排序完数的下一个数。

3. 直到表中所有的数据有序。

#include "sort.h"
 
//实现形式一：
vector<int> seekSort(vector<int>& src)
{
	int n = src.size();
	for (int i = 0; i < n - 1; ++i)
	{
		int pos = -1, max = src[i];
		for (int j = i + 1; j < n; ++j)
		{
			if (max < src[j])
			{
				max = src[j];
				pos = j;
			}
		}
		if (pos != -1)
			SWAP(src[i], src[pos]);
	}
 
	return src;
}
 
//实现形式二：
vector<int> selectSort(vector<int>& src)
{
	int n = src.size();
	for (int i = 0; i < n - 1; ++i)
	{
		int min = i;
		for (int j = i + 1; j < n; ++j)
		{
			if (src[j] > src[min])
				min = j;
		}
		if (min != i)
		{
			SWAP(src[i], src[min]);
		}
	}
 
	return src;
}

插入排序：

       线性表的插入排序，（从大到小）插入排序的基本思路是：从一个数开始，将其看作是有序，取下一个数，如果次数比第一个数小则将次数插在第一个数的后面，反之，将第一个数往后挪一位，将次数插在第一个数前面，这样构成一个包含两个数的有序列。接下来取出第三个数，并遍历有序列，找到合适的插入位置，将插入位置之后的数整体往后挪一位。这样取数插入，直到整个表中的数据被全部取完。

算法过程：

1. 取数的过程从第二个数开始。

2. 找到合适的位置，将位置后排好序的数依此向后移动一个位置。

3. 直到，表中的数据全部取出。

#include "sort.h"
 
vector<int> insertSort(vector<int>& src)
{
	int n = src.size();
 
	for (int i = 1; i < n; ++i)
	{
		int temp = src[i], pos = -1;
		for (int j = i - 1; j >= 0; --j)
		{
			if (src[j] < temp)
			{
				pos = j;
			}
		}
		if (pos != -1)
		{
			for (int k = i; k > pos; --k)
			{
				src[k] = src[k - 1];
			}
			src[pos] = temp;
		}
	}
 
	return src;
}

希尔排序：

       线性表做希尔排序，（由大到小）希尔排序是渐变步长的插入排序，一开始步长较大可以在初排序的过程中保证序列相对有序，再依此缩短步长，下次排序只需要做出局部调整，当步长变成1时再略微调整，排序就结束了。

算法过程：

1. 选择步长，进行插入排序。

2. 缩短步长进行插入排序。

#include "sort.h"
 
vector<int> shellSort(vector<int>& src)
{
	int n = src.size();
	for (int step = n / 2; step > 0; step /= 2)
	{
		for (int i = step; i < n; ++i)
		{
			for (int j = i - step; j + step < n; j += step)
			{
				if (src[j] > src[j + step])
					SWAP(src[j], src[j + step]);
			}
		}
	}
	return src;
}

堆排序：

       堆排序是利用二叉树的概率构造大顶堆和小顶堆，大顶堆中每一个子树其根节点的值总是大于或等于左右子节点，小顶堆，则相反，根节点的值都小于等于左右子节点。但在对线性表做堆排序时，并不需要构建堆，也就是不需要构建二叉树。秩序要应用一下规则：

//下标为i的节点其做左叶子节点的下标为2i + 1,其右叶子节点下标为2i + 2
//大顶堆：a[i] >= a[2 * i + 1] && a[i] >= a[2 * i + 2];

//小顶堆：a[i] <= a[2 * i + 1] && a[i] <= a[2 * i + 2];

因此每次对序列进行一次大顶堆或小顶堆的调整，就可以得到一个最大数或者是最小数，并将次数从堆中分隔出放置线性表结尾，再对余下数进行调整，直到所有数都被调整为有序。

#include "sort.h"
 
//下标为i的节点其做左叶子节点的下标为2i + 1,其右叶子节点下标为2i + 2
//大顶堆：a[i] >= a[2 * i + 1] && a[i] >= a[2 * i + 2];
//小顶堆：a[i] <= a[2 * i + 1] && a[i] <= a[2 * i + 2];
 
void adjustHeep(vector<int>& src, int end)
{
	for (int i = end / 2; i >= 0; --i)
	{
		if (2 * i + 2 <= end && src[i] > src[2 * i + 2])
		{
			SWAP(src[i], src[2 * i + 2]);
		}
		if (2 * i + 1 <= end && src[i] > src[2 * i + 1])
		{
			SWAP(src[i], src[2 * i + 1]);
		}
	}
}
 
vector<int> heepSort(vector<int>& src)
{
	for (int i = src.size() - 1; i > 0; --i)
	{
		adjustHeep(src, i);
		SWAP(src[0], src[i]);
	}
	return src;
}

归并排序：

       归并排序的思想，类似于刚学数据结构时总会做到的一道数据结构题：将两个有序序列合并为一个有序序列。因此对于一个无序的序列做归并排序，其过程很容易结合递归操作进行。在递归深入的过程中将一串无需的序列划分为一个个单独的数，单独的数当作是有序的，在递归回溯的过程中将这些单独的数一对一对合并成序列，最终合并成一个大的有序的序列。

#include "sort.h"
 
vector<int>& mergeStep(vector<int>& src, int af, int at, int bf, int bt)
{
	vector<int> a(src.begin() + af, src.begin() + at + 1);
	vector<int> b(src.begin() + bf, src.begin() + bt + 1);
 
	size_t i = 0, j = 0;
	while (i < a.size() && j < b.size())
	{
		if (a[i] < b[j])
		{
			src[af] = a[i];
			i++;
		}
		else
		{
			src[af] = b[j];
			j++;
		}
		af++;
	}
 
	if (i < a.size())
	{
		for (; i < a.size(); ++i)
		{
			src[af++] = a[i];
		}
	}
 
	if (j < b.size())
	{
		for (; j < b.size(); ++j)
		{
			src[af++] = b[j];
		}
	}
	return src;
}
 
vector<int>& mergerSort(vector<int>& src, int left, int right)
{
	if (left >= right)
		return src;
 
	int mid = (left + right) / 2;
	mergerSort(src, left, mid);
	mergerSort(src, mid + 1, right);
	mergeStep(src, left, mid, mid + 1, right);
}

快速排序：

       快速排序的思想是，每次从无序的序列中找出一个基数，对序列做划分，大于基数的数放一边，小于基数的数放另一边。下一次，再分别对基数两边无序的数，从中再寻找基数做划分，这样一直划分下去，直到选取基数后其两边都没有数，快速排序结束。

       由于其空间复杂度是O(1)，需要一个单位的辅助空间用来保存基数的值，所以开始遍历对比的方向是序列中相对于基数的另一头，例如：如果从左边开始取基数，那么开始比较的时候取的数一定是从序列的右边开始，这样进行交换。

       一次选取基数排序的过程结束的标志是左边的位置标记等于右边位置标记的值。如果是从小往大排序，比基数小的放在左边，比基数大的放在右边。

#include "sort.h"
#include <stack>
 
 
//vector 返回使用移动语义，如果返回值不是引用类型会引起内存不可读
vector<int>& quickSort(vector<int>& src, int left, int right) 
{
	if (left >= right)
		return src;
 
	int l = left;
	int r = right;
	int temp = src[left];
	while (l < r)
	{
		while (l < r && src[r] >= temp)
		{
			r--;
		}
		src[l] = src[r];
		while (l < r && src[l] <= temp)
		{
			l++;
		}
		src[r] = src[l];
	}//r == l
	src[l] = temp;
	quickSort(src, left, l - 1);
	quickSort(src, r + 1, right);
}
 
 
//返回划分值下标：
int seek(vector<int>&src, int l, int r)
{
	int index = l;
	int temp = src[l];
	while (l < r)
	{
		while (l < r && src[r] <= temp)
		{
			r--;
		}
		src[l] = src[r];
		while (l < r && src[l] >= temp)
		{
			l++;
		}
		src[r] = src[l];
	}//l == r
	src[l] = temp;
	index = l;
	return index;
}
//栈实现快速排序：
vector<int>& quickSort(vector<int>& src)
{
	size_t index = seek(src, 0, src.size() - 1);
	stack<size_t> range;
	if (index - 1 > 0)//基准左边有数据
	{
		range.push(0);
		range.push(index - 1);
	}
	if (index + 1 < src.size() - 1) //基准右边有数据
	{
		range.push(index + 1);
		range.push(src.size() - 1);
	}
 
	while (!range.empty())
	{
		size_t right = range.top();
		range.pop();
		size_t left = range.top();
		range.pop();
 
		index = seek(src, left, right);
 
		if (index - 1 > left)
		{
			range.push(left);
			range.push(index - 1);
		}
 
		if (index + 1 < right)
		{
			range.push(index + 1);
			range.push(right);
		}
	}
 
	return src;
}

相关内容：

        上文中用到的头文件sort.h

#pragma once
 
#include <iostream>
#include <vector>
using namespace std;
 
#define SWAP(a, b) a^=b^=a^=b

        上文中的main函数

#include "sort.h"
 
extern vector<int> advancePopSort(vector<int>&);
extern vector<int> seekSort(vector<int>&);
extern vector<int> selectSort(vector<int>&);
extern vector<int> insertSort(vector<int>& src);
extern vector<int>& quickSort(vector<int>& src, int left, int right);
extern vector<int> shellSort(vector<int>& src);
extern vector<int>& mergerSort(vector<int>& src, int left, int right);
extern vector<int> heepSort(vector<int>& src);
extern vector<int>& quickSort(vector<int>& src);
 
void showResult(const vector<int>& src)
{
	typedef vector<int>::const_iterator vi_itr;
	for (vi_itr itr = src.begin(); itr != src.end(); ++itr)
	{
		cout << *itr << " ";
	}
	cout << endl;
}
 
int main()
{
	int buf[] = { 2, 3, 1, 7, 5, 8, 4, 3, 6 };
 
	//vector<int> sort_buff = insertSort(vector<int>(buf, buf + 9));
	/*vector<int> sort_buff(buf, buf + 9);
	quickSort(sort_buff, 0, 8);*/
 
	//vector<int> sort_buff = mergerSort(vector<int>(buf, buf + 9), 0, 8);
	vector<int> sort_buff = shellSort(vector<int>(buf, buf + 9));
 
	showResult(sort_buff);
}

       C++容器vector中用到的排序算法，是快速排序算法，但是是基于插入排序和堆排序实现的。

       算法的稳定性是指，相同的数在排序前后依然保持相对位置，为稳定的排序算法，否则为不稳定的排序算法。