hanfengye (韩丰业)

UID: 167, 注册于 2023-2-26 13:23:58, 最后登录于 2023-10-20 11:26:04, 目前离线.

解决了 12 道题目，RP: 0 (No. ?)

♂

个人简介
骗分过样例，暴力出奇迹。

数学先打表，ＤＰ看运气。

穷举ＴＬＥ，递推ＵＫＥ。

模拟ＭＬＥ，贪心还ＣＥ。

想要骗到分，就要有方法。

图论背模板，数论背公式。

动规背方程，高精背代码。

如果都没背，干脆输样例。

1.插入排序

思想：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

实际中我们玩扑克牌时，就用了插入排序的思想：

演示过程动图：

**单趟：**若数组(arr)除最后一个元素外其余全部有序，设最后一个元素的下标为i，将arr[i]与前面的元素比较，前面的元素比他大则前面的元素向右移动，比他小则在该元素的后面插入。

**复合：**因为不知道数组中得到前几个元素是已经有序的，所以直接从第二个元素开始执行插入排序，单个过程与上述相同，将每个元素都进行一次插入排序。

代码如下：
```
// 插入排序
void InsertSort(int* a, int n)
{
	assert(a);
	int i = 0;
	for (i = 0; i < n - 1; i++)//因为x元素位置是i的下一个位置，为防止x越界，需要使 i < n-1
	{
		int end = i;//已经有序的最后一个元素(一个元素不需要排序，所以默认从0开始)
		int x = a[end + 1];//需要排序的元素

        //单趟
		while (end >= 0)
		{

            //若前一个数字大于x，则需将他向右移动
			if (a[end] > x)
			{
				a[end + 1] = a[end];
                //继续判断前面的元素
				--end;
			}

            //前面元素小于x
			else
			{
				break;
			}
		}

        //将x插入正确位置(两种情况)
        //1.前面的数字小于x
        //2.前面的数字都大于x，x放在下标为0处
		a[end + 1] = x;
	}
}
```
直接插入排序的特性总结：
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定
2.希尔排序

希尔排序法又称缩小增量法。

基本思想：

先选定一个整数gap，把待排序文件中所有记录分成gap个组，所有距离为gap的记录分在同一组内，并对每一组内的元素进行排序。

然后将gap逐渐减小重复上述分组和排序的工作。

当到达gap=1时，所有元素在统一组内排好序。

静态图演示：

**动图演示： **

这里重要的是理解分组思想，每一个组其实就是一个插入排序，相当于进行多次插入排序。

代码如下：
```
// 希尔排序
void ShellSort(int* a, int n)
{
	assert(a);
	int gap = n;
	while (gap > 1)
	{
		//gap /= 2;
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int x = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > x)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = x;
		}
	}
}
```
希尔排序的特性总结：
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，这里不深究。
4. 时间复杂度O(N^1.5)
5. 空间复杂度O(1)
6. 稳定性：不稳定。
3.选择排序

基本思想：

第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始(末尾)位置，

然后选出次小(或次大)的一个元素，存放在最大(最小)元素的下一个位置，

重复这样的步骤直到全部待排序的数据元素排完。

动图演示：

代码入下：

这里我们可以进行一个优化，最小值和最大值同时选，然后将最小值与起始位置交换，将最大值与末尾位置交换。
```
// 选择排序
void SelectSort(int* a, int n)
{
	assert(a);
	int begin = 0;//保存数组的起始位置
	int end = n - 1;//保存换数组的末尾位置

	while (begin < end)
	{
		int maxi = begin;//保存最大元素下标
		int mini = begin;//保存最小元素下标

        //遍历数组寻找最小和最大元素
		for (int i = begin; i <= end; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}

        //将最小元素交换到起始位置
		Swap(a+begin, a+mini);

        //判断最大值的位置是否在起始位置
		if (maxi == begin)
		{
			maxi = mini;  
		}

        //将最大元素交换到末尾位置
		Swap(a+end, a+maxi);
        //移动数组起始和末尾位置
		begin++;
		end--;
	}
}
```
注意：

在进行最小值和最大值同时交换时也会出现一个问题，

如果最大值在起始位置的时候，交换了最小值之后，最大值就被交换到了min的位置，

如果继续交换max，就会将最小值交换到末尾位置。

所以，在每次交换了最小值之后应该判断一下最大值是否在起始位置，如果在需要将max赋值为min。
直接选择排序的特性总结：
1. 直接选择排序思考非常好理解，但是效率不是很好(不论数组是否有序都会执行原步骤)。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
4.堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

1. 建堆
- 升序：建大堆
- 降序：建小堆
2. 利用堆删除思想来进行排序 建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

这里以升序为例：
- 首先应该建一个大堆，不能直接使用堆来实现。可以将需要排序的数组看作是一个堆，但需要将数组结构变成堆。
- 我们可以从堆从下往上的第二行最右边开始依次向下调整直到调整到堆顶，这样就可以将数组调整成一个堆，且如果建立的是大堆，堆顶元素为最大值。
- 然后按照堆删的思想将堆顶和堆底的数据交换，但不同的是这里不删除最后一个元素。
- 这样最大元素就在最后一个位置，然后从堆顶向下调整到倒数第二个元素，这样次大的元素就在堆顶，重复上述步骤直到只剩堆顶时停止。
动图演示：

注意：实际中并没有删除堆中元素，图中为了方便表示，将交换后的位置画成了空。

代码如下：
```
// 堆排序
void AdjustDown(int* a, int n, int root)//向下调整
{
	assert(a);
	int parent = root;
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int* a, int n)
{
	assert(a);

    //建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}

    //交换
	for (int i = n - 1; i > 0; i--)
	{
		Swap(&a[i], &a[0]);
		AdjustDown(a, i, 0);
	}
}
```
直接选择排序的特性总结：
1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
5.冒泡排序

冒泡排序应该是我们最熟悉的排序了，在C语言阶段我们就学习了冒泡排序。

他的思想也非常简单：

两两元素相比，前一个比后一个大就交换，直到将最大的元素交换到末尾位置。这是第一趟

一共进行n-1趟这样的交换将可以把所有的元素排好。

(n-1趟是因为只剩两个元素时只需要一趟就可以完成)

动图演示：

代码如下：
```
// 冒泡排序
void BubbleSort(int* a, int n)
{
    assert(a);
	int i = 0;
	int flag = 0;

    //n-1趟排序
	for (i = 0; i < n-1; i++)
	{
		int j = 0;

        //一趟冒泡排序
		for (j = 0; j < n - i - 1; j++)
		{
			if (a[j] > a[j+1])
			{
				Swap(&a[j], &a[j+1]);
				flag = 1;
			}
		}

        //若某一趟排序中没有元素交换则说明所有元素已经有序，不需要再排序
		if (flag == 0)
		{
			break;
		}
	}
}
```
冒泡排序的特性总结：
1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定
6.快速排序

这里是排序算法的重点了，非常重要！

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，

其基本思想为：

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

7.归并排序

7.1递归实现

基本思想：

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

若将两个有序表合并成一个有序表，称为二路归并。

归并排序核心步骤：

按照其算法思想：

首先应在数组中找出有序的序列，但数组是否有序编译器可不知道。

所以可以将数组划分，一分二，二分四......直到每个序列中只有一个数字。

一个数字总可以认为他是有序的吧。

最后将同时划分的序列合并。

动图演示：

代码如下：
```
void _MergeSort(int* a, int left, int right,int* tmp)
{
    //区间中没有元素时不再合并
	if (left >= right)
	{
		return;
	}

    //划分数组，每次一分为二
	int mid = (left + right) / 2;
	_MergeSort(a, left, mid,tmp);//划分左区间
	_MergeSort(a, mid + 1, right,tmp);//划分右区间

    //合并有序序列
	int begin1 = left, end1 = mid;//有序序列1
	int begin2 = mid + 1, end2 = right;//有序序列2
	int i = left;
	while (begin1 <= end1 && begin2 <= end2)//注意结束条件为一个序列为空时就停止
	{
		if (a[begin1] < a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}

    //两序列不可能同时为空，将剩余元素合并
	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}

	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}

    //将合并后的序列拷贝到原数组中
    //在这里拷贝的原因是 保证返回到上一层递归后两个子序列中的元素是有序的
	int j = 0;
	for (j = left; j <= right; j++)
	{
		a[j] = tmp[j];
	}
}

// 归并排序递归实现
void MergeSort(int* a, int n)
{
    assert(a);
    //因为需要将两个有序序列合并，需借助额外数组
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc");
		exit(-1);
	}

	_MergeSort(a, 0, n - 1,tmp);

	free(tmp);
	tmp = NULL;
}
```
8.计数排序(了解)

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。操作步骤
1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中
动图演示：

** 代码如下：**
```
// 计数排序
void CountSort(int* a, int n)
{
    assert(a);
    // 创建计数数组，数组大小为原数组中最大值-最小值+1
	int max = a[0], min = a[0];
	int i = 0;
	for (i = 0; i < n; i++)
	{
		if (a[i] > max)
		{
			max = a[i];
		}
		if (a[i] < min)
		{
			min = a[i];
		}
	}
	int range = max - min + 1;
	int* count = (int*)malloc(sizeof(int) * range);
    // 初始化计数数组为0
	memset(count, 0, range * 4);

	// 统计次数
	for (i = 0; i < n; i++)
	{
		count[a[i] - min]++;
	}
    // 根据次数，进行排序
	int j = 0;
	for (i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			a[j++] = i+min;
		}
	}
    free(count);
    count = NULL;
}
```
注意：计数排序在排负数时，可将负数的类型转化成 unsigned int。

**数组中元素有正有负的情况时不适用计数排序。 **
计数排序的特性总结：
1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2. 时间复杂度：O(MAX(N,范围))
3. 空间复杂度：O(范围)
4. 稳定性：稳定
目标：
- [ ] 刷100道普及难度的题
- [ ] 普及组过初赛
- [ ] 25819
- [x] 加油！
最近活动
Stat
Rating

hanfengye (韩丰业)

个人简介

1.插入排序

2.希尔排序

3.选择排序

4.堆排序

5.冒泡排序

6.快速排序

7.归并排序

7.1递归实现

8.计数排序(了解)

最近活动

Stat

Rating

状态

开发

支持

hanfengye (韩丰业)

个人简介

1.插入排序

2.希尔排序

3.选择排序

4.堆排序

5.冒泡排序

6.快速排序

7.归并排序

7.1递归实现

8.计数排序(了解)

最近活动

Stat

Rating

状态

开发

支持

还没有账户？

登录