算法入門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=)