算法笔记—1
#include <iostream>
using namespace std;
int fast[10] = { 0 };
void Simple_barrel_sort()
{
/*
简单的桶排序: 随机输入8个0-10的数字并将其排序
原理: 因为数组下标是已经排序好的数字数列，所以使用一维数组a[n]代表每一个数字；
例如：
a[0]代表数字0；
a[1]代表数字1；
.
.
.
a[n]代表数字n；
初始化数组a[0] = {0}；
随机输入一个数字m，将m作为数组的下标并将a[m]+1；（注意：m < n，当m >= n时会出现数组越界导致程序崩溃）
时间复杂度是O(n)
这种方法在数量过大时会显得十分臃肿。例如:当输入数字大小达到10000+时，就需要10000+个变量。十分占空间。
*/
int barrel[10] = { 0 };
/*
系统在调用rand（）之前都会自动调用srand()，如果在srand()里给参数
seed指定了一个值（这里指定的值是当前时间），那么 rand()就会将
seed的值作为产生伪随机数的初始值；而如果用户在rand()前没有调用过srand()，
那么系统默认将1作为伪随机数的初始值，如果初始值是此时的1或是其他定值，
那么每次rand()产生的随机数序列都是一样的，这也就是所谓的“伪随机数”。
*/
srand((unsigned int)time(0));
for (int i = 0; i < 8; i++)
{
int num = rand()%10;
printf("%d\t", num);
barrel[num]++;
}
printf("\n");
/*
通过for循环依次判断数组a[0]-a[n]的值,每个数字有几次出现就打印几次
*/
for (int i = 0; i < 10; i++)//顺序打印
{
for (int j = 1; j <= barrel[i]; j++)
{
printf("%d\t", i);
}
}
printf("\n");
for (int i = 9; i >= 0; i--)//倒序打印
{
for (int j = 1; j <= barrel[i]; j++)
{
printf("%d\t", i);
}
}
}
void bubbling_sort_0()
{
/*
冒泡排序
基本思想：比较每一对相邻的元素，并且按照规则改变其先后顺序。
例如：4,12,5,1,8按照从大到小排序
从第一个开始比较
4和12比较，12大，将12和4的位置进行交换
12,4,5,1,8
4和5比较，交换位置
12,5,4,1,8
4和1比较，不需要交换位置
1和8比较，交换位置
12,5,4,8,1这样我们就确定了最小的数
再次从第一个开始比较
12和5比较，不需要交换位置
5和4比较，不需要交换位置
4和8比较，交换位置
12,5,8,4,1我们又得到第二小的数
再次从第一个开始比较
12和5比较，不需要交换位置
5和8比较，交换位置
12,8,5,4,1得到第三小的数
再次从第一个开始比较
12和8比较
12,8,5,4,1得到一个完整的从大到小的数列
最后一次是必须的，因为有可能会出现8,12,5,4,1的现象
假如有n个数需要排序
第一遍是要比较n-1次
第二遍是要比较n-2次
.
.
.
第n-1遍是要比较1次
对数列求和可（n^2-n）/2
不难看出时间复杂度是O(n^2)
*/
int bubbling[10] = { 0 };
srand((unsigned int)time(0));
for (int i = 0; i < 10; i++)
{
bubbling[i] = rand() % 10;
printf("%d\t", bubbling[i]);
}
printf("\n");
for (int i = 0; i < 9; i++)//顺序打印
{
for (int j = 0; j < 9 - i; j++)
{
if (bubbling[j] < bubbling[j + 1])
{
int temporary = bubbling[j];
bubbling[j] = bubbling[j + 1];
bubbling[j + 1] = temporary;
}
}
}
/*
for (int i = 0; i < 9; i++)//倒序打印
{
for (int j = 0; j < 9 - i; j++)
{
if (bubbling[j] > bubbling[j + 1])
{
int temporary = bubbling[j];
bubbling[j] = bubbling[j + 1];
bubbling[j + 1] = temporary;
}
}
}*/
printf("\n");
for (int i = 0; i < 10; i++)
{
printf("%d\t", bubbling[i]);
}
}
void fast_sort_0(int left, int right)
{
/*
快速排序：也是通过交换位置实现，不过交换位置的跨度大。在最糟糕的情况下时间复杂度和冒泡排序一样
基本思想：基于二分的思想，通过设置基准数，然后将基准数一一归位。
例如有五个数
5,4,1,9,2
将第一个数字5设置为基准数
再分别使用哨兵i（从左向右移动），j（从右向左移动）
开始将i=5,j=2，j先移动，i在移动（右边先移动，使得i，j相遇位置小于基准值.左边始终小于基准值右边始终大于基准值）
当j找到比5小的数停下，i找到比5大的数停下，将俩个数进行交换。随后在进行移动
当i，j碰到一起时将5和这个数进行交换
2,4,1,5,9
左边重复上述
1,2,4,5,9
平均时间复杂度是O（nlogN）
*/
int i = left, j = right, k = fast[left], temporary;
if (i > j)//输入正确值判断
{
return;
}
while (i != j)
{
while (fast[j] >= k && i < j)//逻辑正确判断
{
j--;
}
while (fast[i] <= k && i < j)
{
i++;
}
if (i < j)
{
temporary = fast[i];
fast[i] = fast[j];
fast[j] = temporary;
}
}
fast[left] = fast[i];
fast[i] = k;
fast_sort_0(left, i - 1);
fast_sort_0(i + 1, right);
}
void book_2006()
{
/*
将书籍去重并且排序
时间复杂度的最佳方案使用桶排序
*/
int book[10] = { 0 }, barrel[20] = { 0 };
srand((unsigned int)time(0));
for (int i = 0; i < 10; i++)
{
book[i] = rand() % 20;
printf("%d\t", book[i]);
}
printf("\n");
for (int i = 0; i < 10; i++)
{
barrel[book[i]]++;
}
for (int i = 0; i < 20; i++)
{
if (barrel[i]) printf("%d \t", i);
}
}
void fast_sort_play()
{
srand((unsigned int)time(0));
for (int i = 0; i < 10; i++)
{
fast[i] = rand() % 10;
printf("%d\t", fast[i]);
}
printf("\n");
fast_sort_0(0, 9);
for (int i = 0; i < 10; i++)
{
printf("%d\t", fast[i]);
}
}
int main()
{
/*
主函数标准形式：main(int argc, char *argv[]=>char **argv)
第一个参数是命令行传入参数的个数，第二个是传入的数据
*/
book_2006();
}