常用算法 | Kyren's Blog

一、C语言常用算法

#include <stdio.h>
#include <stdlib.h>

//C语言中文网-算法 http://c.biancheng.net/cpp/u/c14/
void printArray(int arr[],int length);
int binarySearch0(int a[], int n, int findNum);
int binarySearch(int a[], int low, int high, int findNum);
void bubble_sort(int a[], int n);
void select_sort(int a[],int n);

int main(int argc, char *argv[]) {
	printf("hello world！");
	int arr[] = { 1, 2,5, 3, 4, 8, 7, 6, 9 };
	int sz = sizeof(arr) / sizeof(arr[0]); //取得数组所占内存大小，再除以一个元素占用的内存大小来计算数组长度。
	int num = 7;
	int ret0=binarySearch0(arr, sz, num); //二分法-普通
	int ret=binarySearch(arr,0,sz, num);//二分法-递归

	printArray(arr,sz);
	bubble_sort(arr,sz);
	printArray(arr,sz);
}

void printArray(int arr[],int length){
	//不能再函数里获取数组长度
	//http://www.cnblogs.com/litifeng/p/7065384.html
	printf("\n");
	for(int i=0;i<length;i++){
		printf("%d->",arr[i]);
	}
}

/** 
  * 二分查找普通实现。 
  * @param a 有序数组 
  * @param findNum 查找元素 
  * @return  不存在返回-1 
  */ 
/**
折半查找的原理：
1> 数组必须是有序的
2> 必须已知min和max（知道范围）
3> 动态计算mid的值，取出mid对应的值进行比较
4> 如果mid对应的值大于要查找的值，那么max要变小为mid-1
5> 如果mid对应的值小于要查找的值，那么min要变大为mid+1
*/
int binarySearch0(int a[], int n, int findNum){
	int low = 0;
	int high = n - 1;
	while(low<= high){
		int mid = (low + high)/2;//此处一定要放在while里面
		int midVal = a[mid];
		if(midVal<findNum)
			low = mid + 1;
		else if(midVal>findNum)
			high = mid - 1;
		else
			return mid;
	}
	return -1;
}

/**二分法-递归方法*/
int binarySearch(int a[], int low, int high, int findNum) {  
	int mid = ( low + high ) / 2;       
	if (a[mid] == findNum) {  
		return mid;  
	}  

	if (low >= high) {  
		return -1;  
	} else{
		 if (a[mid]<findNum) 
			return binarySearch(a, mid + 1, high, findNum);  
		 else if (a[mid]>findNum) 
			return binarySearch(a, low, mid - 1, findNum);  
		 else
			return mid;   
	}
}  


/**
 * desc: 冒泡排序
 *	1. 进行两次遍历，第一个for是从 0 - arr.length-1, 第二次是从0到 arr.length - i - 1;
 * 	2. 每一趟之后最后一个是最大值；
 * 
 * 时间复杂度: 最好情况o(n), 最差o(n^2), 平均o(n^2)
 * 
 * 空间复杂度: 0(1)
 */
void bubble_sort(int a[], int n)
{
	int i, j, temp;//temp中间变量
	for (j = 0; j < n - 1; j++)  //一定进行N-1轮比较
	{
		for (i = 0; i < n - 1 - j; i++) //每一轮比较前n-1-i个，即已排序好的最后i个不用比较
		{
			if(a[i] > a[i + 1]) //升序--降序if(a[i] < a[i + 1])
			{   //如果前面一个数比后面数大，交换两个数的值  
				temp = a[i];
				a[i] = a[i + 1];
				a[i + 1] = temp;
			}
		}
	}
}



/**
 * desc: 选择排序
 *	1. 分为两趟，第一趟从0-arr.length-1, 第二趟从i + 1到arr.length
 *	2. 每趟的结果是最小值在最左边
 * 
 * 时间复杂度：最好情况o(n^2), 最差o(n^2), 平均o(n^2)
 * 
 * 空间复杂度：o(1)
 */
void select_sort(int a[],int n)//n为数组a的元素个数
{
	//进行N-1轮选择
	for(int i=0; i<n-1; i++) //趟数
	{
		int min_index = i; 
		//找出第i小的数所在的位置
		for(int j=i+1; j<n; j++) //比较次数
		{
			if(a[j] < a[min_index])
			{
				min_index = j;
			}
		}
		//将第i小的数，放在第i个位置；如果刚好，就不用交换
		if( i != min_index)
		{
			int temp = a[i];
			a[i] = a[min_index];
			a[min_index] = temp;
		}
	}
}

//在程序里，交换2个数，我使用了异或来处理。这个可以根据个人喜好。为了避免产生临时变量，可以使用如下几种方式来交换2个数：

二、交互2个数

在程序里，交换2个数，我使用了异或来处理。这个可以根据个人喜好。为了避免产生临时变量，可以使用如下几种方式来交换2个数：

void swap(int &a, int &b) {
  int temp = a;
  a = b;
  b = temp;
}

void swap(int &a, int &b) {
  a = a ^ b;
  b = b ^ a;
  a = a ^ b;
}

void swap(int &a, int &b) {
   a=a+b;
   b=a-b;
   a=a-b;
}

https://stackoverflow.com/questions/46463778/xcode-9-an-error-occurred-uploading-to-the-itunes-store

算法

排序算法图形化比较：快速排序、插入排序、选择排序、冒泡排序

21天C语言代码训练营（第一天）