算法笔记—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,84和5比较，交换位置12,5,4,1,84和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();
}