每日四个小算法 --- day1

一

/*

*/

将b的数分情况考虑：

当 b == 0时，返回 1

当 b == 1时候， 返回 或者 a <= 1时候返回 a %1000，此时如果 a小于等于1的话

当 b == 2时候， 返回 a*a %1000

当 b 大于等于三时候，分两种情况

当 b为奇数和b为偶数时候,根据公式 a^b = (a^(b/2))^2进行递归

代码：

int getNumber(int a, int b){	if(b == 0)		return 1;	else if(a <= 1 || b == 1){		return a%1000;	}else if(b == 2){		return a*a%1000;	}else if(b & 0x01 == 1)//此时 b 大于等于 3 且是奇数	{		return((getNumber(getNumber(a, b/2), 2)*a) % 1000); // a^3 = a*a^2	}else{		return ((getNumber(getNumber(a, b/2), 2)) % 1000);	}}二马桶排序
/*	马桶排序：		特点：数组的下标是该数字，数组的元素是该数字出现的频率。		可以将待排序的数字看成是马桶，在里面进行插旗运算。*/void sort(int *score, int n){	int newScore[9] = {0};	int i = 0;	int j = 0;	for(i  = 0; i < 5; i++){		newScore[score[i]]++;	}	for(i = 0; i < 9; i++){		if(newScore[i] != 0){			for(j = 0; j < newScore[i]; j++){//数组元素是数字出现的频率				PRintf("%d ", i);//下标是真实出现的数字			}		}	}}三冒泡排序
/*		冒泡排序：				5个数字进行排序，第一趟比较这个五个数字，并且比较的时候进行交换。				第一趟选出最小的数字放到最高位。				第二趟从前四个数字选出最小的位置，放到了第四位。				第三趟就是从前三个数字选出最小的，放到了第三位。				第四趟就是.......................,放到了第二位。				外循环控制要遍历数组的次数，内循环控制比较数组起始位置和比较次数。
时间复杂度： o(n^2)*/void sort(int *a, int n){	int i = 0;	int j = 0;	int temp = 0;	for(i = 0; i < n-1; i++){		for(j = 0; j < n-1-i; j++){			if(a[j] > a[j+1]){				temp = a[j];				a[j] = a[j+1];				a[j+1] =temp;			}		}	}}四：快速排序
/*	快速排序：		首先定义基准变量为temp = a[0];		一次快速排序的过程：首先确定 left < right		然后定义左侧的数字为基准数，int temp = a[left];		假设从小到大比较，则基准数左侧要小于基准数，基准数右侧的数，大于基准数。		首先每次一定要从基数的对面开始，假设J是基数的对面,i是奇数,则如果a[j] >= temp,执行j--		就是找到一个小于基数的,这个数字不应该放在基数的对侧，应该放在同侧。		然后在基数的同侧找一个比基数大的数字,这个数字不应该在基数的同侧。		然后进行交换，最后当 i == j 的时候,这个数组已经被遍历完成,此时将基数放在中间。		对基数左侧的数字进行上述过程。		对基数右侧的数字进行上述过程。*/void quickSort(int *a, int left, int right){	int temp; //基准数	int t;//交换的时候使用	int i = left;//记录基数同侧的数	int j = right;//记录基数对侧的数	if(left > right)		return;//递归结束条件	temp = a[i];//左侧是基准值	while(i != j)//进行一次快速排序的过程,结束条件是 i , j	{		//每次先从基准数的对侧开始,要就找出小于 基准数的		while(temp <= a[j] && i < j){			j--;		}			while(temp >= a[i] && i < j){			i++;		}		if(i != j){			t = a[i];			a[i] = a[j];			a[j] = t;		}	}	//一次完成后将基数归位	a[left] = a[i];	a[i] = temp;	quickSort(a, left, i-1);//从基数左侧开始排序。	quickSort(a, i+1, right);//从基数右侧的开始排序。}