算法入门1、
题1：发明于2300多年前的欧几里得算法：计算两个非负整数p和q的最大公约数
描述：若q是0，则最大公约数为p，否则，将p除以q得到余数r，p和q的公约数几位q和r的最大公约数（递归）
public static int gcd(int p,int q){
if(q==0)return p;
int r = p%q;
return gcd(q,r);
}
1. 选择排序：
描述：找到数组中最小的那个元素，其次将它和数组的第一个元素交换位置，再次，在剩下的元素中找到最小的元素，将它与第二个交换位置，以此类推~
public static int[] sortOrder(int [] a){
int len = a.length;
//每次筛选最小值,往前放
for(int i=0;i<len;i++){
//最小元素的索引，注意是索引！！要和值得关系进行相应转换！！
int min = i;
for(int j=i+1;j<len;j++){
//找出较小值
if(a[min]>a[j]){
//最小元素的索引
min=j;
}
}
//把最小值和a[i]交换
int tmp = a[i];
a[i]=a[min];
a[min]= tmp;
}
return a;
}
算法交换总次数为N，算法的时间效率取决于比较的次数，大约需要N*N/2此比较
太懒了，直接拍了一张照片表示排序流程了~~
2. 直接插入排序
基本思想：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入，插入排序所需的时间取决于输入中元素的初始顺序，例如：对一个很大且其中的元素已经有序（或接近有序）的数组进行排序将会比对随机顺序的数组或逆序数组进行排序要快得多。
public static int [] sortInsert(int[] a)
{
int len = a.length;
for(int i=0;i<len;i++)
{
//将a[i]插入到前面的序列中a[i-1]a[i-2]...
//前面的序列a[i-1]之前的序列是已经排好序的
for(int j=i;j>0&&a[j]<a[j-1];j--)
{
int tmp = a[j-1];
a[j-1]=a[j];
a[j]=tmp;
}
}
return a;
}
选择和插入排序都是N*N级别的排序方式，但插入比选择稍微快一些~
3. 希尔排序
思路： 希尔排序(缩小增量法) 属于插入类排序，使数组中任意间隔为h的元素都是有序的，即一个h有序数组就是h个互相独立的有序数组编织在一起组成的一个数组，若进行排序是h很大，则就能将h移动到很远的地方；
它是将整个无序列分割成若干小的子序列分别进行插入排序。希尔排序并不稳定，O(1)的额外空间，时间复杂度为O(N*(logN)^2)。最坏的情况下的执行效率和在平均情况下的执行效率相比相差不多。
希尔排序间隔序列函数 h = h * 3+ 1
希尔排序比插入排序快很多的原因：当h值很大时，数据项每一趟排序移动的元素个数少，但移动的距离很长，这是非常高效的；当h值减小时，每一趟排序移动的元素个数增加，但此时的数据项已经接近于他们最终排序后的位置，插入排序可以更有效；
public static int [] shellSort(int[]a){
int len = a.length;
int h=1;
while(h<len/3)
h=3*h+1;//1,4,13,40...选用序列 (3^k-1)/2
while(h>0)
{
/*
* j为什么从h开始？分割后的第一子序列应该是这样一个序列，0, h, 2h, 3h, ...
* 插入排序的while循环是从1开始的，因为第一个数始终有序，不需要比较，这个需要了解插入排序的算法，
* 所以比较是从第二个数据线，就是数组的第h个下标开始
*/
for(int i=h;i<len;i++)
{
//将a[i]插入到a[i-h],a[i-2h],a[i-3h]...中
for(int j=i;j>=h&&(a[j]<a[j-h]);j-=h)
{
//exch(j,j-h)
int tmp = a[j];
a[j] = a[j-h];
a[j-h]=tmp;
}
}
h=h/3;
}
return a;
}
4. 归并排序
所谓归并是指将两个或两个的有序数组合并成一个新的有序表
<自顶向下的归并排序代码>
public class MergeSort {
public static void main(String[] args) {
int [] a = {0,1,4,9,5,1,0,4,3,6,8,2,4,1,5,8};
sort(a);
}
public static void sort(int [] a){
int[] aux = new int[a.length];//
sort(a,0,a.length-1,aux);
for(int i=0;i<a.length;i++){
System.out.println(a[i ]);
}
}
public static void sort(int[]a,int lo,int hi,int[] aux){
if(hi<=lo) return;
int mid = lo + (hi-lo)/2;
sort(a,lo,mid,aux);
sort(a,mid+1,hi,aux);
merge(a,lo,hi,mid,aux);
}
public static void merge(int[]a,int lo,int hi,int mid,int[] aux){
int i = lo,j=mid+1;
//数组元素复制到辅助空间中
for(int k=lo;k<=hi;k++){
aux[k]=a[k];
}
for(int k=lo;k<=hi;k++){
if(i>mid) a[k]=aux[j++];
else if(j>hi) a[k]=aux[i++];
else if(aux[j]<aux[i]) a[k]=aux[j++];
else a[k]=aux[i++];
}
}
}
为什么不把数组aux[ ]声明为merge()方法的局部变量？
为了避免每次归并排序时，即使是归并很小的数组，都创建一个新的数组，如果这么做，那么创建新数组将成为归并排序运行时间的主要部分，更好的方式是将aux[ ]作为sort()方法的局部变量，并将它作为参数传递给merge
定义一个长度为16的数组，其递归的过程如下：
sort(a,0,7) lo=0 hi=15 mid=7
sort(a,0,3) lo=0 hi=7 mid=3
sort(a,0,1) lo=0 hi=3 mid=1
sort(a,0,0) lo=0 hi=1 mid=0
sort(a,1,1) lo=0 hi=1 mid=0
merge(a,0,1,0)
sort(a,2,3) lo=0 hi=3 mid=1
sort(a,2,2) lo=2 hi=3 mid=2
sort(a,3,3) lo=2 hi=3 mid=2
merge(a,2,3,2)
merge(a,0,3,1)
sort(a,4,7) lo=0 hi=7 mid=3
sort(a,4,5) lo=4 hi=7 mid=5
sort(a,4,4) lo=4 hi=5 mid=4
sort(a,5,5) lo=4 hi=5 mid=4
merge(a,4,5,4)
sort(a,6,7) lo=4 hi=7 mid=5
sort(a,6,6) lo=6 hi=7 mid=6
sort(a,7,7) lo=6 hi=7 mid=6
merge(a,6,7,6)
merge(a,4,7,5)
merge(a,0,7,3)
sort(a,8,15) lo=0 hi=15 mid=7
sort(a,8,11) lo=8 hi=15 mid=11
sort(a,8,9) lo=8 hi=11 mid=9
sort(a,8,8) lo=8 hi=9 mid=8
sort(a,9,9) lo=8 hi=9 mid=8
merge(a,8,9,8)
sort(a,10,11) lo=8 hi=11 mid=9
sort(a,10,10) lo=10 hi=11 mid=10
sort(a,11,11) lo=10 hi=11 mid=10
merge(a,10,11,10)
merge(a,8,11,9)
sort(a,12,15) lo=8 hi=15 mid=11
sort(a,12,13) lo=12 hi=15 mid=13
sort(a,12,12) lo=12 hi=13 mid=12
sort(a,13,13) lo=12 hi=13 mid=12
merge(a,12,13,12)
sort(a,14,15) lo=12 hi=15 mid=13
sort(a,14,14) lo=14 hi=15 mid=14
sort(a,15,15) lo=14 hi=15 mid=14
merge(a,14,15,14)
merge(a,12,15,13)
merge(a,8,15,11)
merge(a,0,15,7)
![查找算法之二分查找查找算法之二分查找[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)