我的创作纪念日 ---- 2024/3/26

前言

2024.3.26是我在CSDN成为创作者的第128天，也是我第一次真正在网上创作的第128天

当我还在日常创作时，突然发现我收到了一封信

我想我可以分享一下这段时间的感想以及收获

机缘

在CSDN的这段时间里，我学习到了很多知识，也丰富了我的日常生活

在我编写实战项目的时候，有很多操作我还是不是很了解的，尤其是在学校的实战项目，当我遇到不会的代码时可以利用CSDN来学习我的知识盲区，实战项目结束后我认为将项目写到博客里是很有意义的

我认为当我意识到了写博客的时候我的一个机缘就来了

一是可以帮助别人了解相关方面的思路知识等

二是可以巩固自身的基础

做这件事情不仅仅对自身受益匪浅，对他人亦是莫大帮助

只有当自己需要帮助去观看别人的博客的时候，才能感受到一篇好的博客是有多么重要！！！

收获

目前在这段时间里只创作了22篇博客，跟我想的进度差不多

我给自己的任务是一星期一篇博客，希望能够对各位有所收获

我的收获即是对知识的巩固，当然如若能帮助到别人那更是我莫大的收获

日常

创作目前已经是我学习、生活中的一部分了

当我学习一个知识点一段时间之后总会忘记一部分，但这时候写博客不仅能帮助回忆，还能帮助其他人，与其他人一起进步学习

不管再忙，或许在夜间听听歌，敲敲键盘，不知不觉的一篇博客就完成了，这种沉浸其中的感觉也是非常不错的，虽然会感觉时间过的很快，但不会觉得这一天白费了

成就

目前大一下学期，学习进度只到了C++，进度不是很快，但我觉得我写的最好的代码就是数据结构的实现了

下面是快速排序的各种实现方法，其中涉及了递归、非递归（栈、队列）

#include <stdio.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>

// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* a, int left, int right);

// 快速排序挖坑法
int PartSort2(int* a, int left, int right);

// 快速排序前后指针法
int PartSort3(int* a, int left, int right);

//快速排序
void QuickSort(int* a, int left, int right);

// 快速排序 非递归实现 栈
void QuickSortNonR1(int* a, int left, int right);

// 快速排序 非递归实现 队列
void QuickSortNonR2(int* a, int left, int right);

//三数取中法，让key值再中间提升快排效率
int GetMidIndex(int* a, int begin, int end)
{
	int mid = (begin + end) / 2;
	if (a[begin] > a[mid])
	{
		if (a[mid] > a[end])
		{
			return mid;
		}
		else if (a[begin] < a[end])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
	else //a[begin] < a[mid]
	{
		if (a[begin] > a[end])
		{
			return begin;
		}
		else if (a[end] > a[mid])
		{
			return mid;
		}
		else
		{
			return end;
		}
	}
}

int PartSort1(int* a, int left, int right)
{
	int mid = GetMidIndex(a, left, right);
	Swap(&a[mid], &a[left]);

	int keyi = left;

	while (left < right)
	{
		//要先找小，因为keyi在左，右边先出发相遇位置一定是小
		//找小
		while (left < right && a[right] >= a[keyi])
			right--;

		//找大
		//等号一定要加，因为begin是从keyi开始的
		while (left < right && a[left] <= a[keyi])
			left++;

		if (left < right)
			Swap(&a[left], &a[right]);
	}
	Swap(&a[keyi], &a[left]);

	return left;
}

int PartSort2(int* a, int left, int right)
{
	int mid = GetMidIndex(a, left, right);
	Swap(&a[mid], &a[left]);

	int hole = left;
	//key记录挖坑位置的值
	int key = a[hole];

	while (left < right)
	{
		while (left < right && a[right] >= key)
			right--;

		a[hole] = a[right];
		hole = right;

		while (left < right && a[left] <= key)
			left++;

		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;

	return hole;
}

int PartSort3(int* a, int left, int right)
{
	int mid = GetMidIndex(a, left, right);
	Swap(&a[mid], &a[left]);

	int key = left;
	int prev = left, cur = left + 1;
	while (cur <= right && prev != cur)
	{
		if (a[cur] <= a[key])
		{
			prev++;
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	Swap(&a[left], &a[prev]);

	return prev;
}

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;

	//先排好keyi这个固定位置，再向两边排
	int keyi = PartSort3(a, left, right);

	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}

//栈版本，深度优先
void QuickSortNonR1(int* a, int left, int right)
{
	Stack s;
	StackInit(&s);

	//必须先入栈入右区间再入左区间，因为栈是先进后出
	StackPush(&s, right);
	StackPush(&s, left);

	while (!StackEmpty(&s))
	{
		left = StackTop(&s);
		StackPop(&s);
		right = StackTop(&s);
		StackPop(&s);

		int keyi = PartSort1(a, left, right);

		if (left < keyi)
		{
			StackPush(&s, keyi - 1);
			StackPush(&s, left);
		}
		if (right > keyi)
		{
			StackPush(&s, right);
			StackPush(&s, keyi + 1);
		}
	}
}

//队列版本，广度优先
void QuickSortNonR2(int* a, int left, int right)
{
	Queue q;
	QueueInit(&q);

	QueuePush(&q, left);
	QueuePush(&q, right);

	while (!QueueEmpty(&q))
	{
		left = QueueFront(&q);
		QueuePop(&q);
		right = QueueFront(&q);
		QueuePop(&q);

		int keyi = PartSort1(a, left, right);

		if (left < keyi)
		{
			QueuePush(&q, left);
			QueuePush(&q, keyi - 1);
		}
		if (right > keyi)
		{
			QueuePush(&q, keyi + 1);
			QueuePush(&q, right);
		}
	}
}