几个简单的排序

发布于 2023-07-09  231 次阅读


从软工毕业学长那里淘来一本《啊哈!算法》

然后跟着这本书学习学习,记录一下

桶排序

在生活中会遇到一些排序问题,比如站队列的时候要按身高排序、考试的名次要按分数排序、网上购物有时会按价格排序……

对于一组很简单的数字,桶排序无疑是最快最简单的

“桶”的理解:一个一维数组,大小为输入数字的最大值+1,数组的每一个下标都是一个标签,默认每一个数组元素的值都是0,当遍历到变量值等于下标值的时候呢,这个数组元素的值就自增,最后这个一维数组的值就有0或非0,只需要按下标大小取出元素值就能完成排序。

例如:输入5个数字,并从大到小输出

用C语言代码实现就是这样👇(编译器为VS 2022,一些关键字会有所不同

#include<stdio.h>
int main()
{
	int a[21];
	for (int i = 0; i < 21; i++)
		a[i] = 0;//初始化数组为0
	for (int i = 0; i < 5; i++)
	{
		int num;
		scanf_s("%d", &num);
		a[num]++;
	}

	for (int i = 20; i >= 0; i--)
	{
		if (a[i] != 0)
		{
			for (int j = 0; j < a[i]; j++)
			{
				printf("%d ", i);
			}
		}
	}
	return 0;
}

排序是可以实现了,那么想想有什么弊端?

桶排序是基于数组的下标实现的

那么肯定会存在这些问题:

  • 数字不能为负数或者小数
  • 数字不能大于数组的最大值-1
  • 数组也不能太大,不然会十分浪费空间

下面是一道有关桶排序的洛谷题:

给定一个字符串 s ,根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。

示例:

输入: s = "tree"
输出: "eert"
解释: 'e'出现两次,'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外,"eetr"也是一个有效的答案。

提示:

  • 1 <= s.length <= 5 * 105
  • s 由大小写英文字母和数字组成

实现代码如下:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char s[500001];
int a[130];
int cmp(char* p1, char* p2)
{
	int n = a[*p1];
	int m = a[*p2];
	if (n == m)
	{
		return *p1 - *p2;//下标一样则按照字母顺序排列
	}
	return m-n;//下标不一样则按照频率排列
}
int main()
{
	memset(a, 0, sizeof(a));
	scanf_s("%s", s,500001);
	int len = strlen(s);
	for (int i = 0; i < len; i++)
	{
		a[s[i]]++;
	}
	qsort(s, len, sizeof(char), cmp);
	printf("%s", s);
	
}

这里涉及到了qsort快速排序函数,不过主体还是桶排序

冒泡排序

冒泡的基本思想是:每次比较两个相邻的元素,然后根据大小交换

下面是动态图演示:

这种排序的核心就是双重for循环进行遍历比较

网上随便找一段代码:

#include<stdio.h>	
int main()
{
	int n[10] = { 25,35,68,79,21,13,98,7,16,62 };//定义一个大小为10的数组
	int i, j, temp;
	for (i = 1; i <= 9; i++)//外层循环是比较的轮数,数组内有10个数,那么就应该比较10-1=9轮
	{
		for (j = 0; j <= 9 - i; j++)//内层循环比较的是当前一轮的比较次数,例如:第一轮比较9-1=8次,第二轮比较9-2=7次
		{
			if (n[j] > n[j + 1])//相邻两个数如果逆序,则交换位置
			{
				temp = n[j];
				n[j] = n[j + 1];
				n[j + 1] = temp;
			}
		}
	}
	for (i = 0; i < 10; i++)
		printf("%d ", n[i]);

}

这是最基本的冒泡方法

可以在第一层for循环里设立判断,如果第二层for里没有进行交换则说明已经完成排序,就退出循环

不过当数组比较大的时候,使用冒泡排序并不是一个好的选择

快速排序

这是一种最常见的排序方式

基本思想:使用“分治”的策略,将序列分为两个子序列,并设立一个基准数(通常为第一个数字),比较基准数两侧的数据大小来排序(两侧并不是真的这个数字的两侧,而是序列的两侧)

比如说下面这种排列:

3 1 2 5 4 6 9 7 10 8

这时以数字6为基准数,左边都是小于6,右边则都是大于6,这是快速排序想要达到的效果

如何实现?

假如初始序列为这样:

6 1 2 7 9 3 4 5 10 8

分别从序列的两端开始探测,可以理解为两个指针向中间移动()

以6为基准数,先从右往左找一个小于6的数字,再从左往右找一个大于6的数字,并将其交换(不是同时进行的

于是第一遍之后就找到 7 和 5 两个数字并交换

形成新的序列:

6 1 2 5 9 3 4 7 10 8

然后重复这样的操作

这里就省略一部分

最终会遇到这样的数列:

6 1 2 5 4 3 9 7 10 8

可以看到

从左往右找大于的时候左指针会指向7

从右往左找小于的时候右指针会指向3

而这种排序要求的是右指针要先于左指针移动

于是右指针停留在 3 ,左指针在移动的时候会在3与右指针相遇!

看看 3 和基准数 6 的位置关系呢?

将 3 和 6 交换一下便能发现此时序列为:

3 1 2 5 4 6 9 7 10 8

6的左边全是小于,而右边全是大于

至此第一轮探测便真正结束,6回到了正确的位置

不过 6 两侧的序列还是无序的,需要进行排序

基于这种思想,可以通过以下C代码实现快速排序

#include<stdio.h>	
int a[101];
void quickSort(int left, int right)
{
	int i, j, k, temp;
	if (left > right)
		return;
	temp = a[left];//设立基准数,以左边的为基准数
	i = left;
	j = right;//可以看作两个指针,这里用下标来替代指针
	while (i != j)
	{
		while (a[j] >= temp && i < j)
		{
			j--;//从右往左找,直到找到小于,或者跑到最左端,当然跑到最左端的话那么这个数字就是最大了,直接放到right去
		}
		while (a[i] <= temp && i < j)
		{
			i++;
		}
		if (i < j)//没有相遇的情况,就交换
		{
			k = a[i];
			a[i] = a[j];
			a[j] = k;
		}
	}
	//最后归位基准数
	a[left] = a[i];
	a[i] = temp;

	quickSort(left, i - 1);
	quickSort(i + 1, right);//递归调用,分别处理两端序列
	return;
}
int main()
{
	int i, j, n;
	scanf_s("%d", &n);
	for (int c = 1; c <= n; c++)
	{
		scanf_s("%d", &a[c]);
	}
	quickSort(1, n);
	for (int i = 1; i <= n; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

至于为什么非得从右边开始找,可以这样理解👇

给出一组序列:

6 1 2 7 9

先从左边找到 7

再从右边开始,到 7 的时候两个指针就相遇咯

按照上面说的,相遇那么就该归位

那么得到:

7 1 2 6 9

能发现结果不对啊!

问题就在于:如果我们先从左边开始找,那么找到的那个数字一定是大于基准数的,交换之后就违背了左小右大的原则

所以:我们必须从右边开始,也就是从基准数的对面开始。

快速排序还是要依靠数组,不过相较于冒泡,每次的交换都是跳跃式的

不过当序列处于完全逆序的情况下(最坏的情况),快排的时间复杂度和冒泡是一样的

简单的学习了一下三个基本的排序方式

排序方式不止这三种:

  • 冒泡排序(Bubble Sort)
  • 插入排序(Insertion Sort)
  • 希尔排序(Shell Sort)
  • 选择排序(Selection Sort)
  • 快速排序(Quick Sort)
  • 归并排序(Merge Sort)
  • 堆排序(Heap Sort)
  • 计数排序(Counting Sort)
  • 桶排序(Bucket Sort)
  • 基数排序(Radix Sort)

后面再学习其他的罢

千里之行,始于足下
最后更新于 2023-07-10