排序算法——十大排序算法的图示与实现

比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
前七种为比较类排序，后三种为非比较类排序。
稳定性：如果a=b，且a在b前面，排序之后仍能保证a在b前面，则为稳定的。

将左端第一个元素视为有序，然后遍历后面的元素，逐步插入到有序序列中。

//插入排序
void insertionSort(vector& nums)
{
	for (int i = 1; i < nums.size(); ++i)
	{
		int j = i - 1;
		int tmp = nums[i];
		while (j >= 0 && tmp <= nums[j])
		{
			nums[j + 1] = nums[j];
			j--;
		}
		nums[j + 1] = tmp;
	}
}

选择最小的元素和左端交换。

//选择排序
void selectionSort(vector& nums)
{
	for (int i = 0; i < nums.size(); ++i) {
		int minIndex = i;
		for (int j = i + 1; j < nums.size(); ++j) {
			if (nums[j] < nums[minIndex])
			{
				minIndex = j;
			}
		}
		swap(nums[i], nums[minIndex]);
	}

从左到右遍历，遇到小的就交换两个元素，逐渐把大的放到右端。

//冒泡排序
void bubbleSort(vector& nums)
{
	for (int i = 0; i < nums.size() - 1; ++i) {
		for (int j = 0; j < nums.size() - i - 1; ++j) {
			if (nums[j] > nums[j + 1])
			{
				swap(nums[j], nums[j + 1]);
			}
		}
	}
}

希尔排序是插入排序的改进版，通过引入增量将原序列分为多个子序列，对子序列使用插入排序，然后缩小增量，子序列减少，因为前面进行的排序，使得后续使用插入排序时速度更快。
图示

//希尔排序
void shellSort(vector& nums)
{
	for (int gap = nums.size() / 2; gap > 0; gap /= 2) {
		//从第gap个元素开始对组内排序
		for (int i = gap; i < nums.size(); ++i) {
			int j = i;
			while (j - gap >= 0 && nums[j] < nums[j - gap])
			{
				swap(nums[j], nums[j - gap]);
				j -= gap;
			}
		}
	}
}

归并排序与快速排序都是基于递归的思想实现的，而归并排序重点在于合并有序序列。
把一个序列分割到只有一个元素的时候，子序列就变成了有序的，只要保证子序列合并后为有序序列，那么最终的序列就是有序的。
那么归并排序的步骤就确定了：
1.确定结束条件
2.划分左右子序列递归调用归并排序
3.合并有序的子序列
如图所示

//归并排序,先分后合并，需要一个临时数组复制当前区间，一次遍历实现有序合并
void mergeSort(int left, int right, vector&num, vector& tmp)
{
	//结束条件
	if (left >= right)
		return;
	//划分
	int mid = (left + right) / 2;
	mergeSort(left, mid, num, tmp);
	mergeSort(mid + 1, right, num, tmp);
	//合并
	//使用i,j表示左右半区间的访问下标
	int i = left, j = mid + 1;
	//先存储到tmp
	for (int k = left; k <= right; ++k)
	{
		tmp[k] = num[k];
	}
	for (int k = left; k <= right; ++k)
	{
		//i走完了左半区间
		if (i == mid + 1)
			num[k] = tmp[j++];
		//j走完了右半区间，以及tmp[i]小的时候
		else if (j == right + 1 || tmp[i] < tmp[j])
		{
			num[k] = tmp[i++];
		}
		else{
			num[k] = tmp[j++];
		}
	}
}

快速排序的思想是选择一个边界基准元素，将序列小于该元素的放到左边，大于的放到右边，然后对左右子序列再进行快排，是先简单排序再划分的思想。
步骤：
1.确定结束条件
2.按边界基准元素对序列一次排序
3.按基准元素的位置划分左右子序列进行快排
图示

//快排
void quicksort(vector& vec, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int lt = left;
	int r = right;
	while (lt < r)
	{
		while (lt < r && vec[r] >= vec[left])
		{
			--r;
		}
		while (lt < r && vec[lt] <= vec[left])
		{
			++lt;
		}
		swap(vec[lt], vec[r]);
	}
	swap(vec[left], vec[lt]);
	quicksort(vec, left, lt - 1);
	quicksort(vec, lt + 1, right);
}

堆是一种数据结构，可以看做完全二叉树，最大堆（大顶堆），即父节点值大于子节点的值，这保证了最大值一定在根节点上；最小堆（小顶堆），父节点的值小于子节点的值，这保证了最小值一定在根节点上。利用堆的特性，将待排序的序列构建成最大堆，将根节点元素交换至右端，将剩下的n-1个元素再构建为最大堆，将根节点元素交换至右端下一个位置。
堆排序的核心在于构建堆。
最大堆的初始化图示。

c++中的priority_queue即是利用堆实现的， priority_queue 升序队列，最小堆
priority_queue 降序队列，最大堆

堆的初始化

//调整堆
void adjustHeap(vector& nums, int node, int end)
{
	//要调整的节点是最后的叶节点
	if (node > ((end - 1) / 2))
	{
		return;
	}
	int maxNode;
	//因为是根节点，最少有一个左叶节点
	if (node * 2 + 2 <= end)
	{
		if (nums[node * 2 + 2] > nums[node * 2 + 1])
		{
			maxNode = node * 2 + 2;
		}
		else {
			maxNode = node * 2 + 1;
		}
	}
	else {
		maxNode = node * 2 + 1;
	}
	if (nums[maxNode] > nums[node])
	{
		swap(nums[maxNode], nums[node]);
		//发生交换，对于交换后的子节点再进行调整
		adjustHeap(nums, maxNode, end);
	}
}

//最大堆初始化
void buildHeap(vector& nums, int end)
{
	int node = (end - 1) / 2;
	//从最后一个非子叶节点开始调整
	for (int i = node; i >= 0; --i) {
		adjustHeap(nums, i, end);
	}
}

使用堆实现堆排序可以利用堆的输出
将堆的根节点元素输出，将最后一个元素放到根节点，然后从上往下调整

//堆的输出
void popHeap(vector& nums, int& end)
{
	if (end <= 0) {
		printf("堆已为空n");
		return;
	}
	//交换根节点
	swap(nums[0], nums[end--]);
	if (end == 0) {
		return;
	}
	for (int i = 0; i <= (end - 1) / 2; ++i)
	{
		adjustHeap(nums, i, end);
	}
}
//堆排序
void heapSort(vector& nums)
{
	buildHeap(nums, nums.size() - 1);
	int end = nums.size() - 1;
	for (int i = 0; i < nums.size() - 1; ++i) {
		popHeap(nums, end);
	}
}

将堆封装为类的形式，逐步pop堆顶元素即可实现排序。

//最大堆
class maxHeap
{
public:
	maxHeap(vector nums) {
		heapVec.assign(nums.begin(), nums.end());
		count = nums.size();
		last_root_node = count / 2 - 1;
		//从最后一个非子叶节点开始调整
		for (int i = last_root_node; i >= 0; --i) {
			adjustHeap(i);
		}
	}
	//堆的输出
	int popHeap()
	{
		if (count == 0) {
			printf("堆已为空n");
			return 0;
		}
		//交换根节点
		int rootNode = heapVec[0];
		swap(heapVec[0], heapVec[count - 1]);
		//更新count和last_root_node
		count--;
		last_root_node = count / 2 - 1;
		heapVec.pop_back();
		for (int i = 0; i <= count / 2 - 1; ++i)
		{
			adjustHeap(i);
		}
		return rootNode;
	}
	void heapPrintf() {
		printf("当前堆序列为:");
		for (auto i : heapVec) {
			printf("%d ", i);
		}
		printf("n");
	}
private:
	//调整堆
	void adjustHeap(int node)
	{
		//要调整的节点是最后的叶节点
		if (node > last_root_node)
		{
			return;
		}
		int maxNode;
		//因为是根节点，最少有一个左叶节点
		if (node * 2 + 2 < count)
		{
			if (heapVec[node * 2 + 2] > heapVec[node * 2 + 1])
			{
				maxNode = node * 2 + 2;
			}
			else {
				maxNode = node * 2 + 1;
			}
		}
		else {
			maxNode = node * 2 + 1;
		}
		if (heapVec[maxNode] > heapVec[node])
		{
			swap(heapVec[maxNode], heapVec[node]);
			//发生交换，对于交换后的子节点再进行调整
			adjustHeap(maxNode);
		}
	}
	vector heapVec;
	int count;
	int last_root_node;
};

计数排序不是基于比较的排序，而是采用了以空间换时间的思想。
找到待排序序列的最小值最大值，然后初始化一个(max-min+1)大小的数组用于存放元素的个数。
然后遍历待排序序列记录对应元素的个数，最后遍历记录数组，按对应元素的个数放入序列实现排序。
图示

//计数排序
void countSort(vector& nums)
{
	if (nums.size() <= 1)
	{
		return;
	}
	int max = nums[0], min = nums[0];
	for (auto i : nums) {
		max = max < i ? i : max;
		min = min > i ? i : min;
	}
	vector count_arr(max - min + 1);
	for (int i = 0; i < nums.size(); ++i ) {
		count_arr[nums[i] - min]++;
	}
	int count_nums = 0;
	for (int index = 0; index < count_arr.size(); ++index) {
		while (count_arr[index])
		{
			nums[count_nums] = min + index;
			count_nums++;
			count_arr[index]--;
		}
	}
}

计数排序的扩展，试想把计数排序的储存一个元素改为储存一定范围的元素，每个储存区就称之为桶，对每个桶内部进行排序，最后按桶的顺序进行合并即可。由于入桶是利用函数映射关系直接计算出该元素应该放入哪个桶，无需比较，所以时间花费较少。桶内部的排序算法可以根据具体情况选择。
图示

//桶排序
void bucketSort(vector& nums)
{
	int max_num = nums[0], min_num = nums[0];
	//设定桶的个数为4
	int bucket_num = 4;
	for (auto i : nums)
	{
		max_num = i > max_num ? i : max_num;
		min_num = i < min_num ? i : min_num;
	}
	int bucket_num_len = (max_num - min_num + 1) / bucket_num + 1;
	vector> buckets(4);
	for (auto i : nums)
	{
		if ((i - min_num) / bucket_num_len == 0)
		{
			buckets[0].push_back(i);
		}
		else if ((i - min_num) / bucket_num_len == 1)
		{
			buckets[1].push_back(i);
		}
		else if ((i - min_num) / bucket_num_len == 2)
		{
			buckets[2].push_back(i);
		}
		else {
			buckets[3].push_back(i);
		}
	}
	int count = 0;
	for (int i = 0; i < buckets.size(); ++i)
	{
		if (!buckets[i].empty())
		{
			sort(buckets[i].begin(), buckets[i].end());
			for (auto j : buckets[i])
			{
				nums[count] = j;
				++count;
			}
		}
	}
}

针对多重优先级的排序。
从低位开始对元素进行计数排序，然后按高位进行计数排序，直到最高位。
图示

//基数排序
void radixSort(vector& nums)
{
	int max_num = nums[0];
	for (auto i : nums)
	{
		max_num = i > max_num ? i : max_num;
	}
	int max_digit = 1;
	while (max_num)
	{
		max_num /= 10;
		max_digit++;
	}
	for (int i = 1; i <= max_digit; ++i)
	{
		vector> radix_vec(10);
		for (auto j : nums)
		{
			int tmp = j / pow(10, i - 1);
			tmp %= 10;
			radix_vec[tmp].push_back(j);
		}
		int count = 0;
		for (int i = 0; i < radix_vec.size(); ++i)
		{
			if (!radix_vec[i].empty())
			{
				for (auto j : radix_vec[i])
				{
					nums[count] = j;
					++count;
				}
			}
		}
	}
}