算法

一、几种排序方式：

插入排序（直接插入、折半插入、希尔）

交换排序（冒泡、快速）

选择排序（简单选择、堆排序）

归并排序

基排序

关于排序的特点与总结：

（1）当n较小时，可选择直接插入排序、简单选择排序；

（2）当n较大时，选择时间复杂度为n*log2n的排序：快速排序、堆排序；

（3）当数据初始状态基本有序时，使用直接插入排序、冒泡排序。

1、冒泡排序

public class Bubble {

    public static void main(String[] args) {
        int[] a = {23,33,2,25,18,29,99};
        for(int i=0;i<a.length;i++){
            //方法一
            for(int j=i+1;j<a.length;j++){
                if(a[i]>a[j]){
                    int temp=a[j];
                    a[j]=a[i];
                    a[i]=temp;
                }
            }
            //方法二
            for(int j=0;j<a.length-1-i;j++){
                if(a[j]>a[j+1]){
                    int temp=a[j];
                    a[j]=a[j+1];
                    a[j+1]=temp;
                }
            }
        }
        
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }

    }

}

2、二分查找

public static int binary(int[] a,int key){
        int low=0,high=a.length-1,mid;
        while(low<high){
            mid=(low+high)/2;
            if(a[mid]==key){
                return mid;
            }else if(a[mid]>key)
                low=mid+1;
            else
                high=mid-1;
        }
        return -1;
    }

3、快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

package algorithm;

public class Quick {

    public static void main(String[] args) {
        int[] a = {3,1,2,4,55,7,24,667,23};
        QuickSort(a,0,a.length-1);
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }

    }
    
    public static void QuickSort(int[] a,int low,int high){
        if(low<high){
            int pivotpos = Partition(a,low,high);
            QuickSort(a,low,pivotpos-1);
            QuickSort(a,pivotpos+1,high);
        }
        
    }
    public static int Partition(int[] a,int low,int high){
        int pivot = a[low];
        while(low<high){
            while(low<high&&a[high]>=pivot)
                --high;
            a[low]=a[high];
            while(low<high&&a[low]<=pivot)
                ++low;
            a[high]=a[low];            
        }
        a[low]=pivot;
        return low;　　//返回枢轴的最终位置
        
        
    }

}

4、递归实现1+2+...+100

    public static int getSum(int n){
        if(n<=0)
            return -1;
        if(n==1)
            return 1;
        else
            return getSum(n-1)+n;
    }