交换排序
1.冒泡排序
算法思想
1.将所有元素放入数组中；
2.从第一个元素开始，依次将相邻的两个元素比较，若前者大于后者则交换；
3.重复第2步，直到没有交换为止。
程序实现
void sort(int *a, int n) { int i, j, t, ok; for(i=0; i<n-1; i++){ ok=1; for(j=0; j<n-1-i; j++) if(a[j]>a[j+1]){ t=a[j]; a[j]=a[j+1]; a[j+1]=t; ok=0; } if(ok) break; } }
void sort(int a[], int n) { int i, t, ok; if(n==1) reurn; else{ for(i=0;i<n-1;i++) if(a[i]>a[i+1]){ t=a[i]; a[i]=a[i+1]; a[i+1]=t; ok=0; } if(ok) return; else sort(a,n-1); } }
2.交换排序的另一种方法
void sort(int temp_array[ ],int n) { int i,j,t; for(i=0;i<n-1;i++) for(j=i+1;j<n;j++) if(temp_array[i]> temp_array[j]){ t=temp_array[i]; temp_array[i]=temp_array[j]; temp_array[j]=t; } }
选择排序
算法思想
记住每趟比较中最小的数据下标，最后将最小元素与起始元素交换，这样每趟只交换一次。
程序实现
void sort(int temp_array[ ],int n) { int i,j,point,t; for(i=0;i<n-1;i++){ point=i; for(j=i+1;j<n;j++) if(temp_array[point]> temp_array[j])
point=j; if(point!=i){ t=temp_array[point]; temp_array[point]=temp_array[i]; temp_array [i]=t; } } }
插入排序
算法思想
1.新建一个空列表，用于保存有序数列；
2.从原数列取出一个数插入有序列表中，使其仍保持有序状态；
3.重复第2步，直至原数列为空。
程序实现
void sort(int a[],int n) { int i,j,t; for(i=1;i<n;i++){ t=a[i]; //第i+1个数 for(j=i-1;a[j]>t&&j>=0;j--) //第j个数小于t或所有数都大于t a[j+1]=a[j]; //大于t的数向后挪动 a[j+1]=t; //将t插入第j+1位置 } }
查找算法
线性查找法：时间复杂度O(n)级
for(i=0;i<ARRAY_NUM;i++) if(x[i]==key) { m=i; break; } if(m!=-1)
printf(“found! %d”,m); else
printf(“not found!”);
折半查找法：时间复杂度O(log2n)级
while(low<=high){ mid=(low+high)/2; if(a[mid]==key){ k=mid; break; } if(key<a[mid]) high=mid-1; else low=mid+1; }
int search(int x[ ],int low,int high,int key) { int mid; mid=(low+high)/2; if(x[mid]==key)
return mid; if(low>=high)
return –1; else if(key<x[mid]) return search(x,low,mid-1,key); else return search(x,mid+1,high,key); }
原文：https://www.cnblogs.com/yuukirito/p/14776405.html