第一章 排序
先来看看书中提到的三种排序方法.
- 桶排序
- 冒泡排序
- 快速排序
1.桶排序.
桶排序在排序中是比较快的一种排序算法.
它的时间复杂度只有: O(N+M).
有这样一个🌰:
你有10个桶, 每个桶一个编号, 1~10.
另外你有10个球, 球的编号是随机的(可以有重复的编号, 编号范围是1~10), 比如, 2,3,3,5,6,7,3,1,4,8.
桶排序, 个人觉得其实就是一个分类的思想, 把不同类型的分开, 把相同类型的放在一起.
就好比上面的情况, 其实就是把球进行分类, 把对应球放到对应编号的桶里面.
我们来看看桶排序是怎么做的?
- 首先清空桶
// 假设有101个桶, 从1开始
for(int i = 1; i <= 100; i++)
{
buckets[i] = 0;
}
2.输入球的编号
scanf("%d", &n); //输入多少个球
for(int i = 1; i <= n; i++)
{
scanf("%d", &t); // 输入的球的编号, ,这个n必须 <= 100, 这样才能分类放在对应的桶里
buckets[t]++; // 把球放入到对应桶里面
}
3.数数每个桶里有多少个球
for(int i = 1; i <= n; i++)
{
for(int j = ; j <= buckets[i]; j++)
{
printf("%d ", i); // 输出对应桶里面有多少的球
}
}
至此, 桶算法结束.
大家可以看到, 桶算法非常快, 基本上数一遍就可以, 得出结果.
但是它也有一个 非常致命的缺点, 那就是桶的数量.
如果说我们需要排序的数是非常大的,那么我就需要给到非常大编号的桶, 也就是需要非常多的桶.
坏🌰:
某种情况, 我仅仅需要排序三个数据, 0, 3, 34322543543
第三个数是一个非常大的数, 那么真的需要 34322543544 个桶吗?
显然, 这是极大的浪费了内存的空间.
所以, 对桶排序的小结:
1.速度很快, 时间复杂度为: O(N+M).
2.缺点: 耗内存, 以空间换时间.
2.冒泡排序.
冒泡排序, 除了名字比较好听意外, 基本不太用.
时间复杂度: O(N^2)
可以看到它的时间复杂度是N^2, 是指数级别的.就是说, 当你的N越大, 就越慢. 而且不是一般的慢, 是相当的慢, 成指数级别增长.
举个🌰:
初始数据如下:
2,3,3,5,6,7,3,1,4,8
第一遍扫码后, 把最少的数据往后面排:
3,3,5,6,7,3,2,4,8,1
第二遍扫描后:
3,5,6,7,3,3,4,8,2,1
...以此类推, 知道排序完成
8,7,6,5,4,3,3,3,2,1
参考代码
#include <stdio.h>
int main()
{
int a[101], i,n, temp;
for(i = 1; i <= 100; i++)
a[i] = 0;
scanf("%d", &n); // n个数
for(i = 1; i <= n; i++)
{
scanf("%d", &a[i]); // 输入数据
}
// 核心代码
for(i = 1; i <= n-1; i++) //
{
for(j = 1; j <= n-i; j++) // 只需要排序n-i的数
{
if (a[j] < a[j+1]) // 比较, 把大的数往前移动
{
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
// 最后的结果是, 8,7,6,5,4,3,3,3,2,1
for(i = 1; i <= n; i++)
{
printf("%d ", a[i]);
}
getchar();
return 0;
}
3.快速排序.
顾名思义, 既然是快速, 就是很快喽.
时间复杂度为: O(NlogN), 对数级别.
之前的桶排序是一种 分类思想, 那么快速排序就是一种 分治思想.
其实也是很简单, 基本步骤:
1.设置基本点
2.从数组两端进行扫描,
i) 从右边开始对比基准点, 如果小于就停下, 记录 i 位置
ii) 从左边开始对比基准点, 如果大于就停下, 记录 j 位置
iii) 交换 i, j 位置的数据
iv) 重复i, ii iii, 直到 i == j
v) 交换基准数和当前i位置的值
vi) 把数组分割两部分, (left, i-1) , (i+1, right), 两部分, 继续比较, 直到需要比较的数组长度length=1
参考代码
quickSort(int left, int right)
{
int i, j, temp, n;
if (left >= right) return; // 当只有一个数据的时候, 不需要比较直接返回
temp = a[left];
i = left;
j = right;
while( i != j) {
while (a[j] > temp && i < j) j--;
while (a[i] < temp && i < j) i++;
// 如果没有碰到, 就需要交换
if (i < j) {
n = a[i];
a[i] = a[j];
a[j] = n;
}
}
a[left] = a[i];
a[i] = temp; // 交换基准值
// 递归调用(分治), 再进行比较
quickSort(left, i-1);
quickSort(i+1, right);
}
再来个实际的🌰:
小哼买书, 每本书都有ISBN号, 而且每本书的ISBN号都是唯一且不重复的.
这里的关键就是, 去重和排序.
桶排序
排序的过程, 也就可以去除重复的ISBN号.
#include <stdio.h>
int books[1001], i, j, temp;
int main()
{
// 初始化book状态
for(i = 0; i <= 1000; i++)
books[i] = 0;
scanf("%d", n); // 输入书本数量
for(i = 1; i <= n; i++)
{
scanf("%d", &temp);
books[temp] = 1; // 读入对应的ISBN, 标记对应book状态
}
for(i = 0; i < 1000; i++)
{
if (books[i] != 0)
printf("%d ", i);
}
getchar();
return 0;
}
快速排序
1.先排序
2.去重输出
#include <stdio.h>
int books[1001], i, j, temp;
int main()
{
int n, i;
scanf("%d", &n);
for( i = 1; i <= n; i++)
{
scanf("%d", &temp);
books[i] = temp;
}
quickSort(books, 1, n); // 数组排序
printf("%d ", a[1]);
for(i = 2; i <= n; i++)
{
if (a[i] != a[i-1]) // 去重输出
printf("%d ", a[i]);
}
}
void quickSort(int a[], int left, int right)
{
int i, j, base, temp;
if (left > right) return;
base = a[left];
i = left;
j = right;
// 扫描对比基准数
while(i != j)
{
while(a[i] > base && i < j) j--;
while(a[j] < base && i < j) i++;
if (i < j)
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
// 交换基准数的位置
a[left] = a[i];
a[i] = temp;
quickSort(left, i-1);
quickSort(i+1, right);
}
至此, 第一章里三个主要算法介绍到这里.
1.桶排序
特点: 速度快, 内存消耗大, 空间换时间.
2.冒泡排序
特点: 速度慢, 除了除了名字好听.
3.快速排序
特点: 速度快, 时间复杂度:O(NlogN),
可以看到每个中排序算法都是有各自的特点, 使用那种算法, 还是需要根据不同的场景, 来发挥算法的特点.
