菜鸟代码学习散点总结（四）

特别友情提示：复习用的，下列出现的排序，树等代码网上已经烂大街了。。。JAVA大法。。

一、几大排序

1、冒泡排序

 1 public static void bubbleSort(int []a){
 2     for(int i=0;i<a.length-1;i++){
 3         for(int j=i+1;j<a.length;j++){
 4             if(a[i]>a[j]){
 5                 int temp=a[i];
 6                 a[i]=a[j];
 7                 a[j]=temp;
 8             }
 9         }
10     }
11 }

2、选择排序

 1 public static void chooseSort(int []a){
 2     for(int i=0;i<a.length;i++){
 3         int least=a[i];
 4         for(int j=i+1;j<a.length;j++){
 5             if(a[j]<least)
 6                 least=j;
 7         }
 8         int temp=a[i];
 9         a[i]=a[least];
10         a[least]=temp;
11     }
12 }

3、快速排序

public static void quickSort(int []a,int l,int r){
    if(l<r){
        int i=l,j=r,X=a[l];
        while(i<j){
            while(i<j&&a[j]>=X)
                j--;
            if(i<j)
                a[i++]=a[j];
            while(i<j&&a[i]<X)
                i++;
            if(i<j)
                a[j--]=a[i];
        }
        a[i]=X;
        quickSort(a, l, i-i);
        quickSort(a, i+1, r);
    }
}

4、插入排序

public static void insertSort(int []a){
    int j,target;
    for(int i=1;i<a.length;i++){
        j=i;
        target=a[i];
        while(j>0&&a[j-1]>target){
            a[j]=a[j-1];
            j--;
        }
        a[j]=target;
    }
}

5、希尔排序

public static void shellSort(int []a){
    int len=a.length, h=0,target,j;
    while(h<len/3){
        h=h*3+1;
    }
    while(h>0){
        for(int i=h;i<len;i+=h){
            j=i;
            target=a[i];
            while(j>h-1&&a[j-h]>target){
                a[j]=a[j-h];
                j-=h;
            }
            a[j]=target;
        }
        h=(h-1)/3;
    }
}

6、堆排序

 1 public static void buildMaxHeap(int []a,int lastIndex){
 2     for(int i=(lastIndex-1)/2;i>=0;i--){
 3         int k=i;
 4         //当前k节点的子节点存在时
 5         while(k*2+1<=lastIndex){
 6             int bigIndex=k*2+1;
 7             if(bigIndex<lastIndex)
 8                 bigIndex=a[bigIndex]>a[bigIndex+1]?bigIndex:bigIndex+1;
 9             if(a[k]<a[bigIndex]){
10                 swap(a,k,bigIndex);
11                 k=bigIndex;
12             }else{
13                 break;
14             }
15         }
16     }
17 }
18 public static void StackSort(int []a){
19     int len=a.length;
20     for(int i=0;i<len-1;i++){
21         buildMaxHeap(a, len-1-i);
22         swap(a,0,len-1-i);
23     }
24 }

7、归并排序

 1 public static void mergearray(int []a,int first,int mid,int last,int[]temp){
 2     int i=first,m=mid;
 3     int j=mid+1,n=last;
 4     int k=0;
 5     while(i<=m&&j<=n){
 6         if(a[i]<=a[j])
 7             temp[k++]=a[i++];
 8         else
 9             temp[k++]=a[j++];
10     }
11     while(i<=m)
12         temp[k++]=a[i++];
13     while(j<=n)
14         temp[k++]=a[j++];
15     for(i=0;i<k;i++){
16         a[first+i]=temp[i];
17     }
18 }
19 public static void mergeSort(int[]a,int first,int last,int[] temp){
20     if(first<last){
21         int mid=(first+last)/2;
22         mergeSort(a, first, mid, temp);
23         mergeSort(a, mid+1, last, temp);
24         mergearray(a, first, mid, last, temp);
25     }
26 }

8、排序算法总结

二、二分查找

 1 public int binarySearch(int[]a,int x){
 2     int start=0;
 3     int end=a.length;
 4     while(start<=end){
 5         int mid=(start+end)/2;
 6         if(a[mid]==x)
 7             return mid;
 8         else if(x<a[mid])
 9             end=mid-1;
10         else
11             start=mid+1;
12     }
13     return -1;            
14 }

　　查找第一个比K大的数：

public int binarySearch(int[]a,int x){
    int start=0;
    int end=a.length;
    int cur=-1;
    while(start<=end){
        int mid=(start+end)/2;
        if(a[mid]<x){
            start=mid+1;        
        }else{
            cur=mid;
            end=mid-1;
        }
    }
    if(cur==-1){
        System.out.println("No suitable Num");
        return -1;
    }else{
        return a[cur];    
    }        
}