一、算法

1、概念

問題的求解方法

2、算法的特性和設計要求

算法的特性：

確定性? ? ? ? 有窮性? ? ? ? 輸入輸出? ? ? ? 可行性

設計要求：

正確性? ? ? ? 高效性????????低存儲????????健壯性? ? ? ? 可讀性

3、時間復雜度O(n)

用于評估程序執行所需的時間

O(n)記法：? ? ? ? 只保留最高階部分

例題：

?

?4、快速排序

思想：

? ? ? ? 每次取待排序中的一個元素作為基準，將序列分為比基準大和比基準小兩個部分

? ? ? ? 再分對這兩個部分別進行快速排序，直到每個部分都只有一個元素時，結束快速排序

#include <stdio.h>
//一次快排需要返回最后基準的位置
int one_sort(int *p,int low,int high)
{int base = *(p+low);while(high>low){//high一側的數據比基準更大while(*(p+high)>=base&&high>low){high--;}*(p+low) = *(p+high);while(*(p+low)<=base&&high>low){low++;}*(p+high) = *(p+low);}*(p+low)=base;   //將基準放在中間位置return low;
}
void sort(int *p,int low,int high)
{int ret;if(high>low)   //說明序列中不止一個元素{ret = one_sort(p,low,high);sort(p,low,ret-1);sort(p,ret+1,high);}
}
int main(int argc, const char *argv[])
{int arr[]={50,36,66,76,36,12,25,95};sort(arr,0,sizeof(arr)/sizeof(int)-1);for(int i=0;i<sizeof(arr)/sizeof(int);i++){printf("%d\n",arr[i]);}return 0;
}

?5、直接插入排序

思想：

? ? ? ? 假定序列中的元素有序（只有一個元素時，序列一定時有序的），將其他的元素插入到已經排好的序列中并排序。

#include <stdio.h>
void insert_sort(int *p,int len)
{int i,j,temp;//外層循環獲取要插入的每一個元素for(i=1;i<len;i++){//把每次要插入的數據保存temp = p[i];//內層循環找到元素應該插入的位置//因為是順序結構，插入的同時需要保證其他數據不變//需要將插入位置后面的元素后移//后移的就是比我插入元素更大的數for(j=i;j>0&&p[j-1]>temp;j--){p[j] = p[j-1];}//退出循環說明找到了要插入的位置p[j] = temp;}
}
int main(int argc, const char *argv[])
{int arr[]={50,36,66,76,36,12,25,95};int len = sizeof(arr)/sizeof(arr[0]);insert_sort(arr,len);for(int i=0;i<len;i++){printf("%d\n",arr[i]);}return 0;
}

二、查找算法

根據給定關鍵字，在序列中查找該關鍵字的操作

1、二分查找（條件：數列有序）

思想：

????????每次都使用序列中的中間值和給定的關鍵字比較，

????????中間值比關鍵字更大就去比中間值更小的一側查找，

? ? ? ? 中間值比關鍵字更小就去比中間值更大的一側查找。

#include <stdio.h>
int half_search(int *p,int start,int end,int key)
{int mid;//查找算法，即使只有一個數也要判斷while(end>=start){//找到中間值mid = (start+end)/2;   //中間值的下標if(p[mid]>key){end = mid-1;  //更新序列的終止位置}else if(p[mid]<key){start = mid+1;  //更新序列的起始位置}else if(p[mid]==key){return mid;}}
}
int main(int argc, const char *argv[])
{int arr[]={50,36,66,76,36,12,25,95};int len = sizeof(arr)/sizeof(arr[0]);printf("%d\n",half_search(arr,0,len-1,76));return 0;
}

2、哈希表

除留余數法：除數的確定